, какой должна быть структура двоичного поиска узла дерева

Question

я пытаюсь сделать гр программу ++ для двоичного дерева поиска, которая будет содержать следующие функциональные возможности (на самом деле это часть моего назначения колледжа):

A) создать двоичный поиск дерево.

B) Inorder, preorder, postorder traversals. (нерекурсивный)

C) Поиск Val в дереве.

D) Ширина первого прохода.

Е) Глубина первого обхода

F), граф листьев узлы, не-листа узлов.

G) Подсчет №. уровни

мои сомнения: -

1. обычно узел дерева имеет следующую структуру:

class node{ 

private: 
    node *lChild; 
    int info; 
    node *rChild; 
} 

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

class node{ 

private: 
    node *parent //pointer to parent node 
    node *lChild; 
    int info; 
    node *rChild; 
} 

рассматривается как обычная практика или плохая форма программирования двоичного дерева? и если это не считается хорошим способом программирования дерева, есть ли какой-либо другой способ или я должен использовать метод, указанный в книгах с использованием стека (для Depth First) и очереди (для первой ширины) для хранения узлов (посещенных или не посетил соответственно)

2. Это первый раз, когда я учу структуры данных, это будет большим подспорьем, если кто-то может объяснить простыми словами, что есть разница между рекурсивной и не рекурсивной обходе с двоичным учитываемое дерево

Answer 1

1. Вам не нужен указатель на родительский узел. Подумайте о случаях, когда вы будете использовать его. Единственный способ, которым вы можете добраться до узла, - через его родителя, так что вы уже посетили родителя.

2. Знаете ли вы, что такое рекурсивные средства?

Answer 2

я изменить структуру узла и добавить еще один указатель, указывающий на родительский [...] в это рассматривается как нормальная практика или плохая форма программирования бинарного дерева?

Это не обычная практика (но не совсем «плохая форма»). Каждый узел представляет собой набор данных и два указателя. Если вы добавите третий указатель на каждый узел, вы увеличите накладные расходы каждого узла на 50% (два указателя на три указателя на узел), которые для большого двоичного дерева будут довольно много.

Это первый раз, когда я учу структуры данных, это будет большая помощь, если кто-то может объяснить простыми словами, что есть разница между рекурсивной и не рекурсивной обходе

Рекурсивный реализации это функция, которая применяется только к узлу, а затем вызывает себя для последующих узлов. Это позволяет использовать стек вызовов приложения для обработки узлов дерева.

Рекурсивная реализация использует локальный стек для перемещения непереработанных узлов; то он зацикливается до тех пор, пока в стеке будут данные и обрабатывает каждую запись.

Вот пример для печати на консоль, которая показывает разницу между рекурсивной и не рекурсивной (пример является неполным, так как это домашнее задание:]):

void recursive_print(node* n) { 
    std::cout << n->info << "\n"; 
    if(n->lChild) 
     recursive_print(n->lChild); // recursive call 
    // n->rChild is processed the same 
} 
void non_recursive_print(node* n) { 
    std::stack<node*> stack; 
    stack.push(n); 
    while(!stack.empty()) { // behaves (more or less) the same as 
          // the call-stack in the recursive call 
     node* x = stack.top(); 
     stack.pop(); 
     std::cout << x->info << "\n"; 
     if(x->lChild) 
      stack.push(x->lChild); // non-recursive: push to the stack 
     // x->rChild is processed the same way 
    } 
} 
// client code: 
node *root; // initialized elsewhere 
if(root) { 
    recursive_print(root); 
    non_recursive_print(root); 
} 

Answer 3

Там нет ничего, чтобы остановить вас добавление родителя указатель, если хотите. Однако это обычно не требуется и немного увеличивает размер и сложность.

Обычный подход для обхода дерева - это своего рода рекурсивная функция. Вы сначала вызываете функцию и передаете корневой узел дерева. Затем функция вызывает себя, передавая дочерние указатели (по одному за раз). Это происходит рекурсивно вплоть до дерева, пока не осталось дочерних узлов.

Функция выполняет любую обработку, которую вы хотите, на своем собственном узле после возврата рекурсивных вызовов. Это означает, что вы в основном перемещаетесь по дереву с каждым вызовом (делая ваш стек вызовов прогрессивно глубже), а затем выполняете обработку на обратном пути по мере возврата каждой функции.

Функция должна никогда не попытаться вернуться к дереву так же, как это произошло (т. Е. Передать родительский указатель), иначе вы закончите бесконечную рекурсию.

Answer 4

Обычно требуется только родительский указатель, если вам необходимо поддерживать итерация Представьте, что вы нашли узел листьев, а затем хотите найти следующий узел (самый низкий ключ больше текущего ключа), например:

mytree::iterator it1=mytree_local.find(7); 
if (it1 != mytree_local.end()) 
{ 
    mytree::iterator it2=it1.next(); // it1 is a leaf node and next() needs to go up 
} 

Поскольку здесь вы начинаете в нижней части, а не в верхнем, вам нужно идти

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

Answer 5

Я предлагаю вам ознакомиться с шаблоном Посетителя - для его аромата, а не только для его структуры (это очень сложно).

По существу, это шаблон проектирования, который отключает обход дерева таким образом, что у вас есть только один набор кодов, которые обходят обход дерева, и вы используете этот набор кода для выполнения различных функций на каждом узле. Код обхода обычно не является частью класса Node.

В частности, это позволит вам не писать код обхода более одного раза. Например, ответ utnapistims заставит вас написать код обхода для каждой необходимой вам функции; этот пример охватывает печать - для ouputXML() потребуется другая копия кода обхода. В конце концов, ваш класс Node становится огромным неуклюжим зверем.

С помощью Visitor у вас будут свои классы Tree и Node, отдельный класс Traversal и многочисленные функциональные классы, такие как PrintNode, NodeToXML и, возможно, DeleteNode, для использования с классом Traversal.

Что касается добавления указателя родителя, это было бы полезно только в том случае, если вы намеревались припарковаться на данном узле между вызовами к дереву - т. Е. Вы собираетесь выполнять относительный поиск, начинающийся на предварительно выбранном произвольном узле. Это, вероятно, означает, что вам лучше не делать многопоточной работы с указанным деревом. Указатель родителя также будет трудно обновить, так как красное/черное дерево может легко вставить новый узел между текущим узлом и его «родителем».

Я бы предложил класс BinaryTree с методом, который создает экземпляр одного класса Visitor, а класс посетителей принимает реализацию интерфейса Traversal, который будет одним из Breadth, Width или Binary. В принципе, когда посетитель готов перейти к следующему узлу, он вызывает реализацию интерфейса Traversal для его получения (следующий узел).