Как сделать бинарное дерево средствами STL

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

А можно обойтись и простым вектором, как сделано в прилагаемом коде - ведь "дерево" - всего лишь логический способ организации данных.

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

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

Всего существует 3 основных способа обхода двоичного дерева - прямой, симметричный (поперечный) и обратный, наверное, это проще изобразить, чем описать словами:

Прямой обход двоичного дерева

Симметричный обход двоичного дерева

Обратный обход двоичного дерева

В программу "зашито" для теста такое вот незамысловатое дерево:

Тестовое двоичное дерево

Вот полный исходник демо-программки, проверена в Visual Studio 2010 Express.

#include <iostream>
#include <vector>
using namespace std;

struct node { //структура для "дерева чисел"
 unsigned int data;
 int left;
 int right;
};

void makeNode (vector <struct node> &v1, int data) { //создать узел, не добавляя
 struct node b1 = { data, -1, -1 };
 v1.push_back(b1);
}

void setLeftNode (vector <struct node> &v1, int current, int data) { //поставить узел влево
 unsigned int leftIndex = v1.size();
 v1[current].left = leftIndex;
 makeNode (v1, data);
}

void setRightNode (vector<struct node> &v1, int current, int data) { //поставить узел вправо
 unsigned int rightIndex = v1.size();
 v1[current].right = rightIndex;
 makeNode (v1, data);
}

int insertNode (vector <struct node> &v1, int data) { //вставить узел
 if (v1.size() == 0) return -1; //сначала создать хотя бы 1 узел через makeNode
 unsigned int currentIndex = 0;
 while ( currentIndex < v1.size() ) {
  if (data <= v1[currentIndex].data) { //меньшие, либо равные числа идут в левое поддерево
   if(v1[currentIndex].left == -1) {
     setLeftNode (v1, currentIndex, data);
     return 1;
   }
   else currentIndex = v1[currentIndex].left;
  }
  else { 
   if (v1[currentIndex].right == -1) {
    setRightNode (v1, currentIndex, data);
    return 1;
   }
   else currentIndex = v1[currentIndex].right;
  }
 }
 return 0;
}

void preOrderTraversing(vector <struct node> &v1, unsigned int index) { //прямой обход
 cout << v1[index].data << ' '; //убрать, если не нужен вывод в консоль
 if (v1[index].left != -1) preOrderTraversing(v1,v1[index].left );
 if (v1[index].right != -1) preOrderTraversing(v1, v1[index].right);
}

void inOrderTraversing(vector <struct node> &v1, unsigned int index) { //симметричный обход
 if (v1[index].left != -1) inOrderTraversing (v1,v1[index].left );
 cout << v1[index].data << ' '; //убрать, если не нужен вывод в консоль
 if (v1[index].right != -1) inOrderTraversing (v1,v1[index].right);
}

void postOrderTraversing(vector <struct node> &v1, unsigned int index) { //обратный обход
 if (v1[index].left != -1) postOrderTraversing(v1,v1[index].left );
 if (v1[index].right != -1) postOrderTraversing(v1, v1[index].right);
 cout << v1[index].data << ' '; //убрать, если не нужен вывод в консоль
}

int main () {
 vector <struct node> v1;
 makeNode(v1, 5);
 int order[] = { 3, 7, 1, 4, 6, 8 }; //порядок добавления узлов для теста
 int n = sizeof(order)/sizeof(int); //количество добавляемых узлов
 for (int i=0; i<n; i++) insertNode(v1, order[i]);

 cout << endl << "Tree is: ";
 for (int index=0; index<v1.size(); index++) 
   cout << endl << index << ")\t" <<
         "data=" << v1[index].data << "\t" <<
         "leftIndex=" << v1[index].left << "\t" <<
         "rightIndex=" << v1[index].right;

 cout << endl << "pre-order traversing: ";
 preOrderTraversing (v1,0);
 cout << endl << "in-order traversing: ";
 inOrderTraversing (v1, 0);
 cout << endl << "post-order traversing: ";
 postOrderTraversing (v1,0);

 cin.sync(); cin.get(); return 0;
}

Результат выполнения программы:

Tree is:
0)      data=5  leftIndex=1     rightIndex=2
1)      data=3  leftIndex=3     rightIndex=4
2)      data=7  leftIndex=5     rightIndex=6
3)      data=1  leftIndex=-1    rightIndex=-1
4)      data=4  leftIndex=-1    rightIndex=-1
5)      data=6  leftIndex=-1    rightIndex=-1
6)      data=8  leftIndex=-1    rightIndex=-1
pre-order traversing: 5 3 1 4 7 6 8
in-order traversing: 1 3 4 5 6 7 8
post-order traversing: 1 4 3 6 8 7 5

13.05.2016, 14:45 [8833 просмотра]