二叉树实验报告二叉树实验报告总结.docx
《二叉树实验报告二叉树实验报告总结.docx》由会员分享，可在线阅读，更多相关《二叉树实验报告二叉树实验报告总结.docx（18页珍藏版）》请在冰点文库上搜索。
二叉树实验报告二叉树实验报告总结
[二叉树实验报告]二叉树实验报告总结
题目：
编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。
算法描述：
首先创建二叉树结点类，其主要包括：
二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。
然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：
构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。
接下来将对一些重要函数算法进行描述：
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所指结点的右子树不为空，则右子树根结点指针入队，结束。
先序遍历，后序遍历思想与中序遍历一致，这里不再一一分析。
最后创建一颗二叉树，用以检验各函数的功能。
源程序：
#includeiostream
#includestack
#includequeue
#includecstdlib
usingnamespacestd;
templateclassT
classBinaryTree;
templateclassT
classBinaryTreeNode{
friendclassBinaryTreeT
//friendclassBinarySearchTreeT
private:
Tdata;//二叉树结点数据域
BinaryTreeNodeT*left;//二叉树结点指向左子树的指针
BinaryTreeNodeT*right;//二叉树结点指向右子树的指针
public:
BinaryTreeNode（）{};//默认构造函数
BinaryTreeNode（constTele）:
left（NULL）,right（NULL）{data=ele;};
//给定数据的构造函数
BinaryTreeNode（constTele,BinaryTreeNodeT*l,BinaryTreeNodeT*r）;
//给定数据的左右指针的构造函数
~BinaryTreeNode（）{};//析构函数
Tvalue（）const{returndata;};//返回当前结点的数据
BinaryTreeNodeToperator=（constBinaryTreeNodeTNode）{this=Node;};
//重载赋值操作符
BinaryTreeNodeT*leftchild（）const{returnleft;};
//返回当前结点指向左子树的指针
BinaryTreeNodeT*rightchild（）const{returnright;};
//返回当前结点指向右子树的指针
voidsetLeftchild（BinaryTreeNodeT*l）{left=l;};
//设置当前结点的左子树
voidsetRightchild（BinaryTreeNodeT*r）{right=r;};
//设置当前结点的右子树
voidsetValue（constTval）{data=val;};
//设置当前结点的数据域
boolisLeaf（）const;//判定当前结点是否为叶子结点，若是则返回true
};
templateclassT
BinaryTreeNodeT:
:
BinaryTreeNode（constTele,BinaryTreeNodeT*l,BinaryTreeNodeT*r）//给定数据的左右指针的构造函数
{
data=ele;
left=l;
right=r;
}
templateclassT
boolBinaryTreeNodeT:
:
isLeaf（）const//判定当前结点是否为叶子结点，若是则返回true
{
if（data-left==NULLdata-right==NULL）//若左子树和右子树都为空，则返回true
returntrue;
else
returnfalse;
}
templateclassT
classBinaryTree
{
protected:
BinaryTreeNodeT*ROOT;//二叉树根结点指针
public:
BinaryTree（）{ROOT=NULL;};//构造函数
BinaryTree（BinaryTreeNodeT*r）{ROOT=r;}
~BinaryTree（）{DeleteBinaryTree（ROOT）;};//析构函数
boolisEmpty（）const;//判断二叉树是否为空树
voidvisit（constTdata）{coutdata“";}//访问当前结点
BinaryTreeNodeT*Root（）{returnROOT;};//返回二叉树的根结点
BinaryTreeNodeT*Parent（BinaryTreeNodeT*current）;
//返回当前结点的双亲结点
voidParent_PreOrder（BinaryTreeNodeT*curroot,BinaryTreeNodeT*r,BinaryTreeNodeT*//运用先序遍历的思想查找双亲
BinaryTreeNodeT*LeftSibling（BinaryTreeNodeT*current）;
//返回当前结点的左兄弟
BinaryTreeNodeT*RightSibling（BinaryTreeNodeT*current）;
//返回当前结点的右兄弟
voidCreateTree（BinaryTreeNodeT*//根据先序遍历序列构造二叉树
voidDeleteBinaryTree（BinaryTreeNodeT*root）;//删除二叉树或其子树
voidPreOrder（BinaryTreeNodeT*root）;//先序遍历二叉树或其子树
voidInOrder（BinaryTreeNodeT*root）;//中序遍历二叉树或其子树
voidPostOrder（BinaryTreeNodeT*root）;//后序遍历二叉树或其子树
voidPreOrderWithoutRecusion（BinaryTreeNodeT*root）;
//非递归先序遍历二叉树或其子树
voidInOrderWithoutRecusion（BinaryTreeNodeT*root）;
//非递归中序遍历二叉树或其子树
voidPostOrderWithoutRecusion（BinaryTreeNodeT*root）;
//非递归后序遍历二叉树或其子树
voidLevelOrder（BinaryTreeNodeT*root）;//按层序遍历二叉树或其子树
BinaryTreeNodeT*Search（Tt,BinaryTreeNodeT*r）;//二叉树搜索
voidSearch_PreOrder（Tt,BinaryTreeNodeT*r,BinaryTreeNodeT*temp）;
//运用先序遍历的思想查找给定数据所在结点
};
templateclassT
boolBinaryTreeT:
:
isEmpty（）const//判断二叉树是否为空树
{
if（ROOT==NULL）//若根结点为空，则返回true
returntrue;
else
returnfalse;
}
templateclassT
BinaryTreeNodeT*BinaryTreeT:
:
Parent（BinaryTreeNodeT*current）
//返回当前结点的双亲结点
{
if（!
current||!
ROOT||current==ROOT）
//若当前结点不存在或根结点为空或当前结点为根结点，则输出error且跳出函数
{
cout"Error\n";
exit（0）;
}
BinaryTreeNodeT*temp=NULL;//初始化临时指针，temp用于保存最后查找到的双亲结点的地址
Parent_PreOrder（ROOT,current,temp）;//查找双亲的子程序
if（!
temp）//结点不在树中，则双亲不存在
{
cout"Yournodedoesn'tbelongtothistree!
\n";
exit（0）;
}
returntemp;
}
templateclassT
voidBinaryTreeT:
:
Parent_PreOrder（BinaryTreeNodeT*curroot,BinaryTreeNodeT*r,BinaryTreeNodeT*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）;//在右子树中查找
}
}
templateclassT
BinaryTreeNodeT*BinaryTreeT:
:
LeftSibling（BinaryTreeNodeT*current）
//返回当前结点的左兄弟
{
BinaryTreeNodeT*temp=Parent（current）;//先找到给定结点的双亲
if（!
temp-left||current==temp-left）
//双亲的左孩子若不是结点本身，则是结点的左兄弟
{
cout"Thisnodedoesn'thavealeftsibling!
\n";
exit（0）;
}
returntemp-left;
}
templateclassT
BinaryTreeNodeT*BinaryTreeT:
:
RightSibling（BinaryTreeNodeT*current）
//返回当前结点的右兄弟
{
BinaryTreeNodeT*temp=Parent（current）;//先找到给定结点的双亲
if（!
temp-right||current==temp-right）
//双亲的右孩子若不是结点本身，则是结点的右兄弟
{
cout"Thisnodedoesn'thavearightsibling!
\n";
exit（0）;
}
returntemp-right;
}
templateclassT
voidBinaryTreeT:
:
DeleteBinaryTree（BinaryTreeNodeT*root）//删除二叉树或其子树
{
if（root==NULL）return;//判断是否为空树，若为空，则返回
DeleteBinaryTree（root-left）;//递归删除左子树
DeleteBinaryTree（root-right）;//递归删除右子树
deleteroot;//删除根结点
cout"Onenodedeleted!
\n";
root=NULL;//根结点置为空
}
templateclassT
voidBinaryTreeT:
:
PreOrder（BinaryTreeNodeT*root）//先序遍历二叉树或其子树
{
if（root==NULL）//判断是否为空树，若为空，则返回
return;
visit（root-value（））;//访问根结点
PreOrder（root-leftchild（））;//先序遍历左子树
PreOrder（root-rightchild（））;//先序遍历右子树
}
templateclassT
voidBinaryTreeT:
:
PreOrderWithoutRecusion（BinaryTreeNodeT*root）
//非递归先序遍历二叉树或其子树
{
stackBinaryTreeNodeT*tStack;
BinaryTreeNodeT*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（）;//指向右孩子
}
}
}
templateclassT
voidBinaryTreeT:
:
InOrder（BinaryTreeNodeT*root）//中序遍历二叉树或其子树
{
if（root==NULL）//判断是否为空树，若为空，则返回
return;
InOrder（root-leftchild（））;//中序遍历左子树
visit（root-value（））;//访问根结点
InOrder（root-rightchild（））;//中序遍历右子树
}
templateclassT
voidBinaryTreeT:
:
InOrderWithoutRecusion（BinaryTreeNodeT*root）
//非递归中序遍历二叉树或其子树
{
stackBinaryTreeNodeT*tStack;
BinaryTreeNodeT*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（）;//栈顶元素出栈
}
}
}
templateclassT
voidBinaryTreeT:
:
PostOrder（BinaryTreeNodeT*root）//后序遍历二叉树或其子树
{
if（root==NULL）//判断是否为空树，若为空，则返回
return;
PostOrder（root-leftchild（））;//后序遍历左子树
PostOrder（root-rightchild（））;//后序遍历右子树
visit（root-value（））;//访问根结点
}
enumTag{L,R};
templateclassT
classStackNode{
public:
BinaryTreeNodeT*pointer;
Tagtag;
};
templateclassT
voidBinaryTreeT:
:
PostOrderWithoutRecusion（BinaryTreeNodeT*root）
//非递归后序遍历二叉树或其子树
{
stackStackNodeTtStack;
StackNodeTNode;
BinaryTreeNodeT*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）;
}
templateclassT
voidBinaryTreeT:
:
CreateTree（BinaryTreeNodeT*r）//根据先序遍历序列构造二叉树
{
intch;
cinch;
if（ch==0）
r=NULL;
else{//读入非0数
r=newBinaryTreeNodeT（ch）;//生成结点
CreateTree（r-left）;//构造左子树
CreateTree（r-right）;//构造右子树
}
}
templateclassT
voidBinaryTreeT:
:
LevelOrder（BinaryTreeNodeT*root）//按层序遍历二叉树或其子树
{
queueBinaryTreeNodeT*tQueue;
BinaryTreeNodeT*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（））;//右子树入队列
}
}
templateclassT
BinaryTreeNodeT*BinaryTreeT:
:
Search（Tt,BinaryTreeNodeT*root）//二叉树搜索
{
if（isEmpty（））//判断是否为空，若为空树，则跳出函数
{
cout"Thetreeise
升级会员 