实验14中序线索二叉树的类定义(2学时,5章)

《实验14中序线索二叉树的类定义(2学时,5章)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、海南大学信息科学技术学院实验报告实验课程:数据结构与算法实验成绩指导教师王平学号:姓名：班级：同组成员：完成日期：2015年12月3日实验14中序线索二叉树的类定义(验证，2学时)(笫05章树)1.建立、中序遍历和输出(P196r208,212^214)术语:删除使Z为空树destroy,利用前序序列和中序序列构造二叉树createBinaryTree,建立小序线索二叉树createlnThread,找子树屮序第一个结点First,找中序后继结点Next,中序遍历InOrder(1)屮序线索三义树的类定义如卜•所N，其'PW7个

2、成员函数待实现，两个成员两数是链式二义树类的成员函数，要做一些修改。〃中序线索二叉树的类定义〃头文件名：p212_ThreadTree.htemplatestructThreadNode{intltag,rtag;//线索标志,非零为线索,Itag前驱,rtag后继ThreadNode*leftChild,*rightChild;Tdata;ThreadNode(constTitem):data(item),leftChild(NULL),rightChild(NULL),ltag(O),rtag(O){}

3、}；templateclassThreadlree{protected:ThreadNode*root;voiddestroy(ThreadNode*&subTree);//p196删除使Z为牢树ThreadNode*createBinaryTree(T*VLR,T*LVR,intn);〃利用前序序夕0和中序序列构造二叉树voidcreatelnThread(ThreadNodevT>*current,ThreadNodevT>*&pre);〃中序遍历建立线索二叉树，递归p214public:T

4、hreadTree():root(NULL){}~ThreadTree(){if(root)destroy(root);}〃析构函数friendistream&operator〉>vT>(istream&in,ThreadTree&BT);〃调用createBinaryTreevoidcreatelnThread();〃建立中序线索二文.树，调用同名保护成员函数p214ThreadNode*First(ThreadNodeCurrent);//找子树屮序笫一个结点p213ThreadNode*Next(T

5、hreadNode*current);//找中序后继结点p213voidlnOrder(void(*vist)(ThreadNode*p));〃中序遍历p214}；〃输入二叉树template〃调用createBinaryTreeistream&operator〉>(istream&in,ThreadTree&BT){if(BT.root!=NULL)BTdestroy(BTroot);//BT是空树或屮序线索二叉树cout<<"输入二叉树的结点个数：”；intn;in>>n;T*VLR=new

6、T[n],*LVR=newT[n];coutvv”输入二叉树的前序序列：for(inti=0;i>VLR[i];coutvv”输入二叉树的中序序列：”;for(inti=0;i>LVR[i];BT.root=BT.createBinaryTree(VLR,LVR,n);〃建立二义树delete[]VLR;delete[]LVR;BT.createlnThread();〃建立线索〔义树returnin;}//(1-1)createBinaryTree利用前序序列和屮序序列构造二叉树P208/

7、/(1-2)destroy删除使Z为空树，修改P196//(1-3)First找子树中序第一个结点两数实现p213//(1-4)Next找中序后继结点函数实现p213//(1-5)lnOrder中序遍历函数实现p214//(1-6)createlnThread建立线索二叉树(public)函数实现p214//(1-7)createlnThread建立线索二叉树(protected)函数实现p214(2)主函数:#includeusingnamespacestd;#includeHp212_ThreadTree

8、.h"templatevoidvisit(ThreadNode*p){cout<data;}voidmain(){ThreadTreeBT;cin>>BT;〃输入前序序列、中序序列、建立二叉树、中序线索化BT.InOrd