C++ : Алгоритмы - Бинарное дерево поиска. Часть IV

Четвертая часть статьи про реализацию Бинарных деревьев на С++.

Реализовывать будем Обходы дерева. 

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

1) Прямой порядок (англ. preorder)

        Посетить корень, посетить левое поддерево, посетить правое поддерево.

Пример

2)Обратный порядок (англ. postorder)

    Посетить левое поддерево, посетить правое поддерево, посетить корень

Пример

3)  Центрированный (центральный) порядок (англ. inorder)

  Посетить левое поддерево, посетить корень, посетить правое поддерево. Этот метод особенно часто используется, так как дает возможность обхода вершин в порядке возростания их значений.

4) Обход в ширину (англ. Breadth First) 

  Узлы посещаются уровень за уровнем. Каждый уровень обходится слева направо.

Результаты обходов для дерева  22(14(7(_9)17)31),

Рассматриваемые функции :

       void Order(int indef);//Обходы

       void tempOrderAcess();//вывод обходов на экран

       void _PreOrder(BinaryTree<TypeOfTree>* element);//прямой

       void _PostOrder(BinaryTree<TypeOfTree>* element);//обратный

       void _InOrder(BinaryTree<TypeOfTree>* element);//централизированый

       void _BreadthFirstSearch();//в ширину

Листинги:

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::tempOrderAcess(){

       for(auto it = this->tempOrder.begin(); it<this->tempOrder.end();++it)

             cout<<"["<<*it<<"]";

}

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::Order(int indef){

       this->tempOrder.clear();

       switch(indef){

             case 1:_PreOrder(rootOfTree);break;

             case 2:_PostOrder(rootOfTree);break;

             case 3:_InOrder(rootOfTree);break;

             case 4:_BreadthFirstSearch();break;

       }

}

// Прямой обход

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::_PreOrder(BinaryTree<TypeOfTree>* element){

       if (element) {

             this->tempOrder.push_back(element->field);

             _PreOrder(element->leftPointer);

             _PreOrder(element->rightPointer);

       }

}

// Обратный обход

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::_PostOrder(BinaryTree<TypeOfTree>* element){

       if (element) {

             _PostOrder(element->leftPointer);

             _PostOrder(element->rightPointer);

             this->tempOrder.push_back(element->field);

       }

}

// Централизированый обход

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::_InOrder(BinaryTree<TypeOfTree>* element){

       if (element) {

             _InOrder(element->leftPointer);

             this->tempOrder.push_back(element->field);

             _InOrder(element->rightPointer);

       }

}

template <typename TypeOfTree>

void MainBinaryTree<TypeOfTree>::_BreadthFirstSearch(){

       queue<BinaryTree<TypeOfTree>*> tempQueue;

       tempQueue.push(rootOfTree);//запихиваем в очередь первый уровень(тоисть root)

       while (!tempQueue.empty()) {

             //если у текущего узла есть дети, то их тоже добавляем в очередь

             if (tempQueue.front()->leftPointer)

                    tempQueue.push(tempQueue.front()->leftPointer);

             if (tempQueue.front()->rightPointer)

                    tempQueue.push(tempQueue.front()->rightPointer);

             //вытягиваем с очереди информационное поле последнего элемента

             this->tempOrder.push_back(tempQueue.front()->field);

             tempQueue.pop();

       }

}

Пока хватит =)