数据结构C学习.pptx

《数据结构C学习.pptx》由会员分享，可在线阅读，更多相关《数据结构C学习.pptx（137页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/25树 -树的定义和术语 两种树：自由树与有根有序树。自由树：一棵自由树Tf可定义为一个二元组Tf=(V,E)，其中V=v1,.,vn是由n(n0)个元素组成的有限非空集合，称为顶点（vertex）集合。E=(vi,vj)|vi,vjV,1 i,jn是n-1个序对的集合，称为边集合，E中的元素(vi,vj）称为边（edge）或分支。第1页/共137页2023/3/25树 -树的定义和术语 有根树：一棵有根树T，简称为树，它是n(n0)个结点的有限集合。当n=0时，T称为空树；否则，T是非空树，记作其中，r是一个特定的称为根(root)的结点，它没有直接前驱；根以外的其他结点划分为

2、m(m0)个互不相交的有限集合T1,T2,Tm，每个集合又是一棵树，并且称之为根的子树。第2页/共137页2023/3/25树 -树的定义和术语 相关术语子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。第3页/共137页2023/3/25树 -树的定义和术语 叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都是该

3、结点的子孙。结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以此类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。第4页/共137页2023/3/25树 -树的定义和术语 高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。有序树：树中结点的各棵子树T0,T1,是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m0）棵树的集合。第5页/共137页2023/3/25树 -树的抽象数据类型template class Tree/在类界

4、面中的 position 是树中结点的地址。在顺序/存储方式下是下标型,在链表存储方式下是指针型public:Tree();Tree();positionRoot();BuildRoot(constT&value);/建立树的根结点第6页/共137页2023/3/25树 -树的抽象数据类型positionFirstChild(positionp);/返回p第一个子女地址,无子女返回0positionNextSibling(positionp);/返回p 下一兄弟地址,若无下一兄弟返回0positionParent(positionp);/返回 p 双亲结点地址,若 p 为根返回0TgetDat

5、a(positionp);/返回结点 p 中存放的值boolInsertChild(constpositionp,constT&value);/在结点 p 下插入值为 value 的新子女,若插 /入失败,函数返回false,否则返回true第7页/共137页2023/3/25树 -树的抽象数据类型boolDeleteChild(positionp,inti);/删除结点p的第 i个子女及其全部子孙结/点,若删除失败,则返回false,否则返回truevoidDeleteSubTree(positiont);/删除以t为根结点的子树 bool IsEmpty();/判树空否,若空则返回true

6、,否则返回falsevoidTraversal(void(*visit)(positionp);/遍历以 p为根的子树;第8页/共137页2023/3/25二叉树-二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。第9页/共137页2023/3/25二叉树-二叉树的性质 性质1若二叉树结点的层次从1开始,则在二叉树的第i(i1)层最多有2i-1个结点。证明用数学归纳法性质2深度为k(k0)的二叉树最少有k个结点，最多有2k-1个结点。证明：因为每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质

7、1用求等比级数前k项和的公式20+21+22+2k-1=2k-1第10页/共137页2023/3/25二叉树-二叉树的性质 性质3对任何一棵二叉树，如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0n21证明：若设度为1的结点有n1个，总结点数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2,e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1则n2=n0-1n0=n2+1第11页/共137页2023/3/25二叉树-二叉树的性质 定义1 满二叉树(FullBinaryTree)：深度为k的满二叉树是有2k-1个结点的二叉树。定义2 完全二叉树(CompleteB

8、inaryTree)：若设二叉树的深度为k，则共有k层。除第k层外，其它各层(1k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。第12页/共137页2023/3/25二叉树-二叉树的性质 性质4 具有n(n0)个结点的完全二叉树的深度为log2(n+1)。证明：设完全二叉树的深度为k，则有2k-1-1n2k-1即2k-1n+12k，取对数k-11,则i的双亲为 i2；3)若2*i=n,则i的左子女为2*i；4)若2*i+1=n,则i的右子女为2*i+1；5)若i为奇数,且i!=1,则其左兄弟为i-1；6)若i为偶数,且i!=n,则其右兄弟为i+1；7)结点i所在

9、的层次为 log2i+1第14页/共137页2023/3/25二叉树-二叉树的抽象数据类型template class BinaryTreepublic:BinaryTree();/构造函数 BinaryTree(BinTreeNode *lch,BinTreeNode*rch,Titem);/构造函数,以item为根,lch和rch为左、/右子树构造一棵二叉树 int Height();/求树深度或高度 int Size();/求树中结点个数第15页/共137页2023/3/25二叉树-二叉树的抽象数据类型bool IsEmpty();/判二叉树空否？BinTreeNode*Parent(B

10、inTreeNode *current);/求结点current的双亲 BinTreeNode*LeftChild(BinTreeNode*current);/求结点current的左子女 BinTreeNode*RightChild(BinTreeNode *current);/求结点current的右子女 bool Insert(Titem);/在树中插入新元素 bool Remove(Titem);/在树中删除元素 bool Find(constT&item)const;/判断item是否在树中第16页/共137页2023/3/25二叉树-二叉树的抽象数据类型bool getData(c

11、onstT&item)const;/取得结点数据BinTreeNode*getRoot()const;/取根void preOrder(void(*visit)(BinTreeNode *p);/前序遍历,visit是访问函数void inOrder(void(*visit)(BinTreeNode *p);/中序遍历,visit是访问函数void postOrder(void(*visit)(BinTreeNode *p);/后序遍历,(*visit)是访问函数voidlevelOrder(void(*visit)(BinTreeNode*p);/层次序遍历,visit是访问函数;第17页/

12、共137页2023/3/25二叉树-二叉树的数组存储表示 第18页/共137页2023/3/25二叉树-二叉树的链表存储表示 二叉链表和三叉链表的概念二叉树结点定义：每个结点有3个域，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针。二叉链表如下图所示：第19页/共137页2023/3/25二叉树-二叉树的链表存储表示 每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。第20页/共137页2023/3/25二叉树-二叉树的链表存储表示 整个二叉树的链表有一个表头指针，他指向二叉树的根结点。在含有n个结点的二叉链表中有n+1个空链指

13、针域，三叉链表则有n+2个空链指针域。2n-(n-1)=n+1n+1+1=n+2第21页/共137页2023/3/25二叉树-二叉树的链表存储表示 二叉树的链表表示第22页/共137页2023/3/25二叉树-二叉链表的类定义 template struct BinTreeNode/二叉树结点类定义 T data;/数据域 BinTreeNode*leftChild,*rightChild;/左子女、右子女链域 BinTreeNode():leftChild(NULL),rightChild(NULL)/构造函数 BinTreeNode(Tx,BinTreeNode*l=NULL,BinTre

14、eNode*r=NULL)data=x;leftChild=l;rightChild=r;第23页/共137页2023/3/25二叉树-二叉链表的类定义 template class BinaryTree/二叉树类定义public:BinaryTree():root(NULL)/构造函数 BinaryTree(Tvalue):RefValue(value),root(NULL)/构造函数 BinaryTree(BinaryTree&s);/复制构造函数 BinaryTree()destroy(root);/析构函数第24页/共137页2023/3/25二叉树-二叉链表的类定义 bool IsE

15、mpty()return root=NULL;/判二叉树空否BinTreeNode*Parent(BinTreeNode *current)/返回双亲结点 return(root=NULL|root=current)?NULL:Parent(root,t);BinTreeNode*LeftChild(BinTreeNode*current)/返回左子女 return(current!=NULL)?current-leftChild:NULL;第25页/共137页2023/3/25二叉树-二叉链表的类定义 BinTreeNode*RightChild(BinTreeNode*current)/返

16、回右子女return(current!=NULL)？current-rightChild:NULL;int Height()return Height(root);/求树高度int Size()return Size(root);/求结点数BinTreeNode*getRoot()const returnroot;/取根voidpreOrder(void(*visit)(BinTreeNode*p)preOrder(root,visit);/前序遍历第26页/共137页2023/3/25二叉树-二叉链表的类定义 voidinOrder(void(*visit)(BinTreeNode*p)in

17、Order(root,visit);/中序遍历voidpostOrder(void(*visit)(BinTreeNode*p)postOrder(root,visit);/后序遍历voidlevelOrder(void(*visit)(BinTreeNode*p);/层次序遍历int Insert(const Titem);/插入新元素BinTreeNode*Find(T item)const;/搜索第27页/共137页2023/3/25二叉树-二叉链表的类定义 protected:BinTreeNode*root;/二叉树的根指针 TRefValue;/数据输入停止标志 void Crea

18、teBinTree(istream&in,BinTreeNode*&subTree);/从文件读入建树 bool Insert(BinTreeNode*&subTree,const T&x);/插入 void destroy(BinTreeNode *&subTree);/删除 bool Find(BinTreeNode *subTree,const T&x);/查找第28页/共137页2023/3/25二叉树-二叉链表的类定义 BinTreeNode*Copy(BinTreeNode *orignode);/复制int Height(BinTreeNode *subTree);/返回树高度i

19、nt Size(BinTreeNode *subTree);/返回结点数BinTreeNode*Parent(BinTreeNode *subTree,BinTreeNode*current);/返回父结点BinTreeNode*Find(BinTreeNode *subTree,constT&x)const;/搜寻xvoid Traverse(BinTreeNode *subTree,ostream&out);/前序遍历输出第29页/共137页2023/3/25二叉树-二叉链表的类定义 voidpreOrder(BinTreeNode&subTree,void(*visit)(BinTree

20、Node*p);/前序遍历voidinOrder(BinTreeNode&subTree,void(*visit)(BinTreeNode*p);/中序遍历voidpostOrder(BinTreeNode&Tree,void(*visit)(BinTreeNode*p);/后序遍历friend istream&operator(istream&in,BinaryTree&Tree);/重载操作：输入friend ostream&operator(ostream&out,BinaryTree&Tree);/重载操作：输出;第30页/共137页2023/3/25二叉树-二叉链表的函数实现/私有函

21、数:删除根为subTree的子树template void BinaryTree:destroy(BinTreeNode *subTree)if(subTree!=NULL)destroy(subTree-leftChild);/删除左子树 destroy(subTree-rightChild);/删除右子树 delete subTree;/删除根结点 第31页/共137页2023/3/25二叉树 -二叉链表的函数实现/从结点 subTree 开始,搜索结点 current的双亲,/若找到则返回双亲结点地址,否则返回NULL template BinTreeNode*BinaryTree:Pa

22、rent(BinTreeNode *subTree,BinTreeNode *current)if(subTree=NULL)return NULL;if(subTree-leftChild=current|subTree-rightChild=current)return subTree;/找到,返回父结点地址第32页/共137页2023/3/25二叉树 -二叉链表的函数实现BinTreeNode *p;if(p=Parent(subTree-leftChild,current)!=NULL)/递归在左子树中搜索 return p;else return Parent(subTree-rig

23、htChild,current);/递归在右子树中搜索 第33页/共137页2023/3/25二叉树 -二叉链表的函数实现/前序遍历输出template void Traverse(BinTreeNode *subTree,ostream&out)if(subTree!=NULL)outdataleftChild,out);Traverse(subTree-rightChild,out);第34页/共137页2023/3/25二叉树 -二叉链表的函数实现/输入并建立一棵二叉树Tree。in是输入流对象。templateistream&operator (istream&in,BinaryTre

24、e&Tree)CreateBinTree(in,Tree.root);/建立二叉树 return in;第35页/共137页2023/3/25二叉树 -二叉树的遍历二叉树的遍历（BinaryTreeTraversal）就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。“访问”的意思是对结点施行某些操作。令L、R、V分别代表遍历一个结点的左子树、右子树和访问该结点的操作，则可能有VLR,LVR,LRV,VRL,RVL,RLV六种遍历二叉树的规则，若规定先左后右则有VLR（前序遍历）、LVR（中序遍历）、LRV（后序遍历）三种。第36页/共137页2023/3/25二叉树 -二叉树的

25、遍历三种遍历算法：先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。第37页/共137页2023/3/25二叉树 -二叉树的遍历二叉树中序遍历的递归算法template void BinaryTree:InOrder(BinTreeNode *subTree,void(*visit)(BinTreeNode*p)if(subTree!=NULL)InOrder(subTree-leftChild,visit);/遍历左子树 visit(subTree);/访问根结点 InOrder(

26、subTree-rightChild,visit);/遍历右子树 第38页/共137页2023/3/25二叉树 -二叉树的遍历二叉树前序遍历的递归算法template void BinaryTree:PreOrder(BinTreeNode *subTree,void(*visit)(BinTreeNode*p)if(subTree!=NULL)visit(subTree);/访问根结点 PreOrder(subTree-leftChild,visit);/遍历左子树 PreOrder(subTree-rightChild,visit);/遍历右子树 第39页/共137页2023/3/25二叉

27、树 -二叉树的遍历二叉树后序遍历的递归算法template void BinaryTree:PostOrder(BinTreeNode *subTree,void(*visit)(BinTreeNode *p)if(subTree!=NULL)PostOrder(subTree-leftChild,visit);/遍历左子树PostOrder(subTree-rightChild,visit);/遍历右子树visit(subTree);/访问根结点 第40页/共137页2023/3/25二叉树 -二叉树遍历的应用/利用二叉树后序遍历算法计算二叉树的结点个数template int Binary

28、Tree:Size(BinTreeNode *subTree)const if(subTree=NULL)return 0;/空树 else return 1+Size(subTree-leftChild)+Size(subTree-rightChild);第41页/共137页2023/3/25二叉树 -二叉树遍历的应用/利用二叉树后序遍历算法计算二叉树的高度或深度template int BinaryTree:Height(BinTreeNode *subTree)const if(subTree=NULL)return 0;/空树高度为0 else int i=Height(subTree

29、-leftChild);int j=Height(subTree-rightChild);return(ij)?j+1:i+1;第42页/共137页2023/3/25二叉树 -以递归方式建立二叉树/私有函数:以递归方式建立二叉树。template void BinaryTree:CreateBinTree(ifstream&in,BinTreeNode*&subTree)Titem;if(!in.eof()/未读完,读入并建树 in item;/读入根结点的值 if(item!=RefValue)subTree=new BinTreeNode(item);/建立根结点 第43页/共137页20

30、23/3/25二叉树 -以递归方式建立二叉树if(subTree=NULL)cerr “存储分配错!”leftChild);/递归建立左子树CreateBinTree(in,subTree-rightChild);/递归建立右子树 else subTree=NULL;/封闭指向空子树的指针 第44页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 利用栈的前序遍历非递归算法template void BinaryTree:PreOrder(void(*visit)(BinTreeNode *p)stackBinTreeNode*S;BinTreeNode*p=root;S.Push

31、(NULL);第45页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 while(p!=NULL)visit(p);/访问结点 if(p-rightChild!=NULL)S.Push(p-rightChild);/预留右指针在栈中 if(p-leftChild!=NULL)p=p-leftChild;/进左子树 else S.Pop(p);/左子树为空 第46页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 利用栈的中序遍历非递归算法template void BinaryTree:InOrder(void(*visit)(BinTreeNode *p)stack

32、BinTreeNode*S;BinTreeNode*p=root;第47页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 do while(p!=NULL)/遍历指针向左下移动 S.Push(p);/该子树沿途结点进栈 p=p-leftChild;if(!S.IsEmpty()/栈不空时退栈 S.Pop(p);visit(p);/退栈,访问 p=p-rightChild;/遍历指针进到右子女 while(p!=NULL|!S.IsEmpty();第48页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 利用栈的后序遍历非递归算法template struct stkN

33、ode BinTreeNode*ptr;/树结点指针 enum tagL,R;/退栈标记 stkNode(BinTreeNode *N=NULL):ptr(N),tag(L)/构造函数;tag=L,表示从左子树退回还要遍历右子树;tag=R，表示从右子树退回要访问根结点。第49页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 template voidBinaryTree:PostOrder(void(*visit)(BinTreeNode *p)StackstkNodeS;stkNode w;BinTreeNode*p=root;/p是遍历指针 do while(p!=NULL

34、)w.ptr=p;w.tag=L;S.Push(w);p=p-leftChild;int continue1=1;/继续循环标记,用于R第50页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 while(continue1&!S.IsEmpty()S.Pop(w);p=w.ptr;switch(w.tag)/判断栈顶的tag标记 case L:w.tag=R;S.Push(w);continue1=0;p=p-rightChild;break;case R:visit(p);break;while(!S.IsEmpty();/继续遍历其他结点 cout endl;第51页/共13

35、7页2023/3/25二叉树-二叉树遍历的非递归算法 层次序遍历算法template voidBinaryTree:levelOrder(void(*visit)(BinTreeNode*t)if(root=NULL)return;QueueBinTreeNode*Q;BinTreeNode*p=root;Q.EnQueue(p);第52页/共137页2023/3/25二叉树-二叉树遍历的非递归算法 while(!Q.IsEmpty()Q.DeQueue(p);visit(p);if(p-leftChild!=NULL)Q.EnQueue(p-leftChild);if(p-rightChil

36、d!=NULL)Q.EnQueue(p-rightChild);第53页/共137页2023/3/25二叉树 例1：给定一棵二叉树的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，画出这颗二叉树。第54页/共137页2023/3/25二叉树 例2：给定一棵二叉树的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA，画出这颗二叉树。第55页/共137页2023/3/25二叉树 例3：给定一棵二叉树的先序和后序序列不能确定一棵二叉树。第56页/共137页2023/3/25线索二叉树-线索二叉树的概念为什么提出线索二叉树？遍历的过程实质上是对一个非线性结构进行线性化的操作

37、，使每个结点（除第一个和最后一个）在这个线性序列中有且仅有一个直接前驱和直接后继。二叉树种只存储了左右孩子的信息，因此，前驱和后继的信息无法直接找到。就提出了线索二叉树的概念。又因为n个结点的二叉链表中有n+1个空链域，从而得到线索二叉树的存储结构如下。第57页/共137页2023/3/25线索二叉树-线索二叉树的概念规定：若结点有左子树，则leftChild指示其左孩子，否则令leftChild指示其前驱；若结点有右子树，则其rightChild域指示其右孩子，否则令rightChild指示其后继。为避免混淆，增加两个标志域：ltag为0（1）表示leftChild指向左孩子（前驱），rta

38、g为0（1）表示rightChild指向右孩子（后继）。第58页/共137页2023/3/25线索二叉树-线索二叉树的概念其中，指向结点前驱和后继的指针叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化。第59页/共137页2023/3/25线索二叉树-线索二叉树的概念第60页/共137页2023/3/25线索二叉树-中序线索化二叉树的类定义template struct ThreadNode /线索二叉树的结点类 intltag,rtag;/线索标志 ThreadNode*leftChild,*rightChild;/线索或子女指针Tdata;/

39、结点数据 ThreadNode(const Titem)/构造函数 :data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0);第61页/共137页2023/3/25线索二叉树-中序线索化二叉树的类定义template classThreadTree /线索化二叉树类protected:ThreadNode*root;/树的根指针 void createInThread(ThreadNode*current,ThreadNode*&pre);/中序遍历建立线索二叉树 ThreadNode*parent(ThreadNode*t);/

40、寻找结点t的双亲结点第62页/共137页2023/3/25线索二叉树-中序线索化二叉树的类定义public:ThreadTree():root(NULL)/构造函数 void createInThread();/建立中序线索二叉树 ThreadNode*First(ThreadNode*current);/寻找中序下第一个结点 ThreadNode*Last(ThreadNode*current);/寻找中序下最后一个结点 ThreadNode*Next(ThreadNode*current);/寻找结点在中序下的后继结点第63页/共137页2023/3/25线索二叉树-中序线索化二叉树的类定

41、义ThreadNode*Prior(ThreadNode*current);/寻找结点在中序下的前驱结点voidInorder(void(*visit)(ThreadNode*p);/中序遍历voidpreorder(void(*visit)(ThreadNode*p);/前序遍历voidpostorder(void(*visit)(ThreadNode*p);/后序遍历 ;第64页/共137页2023/3/25线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱和后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。线索二叉树-通过中序遍历建立中序

42、线索化二叉树第65页/共137页2023/3/25线索二叉树-通过中序遍历建立中序线索化二叉树template void ThreadTree:createInThread()ThreadNode*pre=NULL;/前驱结点指针 if(root!=NULL)/非空二叉树,线索化 createInThread(root,pre);/中序遍历线索化二叉树 pre-rightChild=NULL;pre-rtag=1;/后处理中序最后一个结点 第66页/共137页2023/3/25线索二叉树-通过中序遍历建立中序线索化二叉树/通过中序遍历,对二叉树进行线索化template void Thread

43、Tree:createInThread(ThreadNode*current,ThreadNode*&pre)if(current=NULL)return;createInThread(current-leftChild,pre);/递归,左子树线索化 if(current-leftChild=NULL)/建立当前结点的前驱线索 current-leftChild=pre;current-ltag=1;第67页/共137页2023/3/25线索二叉树-通过中序遍历建立中序线索化二叉树if(pre!=NULL&pre-rightChild=NULL)/建立前驱结点的后继线索pre-rightCh

44、ild=current;pre-rtag=1;pre=current;/前驱跟上,当前指针向前遍历createInThread(current-rightChild,pre);/递归,右子树线索化第68页/共137页2023/3/25线索二叉树-寻找当前结点在中序下的后继 寻找当前结点在中序下的后继=0=1=NULL无此情况无后继！=NULL后继为当前结点右子树的中序下的第一个结点后继为右子女结点rtagrightChild第69页/共137页2023/3/25线索二叉树-寻找当前结点在中序下的后继/函数返回以*current为根的线索化二叉树中的中序序列下的第一个结点template Thr

45、eadNode*ThreadTree :First(ThreadNode*current)ThreadNode*p=current;while(p-ltag=0)p=p-leftChild;returnp;第70页/共137页2023/3/25线索二叉树-寻找当前结点在中序下的后继/函数返回在线索化二叉树中结点*current在中序下的后继结点template ThreadNode*ThreadTree:Next(ThreadNode*current)ThreadNode*p=current-rightChild;if(current-rtag=0)returnFirst(p);/rtag=0

46、,表示有右子女elsereturnp;/rtag=1,直接返回后继线索第71页/共137页2023/3/25线索二叉树-寻找当前结点在中序下的前驱 寻找当前结点在中序下的前驱=0=1=NULL无此情况无前驱！=NULL前驱为当前结点左子树中序下的最后一个结点前驱为左子女结点ltagleftChild第72页/共137页2023/3/25线索二叉树-中序线索化二叉树的中序遍历 template void ThreadTree :Inorder(void(*visit)(BinTreeNode*p)ThreadNode*p;for(p=First(root);p!=NULL;p=Next(p)vi

47、sit(p);第73页/共137页2023/3/25树与森林-树的存储表示 双亲表示法（父指针表示法）以一组连续的存储单元来存放树中的结点，每个结点有两个域，一个是data域，用来存放数据元素，一个是parent域，用来存放指示其父结点位置的指针。这种存储表示适合经常需要寻找父结点的应用。第74页/共137页2023/3/25树与森林-树的存储表示 孩子表示法（子女链表表示法）为树中每个结点设置一个子女链表，并将这些结点的数据和对应子女链表的头指针放在一个向量中，就构成了子女链表表示。这种存储表示适合需要频繁寻找子女的应用。无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。第

48、75页/共137页2023/3/25树与森林-树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法）子女-兄弟链表表示法也称为树的二叉树表示。他的每个结点的度为2，是最节省存储空间的树的存储表示。每个结点由三个域组成：firstChild指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。第76页/共137页2023/3/25树与森林-树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法）第77页/共137页2023/3/25树与森林-树的子女-兄弟表示的类定义template structTreeNod

49、e /树的结点类 Tdata;/结点数据 TreeNode*firstChild,*nextSibling;/子女及兄弟指针 TreeNode(Tvalue=0,TreeNode*fc=NULL,TreeNode*ns=NULL)/构造函数 :data(value),firstChild(fc),nextSibling(ns);第78页/共137页2023/3/25树与森林-树的子女-兄弟表示的类定义template class Tree/树类private:TreeNode*root,*current;/根指针及当前指针 int Find(TreeNode *p,Tvalue);/在以p为根

50、的树中搜索value void RemovesubTree(TreeNode *p);/删除以p为根的子树 bool FindParent(TreeNode *t,TreeNode*p);public:第79页/共137页2023/3/25树与森林-树的子女-兄弟表示的类定义Tree()root=current=NULL;/构造函数 bool Root();/置根结点为当前结点 bool IsEmpty()return root=NULL;bool FirstChild();/将当前结点的第一个子女置为当前结点 bool NextSibling();/将当前结点的下一个兄弟置为当前结点 boo