题目：
编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。
算法描述：
首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述：
isLeaf函数：若该结点的左子树和右子树都为空，则为叶子结点。
isEmpty函数：根结点为空则为空树。
Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。
LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。
DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。
PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。
7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。
8、CreateTree函数：采用先序遍历序列构造二叉树，设‘0’为空结点，输入非‘0’数，生成新结点，递归创建左子树和右子树。
9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在结点的指针。如果当前结点为空，则返回；否则判断当前结点是否为目标结点，如果是，记住结点位置，返回；否则，递归地在左子树中查找，如果找到，记住结点位置，返回；否则，递归地在右子树中查找。判断temp是否为空，若为空，则未查找到给定元素。
10、LevelOrder函数：利用队列记录二叉树每一层，首先申请队列，申请指针pointer保存根结点，然后判断pointer是否为空，若不为空，则pointer入队。如果队列为空，跳出函数。队列首元素出队，赋给pointer，访问pointer所指结点，如果pointer所指结点的左子树不为空，则左子树根结点指针入队；如果pointer所指结点的右子树不为空，则右子树根结点指针入队，结束。
先序遍历，后序遍历思想与中序遍历一致，这里不再一一分析。最后创建一颗二叉树，用以检验各函数的功能。
源程序：
#include<iostream>
#include<stack>
#include<queue>
#include <cstdlib>
using namespace std;
template < class T >
class BinaryTree;
template < class T >
class BinaryTreeNode{
friend class BinaryTree< T >;
//friend class BinarySearchTree< T >;
private:
T data; //二叉树结点数据域
BinaryTreeNode< T > * left; //二叉树结点指向左子树的指针
BinaryTreeNode< T > * right; //二叉树结点指向右子树的指针
public:
BinaryTreeNode(){}; //默认构造函数
BinaryTreeNode(const T& ele) :left(NULL), right(NULL) {data = ele;};
//给定数据的构造函数
BinaryTreeNode(const T& ele,BinaryTreeNode< T > * l,BinaryTreeNode< T > * r);
//给定数据的左右指针的构造函数
~BinaryTreeNode(){}; //析构函数
T value() const{return data;}; //返回当前结点的数据
BinaryTreeNode< T >&operator=(const BinaryTreeNode< T >&Node){this=Node;};
//重载赋值操作符
BinaryTreeNode< T > * leftchild() const{return left;};
//返回当前结点指向左子树的指针
BinaryTreeNode< T > * rightchild() const{return right;};
//返回当前结点指向右子树的指针
void setLeftchild(BinaryTreeNode< T > * l){left = l;};
//设置当前结点的左子树
void setRightchild(BinaryTreeNode< T > * r){right = r;};
//设置当前结点的右子树
void setValue(const T& val){data = val;};
//设置当前结点的数据域
bool isLeaf() const; //判定当前结点是否为叶子结点，若是则返回true
};
template < class T >
BinaryTreeNode< T >::BinaryTreeNode(const T& ele,BinaryTreeNode< T > * l,BinaryTreeNode< T > * r) //给定数据的左右指针的构造函数
{
data = ele;
left = l;
right = r;
}
template < class T >
bool BinaryTreeNode< T >::isLeaf() const //判定当前结点是否为叶子结点，若是则返回true
{
if(data->left == NULL && data->right == NULL) //若左子树和右子树都为空，则返回true
return true;
else
return false;
}
template < class T >
class BinaryTree
{
protected:
BinaryTreeNode< T > * ROOT; //二叉树根结点指针
public:
BinaryTree(){ROOT=NULL;}; //构造函数
BinaryTree(BinaryTreeNode< T > * r){ROOT = r;}
~BinaryTree(){DeleteBinaryTree(ROOT);}; //析构函数
bool isEmpty() const; //判断二叉树是否为空树
void visit(const T& data){cout << data <<" ";} //访问当前结点
BinaryTreeNode< T > * & Root(){return ROOT;}; //返回二叉树的根结点
BinaryTreeNode< T > * Parent(BinaryTreeNode< T > * current);
//返回当前结点的双亲结点
void Parent_PreOrder(BinaryTreeNode< T > *curroot,BinaryTreeNode< T > *r,BinaryTreeNode< T > *&t); //运用先序遍历的思想查找双亲
BinaryTreeNode< T > * LeftSibling(BinaryTreeNode< T > * current);
//返回当前结点的左兄弟
BinaryTreeNode< T > * RightSibling(BinaryTreeNode< T > * current);
//返回当前结点的右兄弟
void CreateTree(BinaryTreeNode< T > * &r); //根据先序遍历序列构造二叉树
void DeleteBinaryTree(BinaryTreeNode< T > * root); //删除二叉树或其子树
void PreOrder(BinaryTreeNode< T > * root); //先序遍历二叉树或其子树
void InOrder(BinaryTreeNode< T > * root); //中序遍历二叉树或其子树
void PostOrder(BinaryTreeNode< T > * root); //后序遍历二叉树或其子树
void PreOrderWithoutRecusion(BinaryTreeNode< T > * root);
//非递归先序遍历二叉树或其子树
void InOrderWithoutRecusion(BinaryTreeNode< T > * root);
//非递归中序遍历二叉树或其子树
void PostOrderWithoutRecusion(BinaryTreeNode< T > * root);
//非递归后序遍历二叉树或其子树
void LevelOrder(BinaryTreeNode< T > * root); //按层序遍历二叉树或其子树
BinaryTreeNode<T> * Search( T &t, BinaryTreeNode<T> *r ); //二叉树搜索
void Search_PreOrder( T &t, BinaryTreeNode<T> *r, BinaryTreeNode<T> *&temp );
//运用先序遍历的思想查找给定数据所在结点
};
template < class T >
bool BinaryTree< T >::isEmpty() const //判断二叉树是否为空树
{
if(ROOT == NULL) //若根结点为空，则返回true
return true;
else
return false;
}
template <class T>
BinaryTreeNode<T> * BinaryTree<T>::Parent( BinaryTreeNode<T> *current )
//返回当前结点的双亲结点
{
if( !current || !ROOT || current == ROOT )
//若当前结点不存在或根结点为空或当前结点为根结点 ，则输出error且跳出函数
{
cout << "Error\n";
exit(0);
}
BinaryTreeNode<T> *temp = NULL; //初始化临时指针，temp用于保存最后查找到的双亲结点的地址
Parent_PreOrder( ROOT, current, temp ); //查找双亲的子程序
if(!temp) //结点不在树中，则双亲不存在
{
cout << "Your node doesn't belong to this tree!\n";
exit(0);
}
return temp;
}
template <class T>
void BinaryTree<T>::Parent_PreOrder( BinaryTreeNode<T> *curroot,BinaryTreeNode<T> *r, BinaryTreeNode<T> *&t ) //运用递归实现先序遍历，在遍历过程中判断是否找到双亲节点
{
if( !curroot || curroot->isLeaf() ) return; //当前结点为空或叶子结点
if( r == curroot->left || r == curroot->right ) //判断双亲结点的条件
{
t = curroot; //t是对temp的引用，在此修改temp的值
return;
}
else
{
Parent_PreOrder( curroot->left, r, t ); //在左子树中查找
if( t ) return; //如果已在左子树中找到，便不必在右子树中查找
Parent_PreOrder( curroot->right, r, t ); // 在右子树中查找
}
}
template <class T>
BinaryTreeNode<T> * BinaryTree<T>::LeftSibling( BinaryTreeNode<T> *current )
//返回当前结点的左兄弟
{
BinaryTreeNode<T> *temp = Parent(current); //先找到给定结点的双亲
if( !temp->left || current == temp->left )
//双亲的左孩子若不是结点本身，则是结点的左兄弟
{
cout << "This node doesn't have a leftsibling!\n";
exit(0);
}
return temp->left;
}
template <class T>
BinaryTreeNode<T> * BinaryTree<T>::RightSibling( BinaryTreeNode<T> *current )
//返回当前结点的右兄弟
{
BinaryTreeNode<T> *temp = Parent(current); //先找到给定结点的双亲
if( !temp->right || current == temp->right )
//双亲的右孩子若不是结点本身，则是结点的右兄弟
{
cout << "This node doesn't have a rightsibling!\n";
exit(0);
}
return temp->right;
}
template < class T >
void BinaryTree< T >::DeleteBinaryTree(BinaryTreeNode< T > * root) //删除二叉树或其子树
{
if(root == NULL) return; //判断是否为空树，若为空，则返回
DeleteBinaryTree( root->left ); //递归删除左子树
DeleteBinaryTree( root->right ); //递归删除右子树
delete root; //删除根结点
cout << "One node deleted!\n";
root = NULL; //根结点置为空
}
template < class T >
void BinaryTree< T >::PreOrder(BinaryTreeNode< T > * root) //先序遍历二叉树或其子树
{
if(root == NULL) //判断是否为空树，若为空，则返回
return;
visit(root->value()); //访问根结点
PreOrder(root->leftchild()); //先序遍历左子树
PreOrder(root->rightchild()); //先序遍历右子树
}
template < class T >
void BinaryTree< T >::PreOrderWithoutRecusion(BinaryTreeNode< T > * root)
//非递归先序遍历二叉树或其子树
{
stack< BinaryTreeNode< T > * >tStack;
BinaryTreeNode< T > * pointer = root; //保存输入参数
while(!tStack.empty()||pointer){
if(pointer){
visit(pointer->value()); //访问当前结点
tStack.push(pointer); //当前结点地址入栈
pointer = pointer->leftchild(); //当前链接结构指向左孩子
}
else{ //左子树访问完毕，转向访问右子树
pointer = tStack.top(); //当前链接结构指向栈顶的元素
tStack.pop(); //栈顶元素出栈
pointer = pointer->rightchild(); //指向右孩子
}
}
}
template < class T >
void BinaryTree< T >::InOrder(BinaryTreeNode< T > * root) //中序遍历二叉树或其子树
{
if(root == NULL) //判断是否为空树，若为空，则返回
return;
InOrder(root->leftchild()); //中序遍历左子树
visit(root->value()); //访问根结点
InOrder(root->rightchild()); //中序遍历右子树
}
template < class T >
void BinaryTree< T >::InOrderWithoutRecusion(BinaryTreeNode< T > * root)
//非递归中序遍历二叉树或其子树
{
stack< BinaryTreeNode< T > * >tStack;
BinaryTreeNode< T > * pointer = root;
while(!tStack.empty()||pointer){
if(pointer){
tStack.push(pointer); //当前结点地址入栈
pointer = pointer->leftchild(); //当前链接结构指向左孩子
}
else{ //左子树访问完毕，转向访问右子树
pointer = tStack.top(); //当前链接结构指向栈顶的元素
visit(pointer->value()); //访问当前结点
pointer = pointer->rightchild(); //指向右孩子
tStack.pop(); //栈顶元素出栈
}
}
}
template < class T >
void BinaryTree< T >::PostOrder(BinaryTreeNode< T > * root) //后序遍历二叉树或其子树
{
if(root == NULL) //判断是否为空树，若为空，则返回
return;
PostOrder(root->leftchild()); //后序遍历左子树
PostOrder(root->rightchild()); //后序遍历右子树
visit(root->value()); //访问根结点
}
enum Tag{L,R};
template < class T >
class StackNode{
public:
BinaryTreeNode< T > * pointer;
Tag tag;
};
template < class T >
void BinaryTree< T >::PostOrderWithoutRecusion(BinaryTreeNode< T > * root)
//非递归后序遍历二叉树或其子树
{
stack< StackNode< T > >tStack;
StackNode< T >Node;
BinaryTreeNode< T > * pointer = root;
do{
while(pointer != NULL){ //将左子树中的结点加Tag=L后压入栈中
Node.pointer = pointer;
Node.tag = L;
tStack.push(Node);
pointer = pointer->leftchild();
}
Node = tStack.top(); //栈顶元素出栈
tStack.pop();
pointer = Node.pointer;
if(Node.tag == R){ //如果从右子树回来
visit(pointer->value()); //访问当前结点
pointer = NULL; //置pointer为空，以继续弹栈
}
else{ //如果从左子树回来
Node.tag = R; //标志域置为R，进入右子树
tStack.push(Node);
pointer = pointer->rightchild();
}
}
while(!tStack.empty()||pointer);
}
template < class T >
void BinaryTree< T >::CreateTree(BinaryTreeNode< T > * &r) //根据先序遍历序列构造二叉树
{
int ch;
cin >> ch;
if(ch == 0)
r = NULL;
else{ //读入非0数
r = new BinaryTreeNode< T >(ch); //生成结点
CreateTree(r->left); //构造左子树
CreateTree(r->right); //构造右子树
}
}
template < class T >
void BinaryTree< T >::LevelOrder(BinaryTreeNode< T > * root) //按层序遍历二叉树或其子树
{
queue< BinaryTreeNode< T > * >tQueue;
BinaryTreeNode< T > * pointer = root;
if(pointer)
tQueue.push(pointer); //根结点入队列
while(!tQueue.empty()){
pointer = tQueue.front(); //获得队列首结点
tQueue.pop(); //当前结点出队列
visit(pointer->value()); //访问当前结点
if(pointer->leftchild() != NULL)
tQueue.push(pointer->leftchild()); //左子树入队列
if(pointer->rightchild() != NULL)
tQueue.push(pointer->rightchild()); //右子树入队列
}
}
template <class T>
BinaryTreeNode<T> * BinaryTree<T>::Search( T &t, BinaryTreeNode<T> *root ) //二叉树搜索
{
if( isEmpty() ) //判断是否为空，若为空树，则跳出函数
{
cout << "The tree is empty!\n";
exit(0);
}
BinaryTreeNode<T> *temp = NULL; //初始化临时指针，temp用于保存最后查找到的结点地址
Search_PreOrder( t, root, temp );
if( !temp ) //未查找到对应结点，将返回NULL
cout << t << " doesn't exist in the tree!\n";
return temp;
}
template <class T>
void BinaryTree<T>::Search_PreOrder( T &t, BinaryTreeNode<T> *root, BinaryTreeNode<T> *&temp )
//运用先序遍历的思想查找给定数据所在结点
{
if( !root ) return; //判断是否为空树，若为空，则返回
if( t == root->value()) //找到指定结点并用temp保存地址
{
temp = root;
return;
}
Search_PreOrder( t, root->left, temp ); //递归左子树
if( temp ) return; //如果已在左子树中找到，则返回temp
Search_PreOrder( t, root->right, temp ); //递归右子树
}
int main()
{
BinaryTree<int> my_tree; //定义my_tree
cout << "Create my tree :" << endl;
my_tree.CreateTree(my_tree.Root()); //创建my_tree
cout << "my_tree's PreOrder is ";
my_tree.PreOrder(my_tree.Root()); //先序遍历
cout << endl << "my_tree's PreOrderWithoutRecusion is ";
my_tree.PreOrderWithoutRecusion(my_tree.Root());
cout << endl << "my_tree's InOrder is ";
my_tree.InOrder(my_tree.Root()); //中序遍历
cout << endl << "my_tree's InOrderWithoutRecusion is ";
my_tree.InOrderWithoutRecusion(my_tree.Root());
cout << endl << "my_tree's PostOrder is ";
my_tree.PostOrder(my_tree.Root()); //后序遍历
cout << endl << "my_tree's PostOrderWithoutRecusion is ";
my_tree.PostOrderWithoutRecusion(my_tree.Root());
cout << endl << "my_tree's LevelOrder is ";
my_tree.LevelOrder(my_tree.Root()); //层序遍历
cout << endl;
int SearchElement;
cout << "Please input a value you'd like to search in your tree:\n";
cin >> SearchElement; //输入搜索元素
BinaryTreeNode<int> *temp = my_tree.Search(SearchElement,my_tree.Root());
//临时指针储存搜索地址
if(temp) //若为空，则不存在
cout << "Your searchelement is " << temp->value() << endl;
else
cout << "none\n";
return 0;
}
实验结果：
创建一颗二叉树： 5
2 4
7 3
6 9
其先序遍历为：5273694，中序遍历为：7263954，后序遍历为：7693245，层序遍历为：5247369。搜索3，则可找到，搜索6，则不存在。程序运行结果如下图：
相关热词搜索： 实验 报告 二叉树