Как пройти по двоичному дереву и подсчитать вхождение значения без передачи значения

Question

В настоящее время я работаю над программой для реализации двоичного дерева поиска. Структура для дерева выглядит следующим образом:

struct treeNode { 
    Type value; 
    int count; 
    treeNode* left; 
    treeNode* right; 
}; 
treeNode* root; 

Я пытаюсь реализовать следующую функцию:

template <class Type> 
int bstree<Type>::count(){ 

return count(root); 
} 

template <class Type> 
int bstree<Type>::count(treeNode* sroot){ 


} 

Я пытаюсь выяснить, как я хотел бы посетить каждый узел и сложить все количество значения для каждого узла.

Answer 1

Я не уверен, почему вы передаете аргумент ... не так ли?

template <class Type> 
int treeNode<Type>::get_count() 
{ 
    int result = count; 
    if (left) result += left->get_count(); 
    if (right) result += right->get_count(); 
    return result; 
} 

, а затем вы называете root->get_count();

Answer 2

template <class Type> 
int bstree<Type>::count(treeNode* sroot){ 
    int ret = 0; 
    if (sroot) 
    { 
     ret = sroot->count; 
     ret += count(sroot->left); 
     ret += count(sroot->right); 
    } 

    return ret; 
} 

Answer 3

Некоторые сумасшедшие C++ есть

Единственный способ, которым я вижу, что вы могли бы сделать это, чтобы иметь глобальную переменную, которая обновляется с помощью двух функций обратного вызова , один идет влево и вправо. Вы начинаете с первого узла. Каждый узел, который вы достигнете, должен привести к запуску другого экземпляра/потока этих функций. Рекурсия может быть непригодной, поскольку она может привести к переполнению стека. Вам нужно создать два новых потока на каждом узле, чтобы перейти от текущего дерева влево и вправо. Сначала я подумал, что есть возможность ходить в узел несколько раз, но теперь я понимаю, что этого никогда не должно быть, потому что левый правый ход всегда будет происходить на другом уровне дерева. Я предполагаю, что вы правильно реализовали дерево, потому что, если вы случайно создали круговую очередь/список с указателями, добро пожаловать на бесконечность, если вы не отметите каждое значение, которое было подсчитано, как было предложено ранее.

Я не использовал C++ в течение многих лет, но вы должны иметь возможность указывать указатель на список, тогда вы можете обманывать и не нуждаться ни в одном из вышеперечисленных, просто перемещайте его последовательно.