Вот Вам программа.
Некоторое уточнение к предыдущему.
В данной программе для вывода используется рекурсия, поэтому задавать текущий узел параметром
необходимо, но тогда вызываемую функцию с параметрами необходимо определить, как private
Как и удаление дерева...
Для вставки передавать корень параметром необходимости нет.
Кое-что подправил, прокомментировал
[code h=200]
#include <iostream>
using namespace std;
#define nullptr 0
struct Node
{
int key;
Node *left;
Node *right;
Node *parent;
};
template<class T>
class Bintree
{
public:
//конструктор
Bintree<T>(){head = nullptr;};
//деструктор
~Bintree(void);
//вставка
void insert(T k);
//вывод
void show(int sp=20);
private:
Node* head;
void FreeNode(Node *node);
void show(Node *node, int sp);
};
template<class T>
void Bintree<T>::FreeNode(Node *node)
{
if (node)
{
Bintree::FreeNode(node->left); //левого потомка
Bintree::FreeNode(node->right); //правого потомка
delete node; //память самого узла
}
}
template<class T>
Bintree<T>::~Bintree()
{
Bintree<T>::FreeNode(head);
}
template <typename T>
void Bintree<T>::insert(T k)
{
Node *z = new Node; //создаем новый узел
z->key = k; //ключ
z->left = z->right = nullptr; //обнулим указатели на потомков
if (head == nullptr) //был ли корень?
{ //если дерева нет то формируем корень
z->parent = nullptr; //у корня родителя нет
head = z; //сохраним как корень
}
else
{
Node *x = head; //начинаем обход с корня
while (1) //по всем узлам
{
if (z->key > x->key) //если ключ нового узла больше текущего
{
if (x->right != nullptr)//и если правый потомок непустой
x = x->right; //то правого потомка делаем текущим
else
{ //правый пустой
z->parent = x; //текущий для нового будет родителем
x->right = z; //а правым потомком текущего станет новый
break; //новый узел вставлен в дерево - выходим из цикла
}
}
else if (z->key < x->key) //если ключ нового узла меньше текущего
{
if (x->left != nullptr) //и левый потомок непустой
x = x->left; //то левого потомка делаем текущим
else
{ //левый пустой
z->parent = x; //текущий для нового будет родителем
x->left = z; //а левым потомком текущего станет новый
break; //новый узел вставлен в дерево - выходим из цикла
}
}
else
{
delete z; //если равно, то удалим созданный узел (игнорируем!)
break; //и выходим из цикла
}
}
}
}
template <typename T> //показываем элементы дерева
void Bintree<T>::show(int sp)
{
Bintree<T>::show(head, sp);
}
template <typename T> //показываем элементы дерева
void Bintree<T>::show(Node *node, int sp=20)
{
if (node == nullptr)
return;
show(node->right, sp + 5);
for (int i = 0; i < sp; ++i) cout << ' ';
cout << node->key << endl;
show(node->left, sp + 5);
}
int main()
{
Bintree<int> tree; //создаем класс
tree.insert(5); //вставим несколько узлов
tree.insert(3);
tree.insert(7);
tree.insert(6);
tree.show(); //выведем с позиции 20 (по умолчанию)
tree.insert(4); //добавим еще несколько узлов
tree.insert(8);
tree.show(0); //выведем с 0 позиции
tree.insert(8); //пытаемся добавить узел с существующим ключом
tree.show(0); //выводим
return 0;
}
[/code]