#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stack>
#include <queue>
#include "TreeH.h"
using namespace std;
template <class T>
void BinaryTree<T>::Insert(const T &x)
{
Insert(x, root);
}
template <class T>
void BinaryTree<T>::Insert(const T &x, BinaryNode * &t)
{
if(t == NULL)
t = new BinaryNode(x);
else if(x < t ->data)
Insert(x, t ->left);
else if(x > t ->data)
Insert(x, t ->right);
}
template <class T>
void BinaryTree<T>::Remove(const T &x)
{
Remove(x, root);
}
template <class T>
void BinaryTree<T>::Remove(const T &x, BinaryNode * &t)
{
if(t == NULL)
return;
if(x < t ->data)
Remove(x, t->left);
else if(x > t ->data)
Remove(x, t->right);
else if(t->left != NULL && t->right != NULL)
{
t->data = FindMin(t->right)->data;
Remove(t->data,t->right);
}
else
{
BinaryNode *OldNode = t;
t = (t->left != NULL) ? t->left : t->right;
}
}
template <class T>
void BinaryTree<T>::PreOrder(BinaryNode *t) const
{
if(t != NULL)
{
cout << t ->data << " ";
PreOrder(t ->left);
PreOrder(t ->right);
}
}
template <class T>
void BinaryTree<T>::Inorder(BinaryNode *t) const
{
if(t != NULL)
{
Inorder(t ->left);
cout << t ->data << " ";
Inorder(t ->right);
}
}
template <class T>
void BinaryTree<T>::PostOrder(BinaryNode *t) const
{
if(t != NULL)
{
PostOrder(t ->left);
PostOrder(t ->right);
cout << t ->data << " ";
}
}
template <class T>
void BinaryTree<T>::PreWithoutRecusion(BinaryNode *t) const
{
if(t == NULL)
return;
stack<BinaryNode *> S;
BinaryNode *p = t;
while(!S.empty() || p)
{
while(p)
{
cout << p ->data << " ";
S.push(p);
p = p ->left;
}
if(!S.empty())
{
p = S.top();
S.pop();
p = p->right;
}
}
}
template <class T>
void BinaryTree<T>::InWithoutRecusion(BinaryNode *t) const
{
if(t ==NULL)
return;
stack<BinaryNode *> S;
BinaryNode *p = t;
while(!S.empty() || p)
{
while(p)
{
S.push(p);
p = p ->left;
}
if(!S.empty())
{
p = S.top();
cout << p ->data << " ";
S.pop();
p = p->right;
}
}
}
template <class T>
void BinaryTree<T>::LeveleOrder(BinaryNode * p) const
{
if(p == NULL)
return;
queue<BinaryNode *> Q;
//BinaryNode *p = t;
while(!Q.empty() || p)
{
cout << p ->data << " ";
if(p ->left) Q.push(p ->left);
if(p ->right) Q.push(p ->right);
if(Q.empty() == true)
return;
p = Q.front();
Q.pop();
}
}
template <class T>
bool BinaryTree<T>::Contain(const T &x) const
{
return Contain(x, root);
}
template <class T>
bool BinaryTree<T>::Contain(const T &x, BinaryNode *t) const
{
if(x == t ->data)
return true;
else if(x < t ->data)
return Contain(x, t ->left);
else if(x > t ->data)
return Contain(x, t ->right);
else
return false;
}
template <class T>
BinaryTree<T>::BinaryNode * BinaryTree<T>::FindMin(BinaryNode *t) const
{
if(t == NULL)
return NULL;
if(t->left == NULL)
return t;
return FindMin(t->left);
}
int main()
{
cout << " ************************************************************************" << endl;
cout << " * 1.向树中添加元素 2.删除指定树元素 3.判断是否包含指定该元素 *" << endl;
cout << " * 4.先序递归遍历树 5.中序递归遍历树 6.后序递归遍历树 *" << endl;
cout << " * 7.先序非递归遍历树 8.中序非递归遍历树 9.层次非递归遍历树 *" << endl;
cout << " * 按其它键退出 *"<< endl;
cout << " ************************************************************************" << endl;
BinaryTree<int> BT;
int x, quit = 0;
while(!quit)
switch(getch())
{
case '1':
cout << "请输入要添加的元素：" << endl;
cin >> x;
BT.Insert(x);
cout << "添加成功!" << endl;
//BT.LeveleOrder(BT.GetRoot());
//cout << endl;
break;
case '2':
cout << "请输入要删除的元素：" << endl;
cin >> x;
BT.Remove(x);
cout << "树中元素为：" << endl;
BT.PreOrder(BT.GetRoot());
cout << endl;
break;
case '3':
cout <<"请输入要判断该元素：" << endl;
cin >> x;
if(BT.Contain(x) == true)
cout << "存在!" << endl;
else
cout << "不存在！" << endl;
case '4':
cout << "先序递归遍历树中元素为：" << endl;
BT.PreOrder(BT.GetRoot());
cout << endl;
break;
case '5':
cout << "中序递归遍历树中元素为：" << endl;
BT.Inorder(BT.GetRoot());
cout << endl;
break;
case '6':
cout << "后序递归遍历树中元素为：" << endl;
BT.PostOrder(BT.GetRoot());
cout << endl;
break;
case '7':
cout << "先序非递归遍历树中元素为：" << endl;
BT.PreWithoutRecusion(BT.GetRoot());
cout << endl;
break;
case '8':
cout << "中序非递归遍历树中元素为：" << endl;
BT.InWithoutRecusion(BT.GetRoot());
cout << endl;
break;
case '9':
cout << "层次非递归遍历树中元素为：" << endl;
BT.LeveleOrder(BT.GetRoot());
cout << endl;
break;
default:
quit=1;
}
return 0;
}
