二叉树实验报告

1、题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。算法描述：首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述：1、 isleaf函数：若该结点的左子树和右子树都为空，则为叶子结点。2、 isempty函数：根结点为空则为空树。3

2、、 parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。4、 leftsibling（rightsibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。5、 deletebinarytree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。6

3、、 preorder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。7、preorderwithoutrecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。8、createtree函数：采用先序遍历序列构造二叉树，设0为空结点，输入非0数

4、，生成新结点，递归创建左子树和右子树。9、search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在结点的指针。如果当前结点为空，则返回；否则判断当前结点是否为目标结点，如果是，记住结点位置，返回；否则，递归地在左子树中查找，如果找到，记住结点位置，返回；否则，递归地在右子树中查找。判断temp是否为空，若为空，则未查找到给定元素。10、levelorder函数：利用队列记录二叉树每一层，首先申请队列，申请指针pointer保存根结点，然后判断pointer是否为空，若不为空，则poin

5、ter入队。如果队列为空，跳出函数。队列首元素出队，赋给pointer，访问pointer所指结点，如果pointer所指结点的左子树不为空，则左子树根结点指针入队；如果pointer所指结点的右子树不为空，则右子树根结点指针入队，结束。先序遍历，后序遍历思想与中序遍历一致，这里不再一一分析。最后创建一颗二叉树，用以检验各函数的功能。源程序：#include#include#include#include using namespace std;template class binarytree;template class binarytreenodefriend class binaryt

6、ree;/friend class binarysearchtree;private:t data;/二叉树结点数据域 binarytreenode * left; /二叉树结点指向左子树的指针 binarytreenode * right;/二叉树结点指向右子树的指针 public: binarytreenode();/默认构造函数 binarytreenode(const t& ele) :left(null), right(null) data = ele;/给定数据的构造函数 binarytreenode(const t& ele,binarytreenode * l,binarytr

7、eenode * r);/给定数据的左右指针的构造函数 binarytreenode();/析构函数 t value() constreturn data;/返回当前结点的数据 binarytreenode&operator=(const binarytreenode&node)this=node;/重载赋值操作符 binarytreenode * leftchild() constreturn left;/返回当前结点指向左子树的指针 binarytreenode * rightchild() constreturn right;/返回当前结点指向右子树的指针 void setleftchi

8、ld(binarytreenode * l)left = l;/设置当前结点的左子树 void setrightchild(binarytreenode * r)right = r;/设置当前结点的右子树 void setvalue(const t& val)data = val;/设置当前结点的数据域 bool isleaf() const; /判定当前结点是否为叶子结点，若是则返回true ;template binarytreenode:binarytreenode(const t& ele,binarytreenode * l,binarytreenode * r)/给定数据的左右指针

9、的构造函数data = ele;left = l;right = r;template bool binarytreenode:isleaf() const/判定当前结点是否为叶子结点，若是则返回trueif(data-left = null & data-right = null)/若左子树和右子树都为空，则返回true return true;else return false;template class binarytreeprotected:binarytreenode * root;/二叉树根结点指针 public:binarytree()root=null;/构造函数 binar

10、ytree(binarytreenode * r)root = r;binarytree()deletebinarytree(root);/析构函数 bool isempty() const;/判断二叉树是否为空树 void visit(const t& data)cout data ;/访问当前结点 binarytreenode * & root()return root;/返回二叉树的根结点 binarytreenode * parent(binarytreenode * current);/返回当前结点的双亲结点void parent_preorder(binarytreenode *c

11、urroot,binarytreenode *r,binarytreenode *&t);/运用先序遍历的思想查找双亲binarytreenode * leftsibling(binarytreenode * current);/返回当前结点的左兄弟 binarytreenode * rightsibling(binarytreenode * current);/返回当前结点的右兄弟 void createtree(binarytreenode * &r);/根据先序遍历序列构造二叉树 void deletebinarytree(binarytreenode * root);/删除二叉树或其子

12、树 void preorder(binarytreenode * root);/先序遍历二叉树或其子树 void inorder(binarytreenode * root);/中序遍历二叉树或其子树 void postorder(binarytreenode * root);/后序遍历二叉树或其子树 void preorderwithoutrecusion(binarytreenode * root);/非递归先序遍历二叉树或其子树 void inorderwithoutrecusion(binarytreenode * root);/非递归中序遍历二叉树或其子树 void postorde

13、rwithoutrecusion(binarytreenode * root);/非递归后序遍历二叉树或其子树 void levelorder(binarytreenode * root);/按层序遍历二叉树或其子树 binarytreenode * search( t &t, binarytreenode *r );/二叉树搜索 void search_preorder( t &t, binarytreenode *r, binarytreenode *&temp );/运用先序遍历的思想查找给定数据所在结点;template bool binarytree:isempty() const/

14、判断二叉树是否为空树 if(root = null)/若根结点为空，则返回true return true;else return false;template binarytreenode * binarytree:parent( binarytreenode *current ) /返回当前结点的双亲结点 if( !current | !root | current = root )/若当前结点不存在或根结点为空或当前结点为根结点 ，则输出error且跳出函数 cout errorn;exit(0);binarytreenode *temp = null;/初始化临时指针，temp用于保存

15、最后查找到的双亲结点的地址 parent_preorder( root, current, temp );/查找双亲的子程序 if(!temp)/结点不在树中，则双亲不存在 cout your node doesnt belong to this tree!n;exit(0);return temp;template void binarytree:parent_preorder( binarytreenode *curroot,binarytreenode *r, binarytreenode *&t )/运用递归实现先序遍历，在遍历过程中判断是否找到双亲节点 if( !curroot |

16、curroot-isleaf() ) return;/当前结点为空或叶子结点 if( r = curroot-left | r = curroot-right )/判断双亲结点的条件 t = curroot;/t是对temp的引用，在此修改temp的值 return;elseparent_preorder( curroot-left, r, t );/在左子树中查找 if( t ) return; /如果已在左子树中找到，便不必在右子树中查找 parent_preorder( curroot-right, r, t );/ 在右子树中查找 template binarytreenode * b

17、inarytree:leftsibling( binarytreenode *current )/返回当前结点的左兄弟 binarytreenode *temp = parent(current);/先找到给定结点的双亲 if( !temp-left | current = temp-left )/双亲的左孩子若不是结点本身，则是结点的左兄弟cout left;template binarytreenode * binarytree:rightsibling( binarytreenode *current )/返回当前结点的右兄弟 binarytreenode *temp = parent(

18、current);/先找到给定结点的双亲if( !temp-right | current = temp-right )/双亲的右孩子若不是结点本身，则是结点的右兄弟cout right;template void binarytree:deletebinarytree(binarytreenode * root)/删除二叉树或其子树 if(root = null) return;/判断是否为空树，若为空，则返回 deletebinarytree( root-left );/递归删除左子树 deletebinarytree( root-right );/递归删除右子树 delete root;

19、/删除根结点 cout one node deleted!n;root = null;/根结点置为空 template void binarytree:preorder(binarytreenode * root)/先序遍历二叉树或其子树 if(root = null)/判断是否为空树，若为空，则返回 return;visit(root-value();/访问根结点 preorder(root-leftchild();/先序遍历左子树 preorder(root-rightchild();/先序遍历右子树 template void binarytree:preorderwithoutrecu

20、sion(binarytreenode * root)/非递归先序遍历二叉树或其子树 stack binarytreenode * tstack;binarytreenode * pointer = root;/保存输入参数 while(!tstack.empty()|pointer)if(pointer)visit(pointer-value();/访问当前结点 tstack.push(pointer);/当前结点地址入栈 pointer = pointer-leftchild();/当前链接结构指向左孩子 else/左子树访问完毕，转向访问右子树 pointer = tstack.top(

21、);/当前链接结构指向栈顶的元素 tstack.pop();/栈顶元素出栈 pointer = pointer-rightchild();/指向右孩子 template void binarytree:inorder(binarytreenode * root)/中序遍历二叉树或其子树 if(root = null)/判断是否为空树，若为空，则返回 return;inorder(root-leftchild();/中序遍历左子树visit(root-value();/访问根结点 inorder(root-rightchild();/中序遍历右子树template void binarytree

22、:inorderwithoutrecusion(binarytreenode * root)/非递归中序遍历二叉树或其子树stack binarytreenode * tstack;binarytreenode * pointer = root;while(!tstack.empty()|pointer)if(pointer)tstack.push(pointer);/当前结点地址入栈 pointer = pointer-leftchild(); /当前链接结构指向左孩子 else/左子树访问完毕，转向访问右子树pointer = tstack.top();/当前链接结构指向栈顶的元素visi

23、t(pointer-value();/访问当前结点pointer = pointer-rightchild();/指向右孩子tstack.pop();/栈顶元素出栈template void binarytree:postorder(binarytreenode * root)/后序遍历二叉树或其子树 if(root = null)/判断是否为空树，若为空，则返回 return;postorder(root-leftchild();/后序遍历左子树 postorder(root-rightchild();/后序遍历右子树 visit(root-value();/访问根结点 enum tagl,

24、r;template class stacknodepublic:binarytreenode * pointer;tag tag;template void binarytree:postorderwithoutrecusion(binarytreenode * root)/非递归后序遍历二叉树或其子树 stack stacknode tstack;stacknodenode;binarytreenode * pointer = root;dowhile(pointer != null)/将左子树中的结点加tag=l后压入栈中 node.pointer = pointer;node.tag

25、= 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

26、(!tstack.empty()|pointer);template void binarytree:createtree(binarytreenode * &r) /根据先序遍历序列构造二叉树 int ch;cin ch;if(ch = 0) r = null;else/读入非0数 r = new binarytreenode(ch);/生成结点 createtree(r-left);/构造左子树 createtree(r-right);/构造右子树 template void binarytree:levelorder(binarytreenode * root)/按层序遍历二叉树或其子树

27、queue binarytreenode * tqueue;binarytreenode * 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-rightch

28、ild() != null) tqueue.push(pointer-rightchild();/右子树入队列 template binarytreenode * binarytree:search( t &t, binarytreenode *root ) /二叉树搜索 if( isempty() )/判断是否为空，若为空树，则跳出函数 cout the tree is empty!n;exit(0);binarytreenode *temp = null;/初始化临时指针，temp用于保存最后查找到的结点地址search_preorder( t, root, temp );if( !tem

29、p ) /未查找到对应结点，将返回nullcout t doesnt exist in the tree!n;return temp;template void binarytree:search_preorder( t &t, binarytreenode *root, binarytreenode *&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 m