Собственно класс бинарного дерева я прописал (хоть и криво, не в этом дело).
Но метод вставки не подходит к поставленной задачи.
А именно:
На вход программы подается массив (например: 1 4 6 10 0 0 0 7...), где каждый ноль это листок-затычка после которого добавлять ничего нельзя, а все числа добавляются слева на право (сложно объяснить, на скрине пример)
Вот мой класс дерева: h:
#pragma once
class binTree
{
struct Node
{
int Value;
Node * pLeft;
Node * pRight;
Node * pParent;
Node(int x) :Value(x), pLeft(NULL), pRight(NULL), pParent(NULL) {}
};
Node * m_pRoot;
void InoderTreeWalk(Node * x);
Node * TreeSuccessor(Node *x);
Node * TreeMin(Node * x);
public:
binTree();
~binTree();
void TreeInsert(int k);
Node * TreeSearch(Node * X, int k);
void ShowTree();
int Root();
};
cpp:
#include "stdafx.h"
#include "binTree.h"
binTree::binTree()
{
m_pRoot = NULL;
cout << " binTree::binTree() " << this << endl;
}
binTree::~binTree()
{
cout << " binTree::~binTree() " << this << endl;
}
int binTree::Root()
{
return m_pRoot->Value;
}
/*Нормальная функция вставки*/
void binTree::TreeInsert(int k)
{
Node * z = new Node(k);
Node * y = NULL;
Node * x = m_pRoot;
while (x != NULL)
{
y = x;
if (z->Value < x->Value)
x = x->pLeft;
else
x = x->pRight;
}
z->pParent = y;
if (y == NULL)
m_pRoot = z;
else if (z->Value < y->Value)
y->pLeft = z;
else
y->pRight = z;
}
binTree::Node * binTree::TreeSearch(binTree::Node * X, int k)
{
if (X == NULL || k == X->Value)
return X;
if (k < X->Value)
return TreeSearch(X->pLeft, k);
else
return TreeSearch(X->pRight, k);
}
void binTree::InoderTreeWalk(Node * x)
{
if (x != NULL)
{
InoderTreeWalk(x->pLeft);
cout << ' ' << x->Value;
if (x->pParent != NULL)
cout << " Parent = " << x->pParent->Value << endl;
else
cout << endl;
InoderTreeWalk(x->pRight);
}
}
binTree::Node * binTree::TreeSuccessor(Node * x) // поиск следующего элемента
{
if (x->pRight != NULL)
return TreeMin(x->pRight);
Node * y = x->pParent;
while (y != NULL && x == y->pRight)
{
x = y;
y = y->pParent;
}
return y;
}
binTree::Node * binTree::TreeMin(Node * x)
{
while (x->pLeft != NULL)
x = x->pLeft;
return x;
}
void binTree::ShowTree()
{
cout << "\n Tree: \n";
InoderTreeWalk(m_pRoot);
cout << "\n\n";
}
Функция TreeInsert вставляет новые значения так, как это должно происходить в нормальном дереве поиска.
А мне нужна функция которая будет вставлять новые элементы как показано в примере (как на скрине).