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

1、数据结构与算法实验312王平15实验14 中序线索二叉树的类定义（验证，2学时）（第05章 树）1. 建立、中序遍历和输出（P196,208,212214）术语：删除使之为空树destroy，利用前序序列和中序序列构造二叉树createBinaryTree，建立中序线索二叉树createInThread，找子树中序第一个结点First，找中序后继结点Next，中序遍历InOrder(1) 中序线索二叉树的类定义如下所示，其中有7个成员函数待实现，两个成员函数是链式二叉树类的成员函数，要做一些修改。/中序线索二叉树的类定义/头文件名：p212_ThreadTree.htemplate<cl

2、ass T>struct ThreadNodeint ltag,rtag;/线索标志，非零为线索，ltag前驱，rtag后继ThreadNode<T> *leftChild,*rightChild;T data;ThreadNode(const T item):data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0);template<class T>class ThreadTreeprotected:ThreadNode<T> *root;void destroy(ThreadNode&l

3、t;T> *&subTree);/p196删除使之为空树ThreadNode<T>* createBinaryTree(T *VLR,T *LVR,int n);/利用前序序列和中序序列构造二叉树void createInThread(ThreadNode<T> *current,ThreadNode<T> *&pre);/中序遍历建立线索二叉树，递归p214public:ThreadTree():root(NULL)ThreadTree() if(root) destroy(root); /析构函数friend istream&

4、; operator>><T>(istream&in,ThreadTree<T>& BT);/调用createBinaryTreevoid createInThread();/建立中序线索二叉树，调用同名保护成员函数p214ThreadNode<T> *First(ThreadNode<T> *current);/找子树中序第一个结点p213ThreadNode<T> *Next(ThreadNode<T> *current);/找中序后继结点p213void InOrder(void(*vis

5、t)(ThreadNode<T> *p);/中序遍历p214;/输入二叉树template<class T>/调用createBinaryTreeistream& operator>>(istream& in,ThreadTree<T>& BT)if(BT.root!=NULL) BT.destroy(BT.root);/BT是空树或中序线索二叉树cout<<"输入二叉树的结点个数：" int n; in>>n;T *VLR=new Tn,*LVR=new Tn;cout<

6、<"输入二叉树的前序序列："for(int i=0;i<n;i+) in>>VLRi;cout<<"输入二叉树的中序序列："for(int i=0;i<n;i+) in>>LVRi;BT.root=BT.createBinaryTree(VLR,LVR,n);/建立二叉树deleteVLR; deleteLVR;BT.createInThread();/建立线索二叉树return in;/(1-1)createBinaryTree利用前序序列和中序序列构造二叉树P208/(1-2)destroy删除使

7、之为空树，修改P196/(1-3)First找子树中序第一个结点函数实现p213/(1-4)Next找中序后继结点函数实现p213/(1-5)InOrder中序遍历函数实现p214/(1-6)createInThread建立线索二叉树(public)函数实现p214/(1-7)createInThread建立线索二叉树(protected)函数实现p214(2) 主函数：#include<iostream>using namespace std;#include"p212_ThreadTree.h"template<class T>void visi

8、t(ThreadNode<T>* p) cout<<p->data; void main()ThreadTree<char> BT;cin>>BT;/输入前序序列、中序序列、建立二叉树、中序线索化BT.InOrder(visit);/中序输出cout<<endl;() 给出实现的7个成员函数。/(1-1)createBinaryTree利用前序序列和中序序列构造二叉树P208template<class T>ThreadNode<T>* ThreadTree<T>:createBinaryTr

9、ee(T *VLR,T *LVR,int n)if(n=0)return NULL;int k=0;while(VLR0!=LVRk)k+;ThreadNode<T> *t=new ThreadNode<T>(VLR0);t->leftChild=createBinaryTree(VLR+1,LVR,k);t->rightChild=createBinaryTree(VLR+k+1,LVR+k+1,n-k-1);return t;/(1-2)destroy删除使之为空树，修改P196template<class T>void ThreadTree

10、<T>:destroy(ThreadNode<T>*&subTree)if(subTree!=NULL)if(subTree->ltag=0) destroy(subTree->leftChild);if(subTree->rtag=0) destroy(subTree->rightChild);delete subTree;subTree=NULL;/(1-3)First找子树中序第一个结点函数实现p213template<class T>ThreadNode<T> *ThreadTree<T>:Fi

11、rst(ThreadNode<T> *current)ThreadNode<T> *p=current;while(p->ltag=0)p=p->leftChild;return p;/(1-4)Next找中序后继结点函数实现p213template<class T>ThreadNode<T> *ThreadTree<T>:Next(ThreadNode<T> *current)ThreadNode<T> *p=current->rightChild;if(current->rtag=0

12、)return First(p);else return p;/(1-5)InOrder中序遍历函数实现p214template<class T>void ThreadTree<T>:InOrder(void(*visit)(ThreadNode<T> *p)ThreadNode<T> *p;for(p=First(root);p!=NULL;p=Next(p)visit(p);/(1-6)createInThread建立线索二叉树(public)函数实现p214template<class T>void ThreadTree<

13、T>:createInThread()ThreadNode<T>*pre=NULL;if(root!=NULL)createInThread(root,pre);pre->rightChild=NULL;pre->rtag=1;/(1-7)createInThread建立线索二叉树(protected)函数实现p214template<class T>void ThreadTree<T>:createInThread(ThreadNode<T> *current,ThreadNode<T> *&pre)if(

14、current=NULL)return;createInThread(current->leftChild,pre);if(current->leftChild=NULL)current->leftChild=pre;current->ltag=1;if(pre!=NULL&&pre->rightChild=NULL)pre->rightChild=current;pre->rtag=1;pre=current;createInThread(current->rightChild,pre);() 给出下面的二叉树的运行结果。ABI

15、CEJMDK2. 前序和后序遍历（P212216）术语：获取根结点getRoot，找子树中序最后一个结点Last，找中序前驱结点Prior，前序遍历PreOrder，后序遍历PostOrder，求父结点parent(1) 在上题中增加了6个成员函数，其中5个成员待实现。/中序线索二叉树的类定义/头文件名：p212_ThreadTree.htemplate<class T>struct ThreadNodeint ltag,rtag;/线索标志，非零为线索，ltag前驱，rtag后继ThreadNode<T> *leftChild,*rightChild;T data;T

16、hreadNode(const T item):data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0);template<class T>class ThreadTreeprotected:ThreadNode<T> *root;void destroy(ThreadNode<T> *&subTree);/p196删除使之为空树ThreadNode<T>* createBinaryTree(T *VLR,T *LVR,int n);/利用前序序列和中序序列构造二叉树void

17、createInThread(ThreadNode<T> *current,ThreadNode<T> *&pre);/中序遍历建立线索二叉树，递归p214public:ThreadTree():root(NULL)ThreadTree() if(root) destroy(root); /析构函数friend istream& operator>><T>(istream&in,ThreadTree<T>& BT);/调用createBinaryTreevoid createInThread();/建立

18、中序线索二叉树，调用同名保护成员函数p214ThreadNode<T> *First(ThreadNode<T> *current);/找子树中序第一个结点p213ThreadNode<T> *Next(ThreadNode<T> *current);/找中序后继结点p213void InOrder(void(*vist)(ThreadNode<T> *p);/中序遍历p214ThreadNode<T>* getRoot() return root; ThreadNode<T> *Last(ThreadNode

19、<T> *current);/找子树最后一个结点p213ThreadNode<T> *Prior(ThreadNode<T> *current);/找前驱结点p213void PreOrder(void(*vist)(ThreadNode<T> *p);/前序遍历p214215void PostOrder(void(*vist)(ThreadNode<T> *p);/后序遍历p215ThreadNode<T>* parent(ThreadNode<T> *t);/求父结点p216;/输入二叉树template&

20、lt;class T>/调用createBinaryTreeistream& operator>>(istream& in,ThreadTree<T>& BT)if(BT.root!=NULL) BT.destroy(BT.root);/BT是空树或中序线索二叉树cout<<"输入二叉树的结点个数：" int n; in>>n;T *VLR=new Tn,*LVR=new Tn;cout<<"输入二叉树的前序序列："for(int i=0;i<n;i+) in

21、>>VLRi;cout<<"输入二叉树的中序序列："for(int i=0;i<n;i+) in>>LVRi;BT.root=BT.createBinaryTree(VLR,LVR,n);/建立二叉树deleteVLR; deleteLVR;BT.createInThread();/建立线索二叉树return in;/上题的友元函数和成员函数复制到此处。/(2-1)Last找子树中序最后一个结点函数实现p213/(2-2)Prior找中序前驱结点函数实现p213/(2-3)PreOrder前序遍历函数实现p214215/(2-4)P

22、ostOrder后序遍历函数实现p215/(2-5)parent求父结点函数实现p216(2) 主函数：#include<iostream>using namespace std;#include"p212_ThreadTree.h"template<class T>void visit(ThreadNode<T>* p) cout<<p->data; void main()ThreadTree<char> BT;cin>>BT;ThreadNode<char> *p;for(p=BT

23、.Last(BT.getRoot();p!=NULL;p=BT.Prior(p)cout<<"当前结点"<<p->data<<" 父结点"if(BT.parent(p)=NULL) cout<<"无"<<endl;else cout<<BT.parent(p)->data<<endl;cout<<"前序遍历：" BT.PreOrder(visit);cout<<endl;cout<<&

24、quot;后序遍历：" BT.PostOrder(visit);cout<<endl;() 给出实现的5个成员函数。/(2-1)Last找子树中序最后一个结点函数实现p213template<class T>ThreadNode<T> * ThreadTree<T>:Last(ThreadNode<T>*current)ThreadNode<T>*p=current;while(p->rtag=0)p=p->rightChild;return p;/(2-2)Prior找中序前驱结点函数实现p213t

25、emplate<class T>ThreadNode<T>*ThreadTree<T>:Prior(ThreadNode<T>*current)ThreadNode<T>*p=current->leftChild;if(current->ltag=0)return Last(p);else return p;/(2-3)PreOrder前序遍历函数实现p214215template<class T>void ThreadTree<T>:PreOrder(void(*visit)(ThreadNode

26、<T>*p)ThreadNode<T>*p=root;while(p!=NULL)visit(p);if(p->ltag=0)p=p->leftChild;else if(p->rtag=0)p=p->rightChild;elsewhile(p!=NULL&&p->rtag=1)p=p->rightChild;if(p!=NULL)p=p->rightChild;/(2-4)PostOrder后序遍历函数实现p215template<class T>void ThreadTree<T>:

27、PostOrder(void(*visit)(ThreadNode<T>*p)ThreadNode<T>*t=root;while(t->ltag=0|t->rtag=0)if(t->ltag=0)t=t->leftChild;else if(t->rtag=0)t=t->rightChild;visit(t);ThreadNode<T>*p;while(p=parent(t)!=NULL)if(p->rightChild=t|p->rtag=1)t=p;elset=p->rightChild;while

28、(t->ltag=0|t->rtag=0)if(t->ltag=0)t=t->leftChild;else if(t->rtag=0)t=t->rightChild;visit(t);/(2-5)parent求父结点函数实现p216template<class T>ThreadNode<T>*ThreadTree<T>:parent(ThreadNode<T>*t)ThreadNode<T>*p;if(t=root)return NULL;for(p=t;p->ltag=0;p=p->l

29、eftChild);if(p->leftChild!=NULL)for(p=p->leftChild;p!=NULL&&p->leftChild!=t&&p->rightChild!=t;p=p->rightChild);if(p=NULL|p->leftChild=NULL)for(p=t;p->rtag=0;p=p->rightChild);for(p=p->rightChild;p!=NULL&&p->leftChild!=t&&p->rightChild!=

30、t;p=p->leftChild);return p;() 给出下面的二叉树的运行结果。A B D E J I C K M 3. 插入和删除（P212，216218）术语：插入为右子女InsertRight，删除右子女DeleteRight(1) 在上题中增加了2个成员函数，都是公有类型成员函数。插入为右子女成员函数原型：void InsertRight(ThreadNode<T> *s,ThreadNode<T> *r);/(3-1) 插入为右子女删除右子女成员函数原型：ThreadNode<T>* DeleteRight(ThreadNode<

31、;T> *s);/(3-2) 删除右子女(2) 主函数。#include<iostream>using namespace std;#include"p212_ThreadTree.h"template<class T>void visit(ThreadNode<T>* p) cout<<p->data; void main()ThreadTree<char> BT;cin>>BT;ThreadNode<char> *s,*r; int i,j;cout<<"t 删除后 前序和中序遍历tt 插入后 前序和中序遍历"<<endl;for(i=1;i<=9;i+)s=BT.First(BT.getRoot();for(j=1;j<i;j+,s=B