Драйвер проверки класса Tree #include <iostream.h> #include <iomanip.h> ©S- #include tree.h

main () I {

Tree<int> intTree; int intVal;

template<class NODETYPE>

void Tree<NODETYPE>::preOrderTraversalО const { preOrderHelper(rootPtr); }

template<class NODETYPE>

void Tree<NODETYPE>::preOrderHelper(TreeNode<NODETYPE> *ptr) const {

if (ptr != 0) {

cout ptr->data ; preOrderHelper(ptr->leftPtr) ; preOrderHelper(ptr->rightPtr) ;

template<class NODETYPE>

void Tree<NODETYPE>::inOrderTraversal() const { inOrderHelper(rootPtr); }

template<class NODETYPE>

void Tree<NODETYPE>::inOrderHelper(TreeNode<NODETYPE *ptr) const {

if (ptr 1= 0) {

inOrderHelper(ptr->leftPtr) ; cout ptr->data ; inOrderHelper(ptr->rightPtr);

template<class NODETYPE>

void Tree<NODETYPE>::postOrderTraversal0 const { postOrderHelper(rootPtr); }

template<class NODETYPE>

void Tree<NODETYPE>::postOrderHelper(TreeNode<NODETYPE> *ptr) const

if (ptr != 0) {

postOrderHelper(ptr->leftPtr); postOrderHelper(ptr->rightPtr) ; cout ptr->data ;

#endif

Tree<float> floatTree; float floatVal;

Ив

cout endl endl endl

Введите 10 чисел с плавающей точкой: endl << setiosflags(ios::fixed ios::showpoint) setprecision(1); for (i = 0; i < 10; i++) { cin floatVal; floatTree.insertNode(floatVal);

cout << endl << Обход в ширину <<endl; floatTree.preOrderTraversal();

cout << endl << Последовательный обход << endl; floatTree.inOrderTraversal ();

cout << endl << Обратный обход << endl; floatTree.postOrderTraversal()g

return 0;

Ж }

Рис. 15.16. Создание бинарного дерева и его обход (часть 4 из 4)

Каждая из функций-элементов inOrderTraversal, preOrderTraversal и postOrderTraversal обходит дерево (см. рис. 15.18) и печатает значения в узлах.

Функция-элемент inOrderTraversal осуществляет последовательный обход дерева, выполняя следующие шаги:

1) Обход левого поддерева с помощью inOrderTraversal.

2) Обработка значения в узле (т.е. печать значения в этом узле).

3) Обход правого поддерева с помощью inOrderTraversal.

Значение в узле не обрабатывается до тех пор, пока не будут обработаны значения в его левом поддереве. Функция-элемент inOrderTraversal для дерева, показанного на рис. 15.18, выдает следующие значения:

6 13 17 27 33 42 48

cout Введите 10 целых чисел: endl; for (int i = 0; i < 10; i++) { cin >> intVal; intTree.insertNode(intVal);

Ж:. }

cout << endl << Обход в ширину <<endl; 5*- intTree.preOrderTraversal() ;

cout << endl << Последовательный обход << endl;

intTree.inOrderTraversal ();

cout <<endl << Обратный обход <<endl;

intTree.postOrderTraversal();

Введите 1О целых чисел: 50 25 75 12 33 67 88 б 13 68

Обход в ширину: 50 25 12 6 13 33 75 67 68 88

Последовательный обход:

6 12 13 25 33 50 67 68 75 88

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

6 13 12 33 25 68 67 88 75 50

Введите 10 чисел с плавающей точкой:

39.2 16.5 82.7 3.3 65.2 90.8 1.1 4.4 89.5 92.5

Обход в ширину:

39.2 16.5 3.3 1.1 4.4 82.7 65.2 90.8 89.5 92.5 Последовательный обход:

1.1 3.3 4.4 16.5 39.2 65.2 82.7 89.5 90.8 92.5 Обратный обход:

1.1 .4 3.3 16.5 65.2 89.5 92.5 90.8 82.7 39.2

Рис. 15.17. Пример вывода данных программы, приведенной на рис. 15.16

Заметим, что функция-элемент inOrderTraversal печатает узловые значения в порядке их возрастания. Процесс создания дерева двоичного поиска в действительности сортирует данные - поэтому этот процесс называется сортировкой бинарного дерева.

Функция-элемент preOrderTraversal осуществляет обход дерева в ширину (прямой обход), выполняя следующие шаги:

1) Обработка значения в узле (печать).

2) Обход левого поддерева с помощью preOrderTraversal.

3) Обход правого поддерева с помощью preOrderTraversal.

Значение в каждом узле обрабатывается, когда обход дерева проходит через этот узел. После того, как значение в данном узле обработано, обрабатываются значения в левом поддереве, а потом - в правом. Функция-элемент preOrderTraversal для дерева, показанного на рис. 15.18, выдает следующие значения:

27 13 6 17 42 33 48

Функция-элемент postOrderTraversal осуществляет обратный обход дерева, выполняя следующие шаги:

1) Обход левого поддерева с помощью postOrderTraversal.

2) Обход правого поддерева с помощью postOrderTraversal.

3) Обработка значения в узле.

Значение в каждом узле не печатается до тех пор, пока не распечатаны значения в его узлах потомках. Функция-элемент postOrderTraversal для дерева, показанного на рис. 15.18, выдает следующие значения:

6 17 13 33 48 42 27