《数据结构线索二叉树实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构线索二叉树实验报告.docx（10页珍藏版）》请在三一办公上搜索。
1、数据结构线索二叉树实验报告线索二叉树应用实验 实验报告 实验目的 掌握线索二叉树的有关知识。 掌握求解线索二叉树中结点前趋和后继的算法以及以相应次序遍历线索二叉树的算法。 掌握二叉树的线索化算法的设计。 实验运行环境 Visual C+ 实验任务 线索二叉树是为了快速求解二叉树中结点在指定次序下的前驱和后继，而将二叉链表中空的左右孩子指针分别改为指向其前驱和后继结点而得到的结构，反映了运算对数据结构的设计的影响。因此，首先要了解线索二叉树的结构特点，其中原本为空的指针被修改为前驱和后继指针，使得对左右子树和线索的判断发生了变化。利用线索可以实现某些次序下的前驱和后继。本实验期望能理解线索二叉树
2、的结构特点，实现各前驱和后接算法的求解，并掌握将二叉树转换为线索二叉树的算法，即线索化算法。为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序btrechar.h中的函数的形式给出，并假设该库函数中定义了线索二叉树的相关功能，如显示线索二叉树等。 实验内容 第一题： 按先序次序遍历先序线索二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：将二叉树的根结点的指针传给函数。 2：判断当前结点是否为先序遍历的最后一个结点，若是则访问完该结点后结束，否则进入3。 2：判断当前结点是否有左子树，若有的话访问完
3、该结点后访问它的左子树，否则访问它的右子树，返回2。 第二题： 按中序次序遍历中序线索二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：将二叉树的根结点的指针传给函数。 2：判断当前结点是否为中序遍历的最后一个结点，若是则访问完该结点后结束，否则进入3。 3：对于当前结点，先访问该结点的前驱结点并进入第二步，其次访问该结点并进入第二步最后访问该结点的后继结点并进入2。 第三题： 将值为x的结点作为先序线索二叉树T的左子树的最后一个结点的右孩子插入进去。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据
4、： letter.cbt 实验准备： 1：将先序线索二叉树的根结点的指针传给函数。 2：判断当前结点是否为要找的结点P，若是则建立一个新的结点，将新结点作为P的右孩子，并根据新建的结点修改前驱后继关系，否则进入3。 3：指针指向该结点先序遍历的后继，返回2。 第四题： 按中序次序线索化二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：设立两个指针pre与t分别代表前驱结点与当前结点。 2：按照中序访问的顺序，对于访问到的每一个结点进行如下的操作。 3：判断当前结点是否为空，若是则结束，否则进入第四步。 4：对于当前结点如果
5、它的左孩子为空，则将该结点前驱线索化， 如果它的前驱指针pre指向的结点的右孩子为空，则将pre指向的结点后继线索化， 如果对于当前结点如果它的右孩子为空，则将该结点的rchild置为1，将t赋值给pre。 5：将t指向它在中序中的后继，返回到3。 第五题： 按后序次序线索化二叉树。 实验测试数据基本要求： 第一组数据： full41.cbt 第二组数据： letter.cbt 实验准备： 1：设立两个指针pre与t分别代表前驱结点与当前结点。 2：按照后序访问的顺序，对于访问到的每一个结点进行如下的操作。 3：判断当前结点是否为空，若是则结束，否则进入4。 4：对于当前结点如果它的左孩子为空
6、，则将该结点前驱线索化， 如果它的前驱指针pre指向的结点的右孩子为空，则将pre指向的结点后继线索化， 如果对于当前结点如果它的右孩子为空，则将该结点的rchild置为1，将t赋值给pre。 5：将t指向它在后序中的后继，返回到3。 实验测试数据 实验程序 #include using namespace std; int m; struct tbnode ; tbnode *pre=NULL; /初始化前驱指针 class tbtree public: int height(tbnode *p); void first_tree(tbnode *p); /先序线索化 void second
7、_tree(tbnode *p); /中序线索化 void third_tree(tbnode *p); /后序线索化 void first_first_tree(tbnode *p); /先序编历先序线索化二叉树 void second_second_tree(tbnode *p); /中序编历中序线索化二叉树 tbnode *&get_root return root; tbnode *prepare(tbnode *p) if(p-ltag=0) return p-lchild; tbtree; char data; tbnode *lchild,*rchild; int ltag,rt
8、ag; void prepare_tree(tbnode *&p); /初始化二叉树 else return p-rchild; tbnode* start(tbnode *p) if(p-rtag=1) return p-rchild; else tbnode *q=p-rchild; while(q-ltag!=1) q=q-lchild; return q; private: tbnode *root; ; tbtree:tbtree root = new tbnode ; root = NULL; int tbtree:height(tbnode *p) int ch_1,ch_2;
9、if(p=NULL) return(0); else /求二叉树的高度函数 ch_1=height(p - lchild); ch_2=height(p - rchild); if(ch_1ch_2) return (ch_1+1); else return ch_2; void tbtree:prepare_tree(tbnode *&p) /初始化二叉树 void tbtree:first_tree(tbnode *p) /先序次序线索化二叉树 if(p != NULL) if(p - lchild=NULL) else p -ltag = 0; if(pre != NULL& pre -
10、rtag =1) pre -rchild =p; if(p -rchild =NULL) p - rtag = 1; else p -rtag = 0; p -ltag = 1; p -lchild = pre; char a; cina; if(a = .) p = NULL; else p = new tbnode ; p - data = a; prepare_tree(p - lchild ); prepare_tree(p - rchild ); coutdata; pre = p; if(p -ltag =0) first_tree(p - lchild); if(p -rtag
11、=0) first_tree(p - rchild); void tbtree:second_tree(tbnode *p) /中序次序线索化二叉树 if(p!=NULL) if(pre!=NULL&pre-rtag=1) pre-rchild=p; if(p-lchild=NULL) else p-ltag=0; if(p-rchild=NULL) p-rtag=1; else p-rtag=0; p-lchild=pre; p-ltag=1; second_tree(p-lchild); coutdata; pre=p; if(p-rtag=0) second_tree(p-rchild)
12、; void tbtree:third_tree(tbnode *p) if(p != NULL) third_tree(p - lchild); third_tree(p - rchild); if(pre != NULL & pre - rtag=1) pre - rchild = p; if(p - lchild =NULL) if(p - rchild =NULL) p - rtag = 1; p - ltag =1; p - lchild = pre; else p - rtag = 0; coutdata; pre = p; void tbtree:first_first_tree
13、(tbnode *p) /先序编历先序线索化二叉树 void tbtree:second_second_tree(tbnode *p) /中序编历中序线索化二叉树 int main coutendl; cout数据结构实验四-线索二叉树应用实验endl; coutltag!=1) p=p-lchild; while(p!=NULL) coutdata; p=start(p); while(p!=NULL) coutdata; p=prepare(p); cout第1题: 按先序次序遍历先序线索二叉树endl; cout第2题: 按中序次序遍历中序线索二叉树endl; cout第3题: 将值为x
14、的结点作为先序线索二叉树T的左子树的endl; cout 最后一个结点的右孩子插入进去endl; cout第4题: 按中序次序线索化二叉树endl; cout第5题: 按后序次序线索化二叉树endl; cout退出程序:0endl; coutchoice; switch(choice) case 1: cout此操作是按中序次序遍历先序线索二叉树endl; coutendl; cout输入所建立二叉树的元素endl; cout此操作是按先序次序遍历先序线索二叉树endl; coutendl; cout输入所建立二叉树的元素endl; coutendl; tbnode *p; T.first_t
15、ree(p); coutendl; T.first_first_tree(p); break; cout请选择一道题endl; T.prepare_tree(p); case 2: coutendl; tbnode *p; T.prepare_tree(p); cout此操作是将值为x的结点作为先序线索二叉树cout的左子树的最后一个结点的右孩子插入进去T.second_tree(p); T.second_second_tree(p); break; case 3: Tendl; endl; cout输入所建立二叉树的元素endl; coutendl; tbnode *p; T.prepare
16、_tree(p); cout按中序次序线索化二叉树endl; coutendl; cout输入所建立二叉树的元素endl; tbnode *p; T.second_tree(p); break; T.first_tree(p); T.first_first_tree(p); cout请输入所要插入的值:choice; T.first_first_tree(p); break; case 4: T.prepare_tree(p); case 5: cout输入错误，请重新输入endl; coutEXITendl; break; cout按后序次序线索化二叉树endl; coutendl; cout输入所建立二叉树的元素endl; tbnode *p; T.third_tree(p); break; T.prepare_tree(p); return 0; case 0: default:
