数据结构 第六章 树与二叉树.ppt

树的定义和基本术语树的定义和基本术语二叉树二叉树(Binary Tree)二叉树的存储结构二叉树的存储结构遍历二叉树遍历二叉树(Binary Tree Traversal)线索化二叉树线索化二叉树(Threaded Binary Tree)树与森林树与森林(Tree&Forest)赫夫曼树赫夫曼树(Huffman Tree)二叉树的计数二叉树的计数6.1 树的定义和基本术语树的定义和基本术语1.树的定义树的定义 树是由树是由n(n 0)个结点组成的有限集合。个结点组成的有限集合。如果如果n=0，称为空树；称为空树；如果如果n 0，则则:有一个特定的称之为有一个特定的称之为根根(root)的结点，它只的结点，它只有后继，但没有前驱；有后继，但没有前驱；除根以外的其它结点划分为除根以外的其它结点划分为m(m 0)个互不个互不相交的有限集合相交的有限集合T0,T1,Tm-1，每个集合本身每个集合本身又是一棵树，并且称之为根的又是一棵树，并且称之为根的子树子树(subTree)。每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个直接直接前驱，但可前驱，但可以有以有0个或多个后继。个或多个后继。n n结点结点结点结点(node)(node)n n结点的度结点的度结点的度结点的度(degree)(degree)n n分支分支分支分支(branch)(branch)结点结点结点结点n n叶叶叶叶(leaf)(leaf)结点结点结点结点n n孩子孩子孩子孩子(child)(child)结点结点结点结点n n双亲双亲双亲双亲(parent)(parent)结点结点结点结点n n兄弟兄弟兄弟兄弟(sibling)(sibling)结点结点结点结点n n祖先祖先祖先祖先(ancestor)(ancestor)结点结点结点结点n n子孙子孙子孙子孙(descendant)(descendant)结结结结点点点点n n结点所处层次结点所处层次结点所处层次结点所处层次(level)(level)n n树的深度树的深度树的深度树的深度(depth)(depth)n n树的度树的度树的度树的度(degree(degree)n n 有序树有序树有序树有序树n n 无序树无序树无序树无序树n n 森林森林森林森林 1）度（次数、级）度（次数、级）（1）结点的度：一个结点所拥有的子数的个数）结点的度：一个结点所拥有的子数的个数 （2）树的度：树内各结点的度的最大值）树的度：树内各结点的度的最大值2）描述上下及左右的关系）描述上下及左右的关系 孩子结点：一个结点的子树的根孩子结点：一个结点的子树的根 双亲结点：双亲结点：P120 兄弟结点：同一个双亲的孩子之间互称兄弟兄弟结点：同一个双亲的孩子之间互称兄弟 祖先：结点的祖先是从根到该结点所经分支上的祖先：结点的祖先是从根到该结点所经分支上的 所有结点所有结点 子孙：子孙：P120结点的后代结点的后代3）层次）层次 （1）结点的层次）结点的层次 （2）树的深度（高度）树的深度（高度）2.树的基本术语树的基本术语树的基本操作：树的基本操作：p119树的建立和遍历树的建立和遍历重点重点树的抽象数据类型树的抽象数据类型6.2 二叉树二叉树(Binary Tree)二叉树的定义二叉树的定义二叉树的五种不同形态二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树组成。特点：特点：1）每个结点的度）每个结点的度2；2）是有序树）是有序树基本操作：基本操作：p121p123二叉树的建立和遍历二叉树的建立和遍历二叉树的抽象数据类型二叉树的抽象数据类型性质性质1 若二叉树的层次从若二叉树的层次从1开始开始,则在二叉树的则在二叉树的第第 i 层最多有层最多有 2i-1个结点。个结点。(i 1)证明用数学归纳法证明用数学归纳法性质性质2 深度为深度为k的二叉树最多有的二叉树最多有 2k-1个结点。个结点。(k 1)证明用求等比级数前证明用求等比级数前k项和的公式项和的公式性质性质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-1 n0=n2+1 同理：同理：三次树：三次树：n0=1+n2+2n3四次树：四次树：n0=1+n2+2n3+3n4K次树：次树：n0=1+n2+2n3+(k-1)nk定义定义1 满二叉树满二叉树(Full Binary Tree)定义定义2 完全二叉树完全二叉树(Complete Binary Tree)若设二叉树的深度为若设二叉树的深度为h，则共有则共有h层。除第层。除第h层层外，其它各层外，其它各层(0 h-1)的结点数都达到最大个数，的结点数都达到最大个数，第第h层从右向左连续缺若干结点，这就是完全二层从右向左连续缺若干结点，这就是完全二叉树。叉树。性质性质4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1证明：证明：设完全二叉树的深度为设完全二叉树的深度为k，则有则有 2k-1-1 n 2k-1 2k-1 n 2k 取对数取对数 k-1 log2n 1,则则 i 的双亲为的双亲为 i/2 n n 若若2*i n,则则 i 的左孩子为的左孩子为2*i，否则无左孩子否则无左孩子 若若2*i+1 n,则则 i 的右孩子为的右孩子为2*i+1，否则无右否则无右孩子孩子n n 若若 i 为偶数为偶数,且且i!=n,则其右兄弟为则其右兄弟为i+1 若若 i 为奇数为奇数,且且i!=1,则其左兄弟为则其左兄弟为i-1n n i 所在层次为所在层次为 log2 i +1完全二叉树的数组表示完全二叉树的数组表示 一般二叉树的数组表示一般二叉树的数组表示二叉树的存储结构二叉树的存储结构1.顺序存储结构（数组表示）顺序存储结构（数组表示）#define MAX_TREE_SIZE 100typedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;由于一般二叉树必须仿照完由于一般二叉树必须仿照完全二叉树那样存储，可能会全二叉树那样存储，可能会浪费很多存储空间，单支树浪费很多存储空间，单支树就是一个极端情况。就是一个极端情况。单支树单支树2.2.链式存储结构链式存储结构typedef struct BiTNode /二叉链表的定义TElemType data;Struct BiTNode*lchild,*rchild;BiTNode,*BiTree;二叉树链表表示的示例二叉树链表表示的示例3.静态二叉链表和静态三叉链表静态二叉链表和静态三叉链表预先开辟空间，用数组表示leftChild,rightChild数组元素的下标6.3 遍历二叉树遍历二叉树 (Traversing Binary Tree)p128 所谓树的遍历，就是按某种次序访问树中的结点，所谓树的遍历，就是按某种次序访问树中的结点，所谓树的遍历，就是按某种次序访问树中的结点，所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。要求每个结点访问一次且仅访问一次。要求每个结点访问一次且仅访问一次。要求每个结点访问一次且仅访问一次。遍历的结果：遍历的结果：遍历的结果：遍历的结果：产生一个关于结点的线性序列。产生一个关于结点的线性序列。产生一个关于结点的线性序列。产生一个关于结点的线性序列。设设设设访问根结点访问根结点访问根结点访问根结点记作记作记作记作 D D 遍历根的左子树遍历根的左子树遍历根的左子树遍历根的左子树记作记作记作记作 L L 遍历根的右子树遍历根的右子树遍历根的右子树遍历根的右子树记作记作记作记作 R R 则可能的遍历次序有则可能的遍历次序有则可能的遍历次序有则可能的遍历次序有 先序先序先序先序 DLR DRL DLR DRL 逆先序逆先序逆先序逆先序 中序中序中序中序 LDR RDL LDR RDL 逆中序逆中序逆中序逆中序 后序后序后序后序 LRD RLDLRD RLD 逆后序逆后序逆后序逆后序先序遍历先序遍历(Preorder Traversal)先序遍历二叉树算法的框架先序遍历二叉树算法的框架是是n n若二叉树为空，则空操作；若二叉树为空，则空操作；n n否则否则uu访问根结点访问根结点(D)；uu先序遍历左子树先序遍历左子树(L)；uu先序遍历右子树先序遍历右子树(R)。遍历结果（前缀表达式）遍历结果（前缀表达式）-+a*b-c d/e f在波兰式中，自左到右在波兰式中，自左到右依次扫描：连续出现依次扫描：连续出现2个操作数时，将其前面个操作数时，将其前面的运算符退出，对该两的运算符退出，对该两操作数进行这两个操作操作数进行这两个操作数前面的运算符的运算，数前面的运算符的运算，运算的中间结果进栈，运算的中间结果进栈，然后再进行上述的操作。然后再进行上述的操作。先序遍历二叉树的递归算法先序遍历二叉树的递归算法void PreOrderTraverse(BiTree T)if(T)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是：n n若二叉树为空，则空操作；若二叉树为空，则空操作；n n否则否则uu中序遍历左子树中序遍历左子树(L)；uu访问根结点访问根结点(D)；uu中序遍历右子树中序遍历右子树(R)。遍历结果（中缀表达式）遍历结果（中缀表达式）a+b*c-d-e/f中序遍历中序遍历(Inorder Traversal)表达式语法树表达式语法树中序遍历二叉树的递归算法中序遍历二叉树的递归算法void InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild);printf(%c,T-data);InOrderTraverse(T-rchild);后序遍历后序遍历(Postorder Traversal)后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是n n若二叉树为空，则空操作；若二叉树为空，则空操作；n n否则否则uu后序遍历左子树后序遍历左子树(L)；uu后序遍历右子树后序遍历右子树(R)；uu访问根结点访问根结点(D)。在逆波兰式中，自左到在逆波兰式中，自左到右依次扫描：是操作数，右依次扫描：是操作数，则依次进栈；遇到运算则依次进栈；遇到运算符。则退出两个操作数，符。则退出两个操作数，对该两操作数进行该运对该两操作数进行该运算符的运算，运算的中算符的运算，运算的中间结果进栈；然后再继间结果进栈；然后再继续重复上述的操作。续重复上述的操作。遍历结果（后缀表达式）遍历结果（后缀表达式）a b c d-*+e f/-后序遍历二叉树的递归算法后序遍历二叉树的递归算法void PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(%c,T-data);由二叉树的先序序列和中序序列可唯一地确定一由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。棵二叉树。例例,先序序列先序序列 ABHFDECKG 和和中序序列中序序列 HBDFAEKCG,构造二叉树过程如构造二叉树过程如下：下：遍历二叉树的非递归算法遍历二叉树的非递归算法n先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈 n中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树n后序遍历：1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈n需用到栈，顺序栈的定义如下：typedef BiTNode*SElemType;typedef structSElemType*base;SElemType*top;int stacksize;SqStack;先序遍历的非递归算法先序遍历的非递归算法void preorder(BiTree T)SqStack S;BiTree P=T;InitStack(S);Push(S,NULL);while(P)printf(%c,P-data);if(P-rchild)Push(S,P-rchild);if(P-lchild)P=P-lchild;else Pop(S,P);先序遍历的非递归算法先序遍历的非递归算法2void preorder(BiTree T)int top=0;BiTree stack20,P=T;do while(P)printf(%c,P-data);stacktop=P;top+;P=P-lchild;if(top)top-;P=stacktop;P=P-rchild;while(top|P);中序遍历的非递归算法中序遍历的非递归算法1void inorder(BiTree T)SqStack S;BiTree P=T;InitStack(S);dowhile(P)*(S.top)=P;S.top+;P=P-lchild;if(S.top)S.top-;P=*(S.top);printf(%c,P-data);P=P-rchild;while(S.top!=S.base)|P);中序遍历的非递归算法中序遍历的非递归算法2（p131算法算法6.3)void inorder(BiTree T)SqStack S;BiTree P=T;InitStack(S);while(P|!Empty(S)if(P)Push(S,P);P=P-lchild;else Pop(S,P);printf(%c,P-data);P=P-rchild;后序遍历时，每遇到一个结点，先把它推入栈后序遍历时，每遇到一个结点，先把它推入栈中，让中，让PopTim=0。在遍历其左子树前，改结点的在遍历其左子树前，改结点的PopTim=1，将其左孩子推入栈中。在遍历完左子将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，树后，还不能访问该结点，必须继续遍历右子树，此时改结点的此时改结点的PopTim=2，并把其右孩子推入栈中。并把其右孩子推入栈中。在遍历完右子树后，结点才退栈访问。在遍历完右子树后，结点才退栈访问。后序遍历的非递归算法后序遍历的非递归算法1void Postorder(BiTree T)BiTree p=T,q=NULL;SqStack S;InitStack(S);Push(S,p);while(!StackEmpty(S)if(p&p!=q)Push(S,p);p=p-lchild;else Pop(S,p);if(!StackEmpty(S)if(p-rchild&p-rchild!=q)Push(S,p);p=p-rchild;else printf(%c,p-data);q=p;后序遍历的非递归算法后序遍历的非递归算法2void postorder(BiTree T)BiTree P=T,q;int flag;SqStack S;InitStack(S);do while(P)*(S.top)=P;S.top+;P=P-lchild;q=NULL;flag=1;while(S.top!=S.base)&flag)P=*(S.top-1);if(P-rchild=q)printf(%c,P-data);S.top-;q=p;else P=P-rchild;flag=0;while(S.top!=S.base);先序建立二叉树的递归算法先序建立二叉树的递归算法(p131,算法算法6.4)Status CreateBiTree(BiTree&T)char ch;scanf(%c,&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;二叉树的显示输出二叉树的显示输出void PrintBiTree(BiTree T,int n)int i;char ch=;if(T)PrintBiTree(T-rchild,n+1);for(i=1;idata);PrintBiTree(T-lchild,n+1);说明：说明：1）遍历的第一个和最后一个结点）遍历的第一个和最后一个结点第一个结点：第一个结点：先序：先序：根结点；根结点；中序：中序：沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；后序：后序：从根结点出发，沿着左链走，找到一个既没从根结点出发，沿着左链走，找到一个既没有左孩子又没有右孩子的结点。有左孩子又没有右孩子的结点。最后一个结点：最后一个结点：中序：中序：从根结点出发，沿着右链走，找到一个没有从根结点出发，沿着右链走，找到一个没有右孩子的结点；右孩子的结点；后序：后序：根结点。根结点。n先序：从根结点出发，沿着右链走，找到一个没有右孩子的结点；如果该结点有左孩子，再沿着其左孩子的右链走，以此类推，直到找到一个没有孩子的结点n求中序的第一个结点的算法：P=T;while(P-lchild)P=P-lchild;printf(P-data);求中序的最后一个结点的算法：P=T；while(P-rchild)P=P-rchild;Printf(P-data);n2）先序+中序 或 后序+中序均可唯一地确定一棵二叉树n3）二叉树的二叉链表存储结构中，有n+1个指针域未利用，已经使用的有n-1个指针域，共有2n个指针域利用二叉树利用二叉树后序遍历后序遍历计算二叉树的深度计算二叉树的深度int Depth(BiTree T)int depl,depr;if(T)depl=Depth(T-lchild);depr=Depth(T-rchild);if(depl=depr)return(depl+1);else return(depr+1);return 0;遍历二叉树的应用遍历二叉树的应用求二叉树结点个数求二叉树结点个数int Size(BiTree T)if(T=NULL)return 0;else return 1+Size(T-lchild)+Size(T-rchild);按层次遍历二叉树按层次遍历二叉树按层次遍历二叉树按层次遍历二叉树 从根开始逐层访问，从根开始逐层访问，从根开始逐层访问，从根开始逐层访问，用用用用FIFOFIFO队列实现。队列实现。队列实现。队列实现。typedef BiTNode*ElemType;typedef structQElemType *base;int front,rear;SqQueue;遍历顺序遍历顺序void LevelOrderTraverse(BiTree T)BiTree p;SqQueue Q;InitQueue(Q);if(T)Q.baseQ.rear=T;Q.rear=(Q.rear+1)%MAXQSIZE;while(Q.front!=Q.rear)p=Q.baseQ.front;printf(%c,p-data);Q.front=(Q.front+1)%MAXQSIZE;if(p-lchild)Q.baseQ.rear=p-lchild;Q.rear=(Q.rear+1)%MAXQSIZE;if(p-rchild)Q.baseQ.rear=p-rchild;Q.rear=(Q.rear+1)%MAXQSIZE;左右子树互换左右子树互换void Exchange(BiTree&T)BiTree S;if(T)S=T-lchild;T-lchild=T-rchild;T-rchild=S;Exchange(T-lchild);Exchange(T-rchild);复制二叉树复制二叉树void CopyTree(BiTree T,BiTree&T1)if(T)T1=(BiTree)malloc(sizeof(BiTNode);if(!T1)printf(Overflown);exit(1);T1-data=T-data;T1-lchild=T1-rchild=NULL;CopyTree(T-lchild,T1-lchild);CopyTree(T-rchild,T1-rchild);6.3线索二叉树（穿线树、线索树）线索二叉树（穿线树、线索树）(Threaded Binary Tree)线索线索(Thread):指向结点前驱和后继的指针指向结点前驱和后继的指针指向结点前驱和后继的指针指向结点前驱和后继的指针若结点有左孩子，则若结点有左孩子，则lchild指示其左孩子，否则指示其左孩子，否则lchild中存储该结点的前驱结点的指针；中存储该结点的前驱结点的指针；若结点有右孩子，则若结点有右孩子，则rchild指示其右孩子，否则指示其右孩子，否则rchild中存储指向该结点的后继结点的指针中存储指向该结点的后继结点的指针实质实质：对一个非线性结构进行线性化操作，使每个结：对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这些线性序列中有且仅点（除第一和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。有一个直接前驱和直接后继。说明说明：在线索树中的前驱和后继是指按某种次序遍历：在线索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继。所得到的序列中的前驱和后继。概概念念:(p132)线索链表、线索、线索化、线索二叉树线索链表、线索、线索化、线索二叉树线索二叉树及其线索链表的表示线索二叉树及其线索链表的表示标志域：标志域：标志域：标志域：ltagltag =0,=0,lchildlchild为左孩子指针为左孩子指针为左孩子指针为左孩子指针ltagltag =1,=1,lchildlchild为为为为前驱线索前驱线索前驱线索前驱线索rtagrtag=0,=0,rchildrchild为右孩子指针为右孩子指针为右孩子指针为右孩子指针rtagrtag=1,=1,rchildrchild为为为为后继指针后继指针后继指针后继指针线索二叉树的存储表示线索二叉树的存储表示 p133typedef enumLink,ThreadPointerTag;/Link=0：指针，指向孩子结点指针，指向孩子结点/Thread=1：线索，指向前驱或后继结点线索，指向前驱或后继结点typedef struct BiThrNodeTElemType data;struct BiThrNode*lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;BiThrTree T；带表头结点的中序穿线链表带表头结点的中序穿线链表从遍历的第一个结点来看：从遍历的第一个结点来看：先序序列中第一个结点必为根结点先序序列中第一个结点必为根结点中、后序序列中第一个结点的左孩子定为空中、后序序列中第一个结点的左孩子定为空从遍历的最后一个结点来看：从遍历的最后一个结点来看：先、中序序列中最后一个结点的右孩子必为空先、中序序列中最后一个结点的右孩子必为空后序序列中最后一个结点一定为根结点后序序列中最后一个结点一定为根结点作用：作用：对于遍历操作，线索树优于非线索树；对于遍历操作，线索树优于非线索树；遍历线索树不用设栈遍历线索树不用设栈步骤：步骤：1)找遍历的第一个结点找遍历的第一个结点2)不断地找遍历到的结点的后继结点，直到树中各结点不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束。都遍历到为止，结束。遍历线索二叉树if(currentRTag=Thread)后继为后继为 currentrchildelse /currentRTag=Link 后继为当前结点右子树后继为当前结点右子树 的中序下的第一个结点的中序下的第一个结点 寻找当前结点寻找当前结点在中序下的后继在中序下的后继ABDECFHIKGJL中序后继线索二叉树DBGJEACHLKFIif(currentLTag=Thread)前驱为前驱为currentlchild else/currentLTag=Link 前驱为当前结点左子树的前驱为当前结点左子树的 中序下的最后一个结点中序下的最后一个结点 寻找当前结点寻找当前结点在中序下的前驱在中序下的前驱ABDECFHIKGJL中序前驱线索二叉树中序序列：DBGJEACHLKFI遍历中序线索二叉树遍历中序线索二叉树(不带头结点）不带头结点）void inorder1_Thr(BiThrTree T)BiThrTree p=T;while(p-LTag=Link)p=p-lchild;printf(%c,p-data);while(p-rchild)if(p-RTag=Link)p=p-rchild;while(p-LTag=Link)p=p-lchild;else p=p-rchild;printf(%c,p-data);void inorder2_Thr(BiThrTree T)BiThrTree p=T;while(p)while(p-LTag=Link)p=p-lchild;printf(%c,p-data);while(p-RTag=Thread&p-rchild)p=p-rchild;printf(%c,p-data);p=p-rchild;ABDECFHIKGJLABDECFHIKGJL先序线索二叉树ABDEGJCFHKLI后序线索二叉树DJGEBLKHIFCA先序线索二叉树先序线索二叉树在先序线索二叉树中在先序线索二叉树中 寻找当前结点的后继与前驱寻找当前结点的后继与前驱遍历先序线索二叉树遍历先序线索二叉树(不带头结点）不带头结点）void preorder_Thr(BiThrTree T)BiThrTree p=T;printf(%c,p-data);while(p-rchild)if(p-LTag=Link)p=p-lchild;else p=p-rchild;printf(%c,p-data);后序线索二叉树后序线索二叉树在后序线索化二叉树中在后序线索化二叉树中 寻找当前结点的后继寻找当前结点的后继遍历后序线索二叉树遍历后序线索二叉树(不带头结点）不带头结点）void postorder_Thr(TriThrTree T)TriThrTree f,p=T;do while(p-LTag=Link)p=p-lchild;if(p-RTag=Link)p=p-rchild;while(p-LTag!=Thread|p-Tag!=Thread);printf(%c,p-data);while(p!=T)if(p-RTag=Link)f=p-parent;if(f-RTag=Thread|p=f-rchild)p=f;else p=f-rchild;do while(p-LTag=Link)p=p-lchild;if(p-RTag=Link)p=p-rchild;while(p-LTag!=Thread|p-RTag!=Thread);else p=p-rchild;printf(%c,p-data);n将未线索过的二叉树给予线索将未线索过的二叉树给予线索在遍历的前在遍历的前提下，按照先、中、后序中的一种提下，按照先、中、后序中的一种n中中序线索化序线索化u后继线索化后继线索化处理前驱结点处理前驱结点Fa.如果无前驱结点，则不必加线索如果无前驱结点，则不必加线索Fb.如果前驱结点的右指针域为非空，也不必加如果前驱结点的右指针域为非空，也不必加线索线索Fc.如果前驱结点的右指针域为空，则把当前结如果前驱结点的右指针域为空，则把当前结点的指针值赋给前驱结点的右指针域。点的指针值赋给前驱结点的右指针域。二叉树的线索化二叉树的线索化后继线索化后继线索化处理前驱结点处理前驱结点void InThreading(BiThrTree P)if(P)InThreading(P-lchild);if(!P-rchild)P-RTag=Thread;if(pre&pre-RTag=Thread)pre-rchild=P;pre=P;InThreading(P-rchild);前驱线索化前驱线索化处理后继结点处理后继结点void InThreading(BiThrTree P)if(P)InThreading(P-lchild);if(!P-lchild)P-LTag=Thread;P-lchild=pre;pre=P;InThreading(P-rchild);通过中序遍历建立中序线索化二叉树通过中序遍历建立中序线索化二叉树P135算法算法6.7void InThreading(BiThrTree P)if(P)InThreading(P-lchild);if(!P-lchild)P-LTag=Thread;P-lchild=pre;if(!pre-rchild)pre-RTag=Thread;pre-rchild=P;pre=P;InThreading(P-rchild);P134 算法算法6.6（设定一个表头结点）（设定一个表头结点）注：指针注：指针pre始终指向当前访问结点的前驱结点始终指向当前访问结点的前驱结点int InOrderThreading(BiThrTree&Thrt,BiThrTree T)if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;pre-RTag=Thread;Thrt-rchild=pre;return OK;中序线索化void InThreading2(BiThrTree P)if(P)InThreading2(P-lchild);if(!P-lchild)P-LTag=Thread;P-lchild=pre;if(!P-rchild)P-RTag=Thread;if(pre&pre-RTag=Thread)pre-rchild=P;pre=P;InThreading2(P-rchild);先序线索化void PreThreading(BiThrTree P)if(P)if(!P-lchild)P-LTag=Thread;P-lchild=pre;if(!P-rchild)P-RTag=Thread;if(pre&pre-RTag=Thread)pre-rchild=P;pre=P;if(P-LTag=Link)PreThreading(P-lchild);if(P-RTag=Link)PreThreading(P-rchild);后序线索化void PostThreading(TriThrTree P)if(P)PostThreading(P-lchild);PostThreading(P-rchild);if(!P-lchild)P-LTag=Thread;P-lchild=pre;if(!P-rchild)P-RTag=Thread;if(preT&preT-RTag=Thread)pre-rchild=P;pre=P;1.树的存储结构树的存储结构树的存储结构树的存储结构6.4 树和森林树和森林1)多重链表（标准存储结构）u定长结构（n为树的度）指针利用率不高u不定长结构 d为结点的度，节省空间，但算法复杂u一般采用定长结构如有n个结点，树的度为k，则共有n*k个指针域，只有n-1个指针域被利用，而未利用的指针域为：n*k-(n-1)=n(k-1)+1，未利用率为：(n(k-1)+1)/nk n(k-1)/nk=(k-1)/k二次树：1/2 ；三次树：2/3；四次树：3/4树的度越高，未利用率越高，由于二叉树的利用率较其他树高，因此用二叉树。data data child1child2child3childndchild2child3childdn2)常用的其他几种存储结构n双亲表示法双亲表示法 p135u用结构数组树的顺序存储方式u类型定义：p135u找双亲方便，找孩子难n孩子链表表示法孩子链表表示法 p136u顺序和链式结合的表示方法u找孩子方便，找双亲难u若用p137图6.14中带双亲的孩子链表表示，则找孩子找双亲都较方便n孩子兄弟表示法孩子兄弟表示法p136u找孩子容易，若增加parent域，则找双亲也较方便。双亲表示双亲表示#define MAX_TREE_SIZE 100typedef struct PTNodeTElemType data;int parent;PTNode;typedef struct PTNode nodesMAX_TREE_SIZE；int r,n;/根位置和结点数PTree;n树的存储结构u孩子表示法ACFEBDGJHI#define MAX_TREE_SIZE 100 typedef struct CTNode int child;struct CTNode*next;*ChildPtr;typedef struct TElemType data;/孩子链表的头指针孩子链表的头指针 ChildPtrfirstchild;CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;intn,r;/结点数和根的位置结点数和根的位置CTree;n树的存储结构u孩子表示法ACFEBDGJHIA BC DE F GH I J 0123456789123 45 6 789 孩子兄弟表示法（二叉链表表示法）孩子兄弟表示法（二叉链表表示法）树的左孩子树的左孩子-右兄弟表示右兄弟表示 datafirstChildnextSiblingtypedef struct CSNodeElemType data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;2.森林与二叉树的转换森林与二叉树的转换森林与二叉树的对应关系森林与二叉树的对应关系(1)树转化成二叉树的简单方法树转化成二叉树的简单方法在同胞兄弟之间加连线；在同胞兄弟之间加连线；在同胞兄弟之间加连线；在同胞兄弟之间加连线；保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；顺时针旋转顺时针旋转顺时针旋转顺时针旋转4545度。度。度。度。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。森林转化成二叉树森林转化成二叉树将森林中的每棵树转换成对应的二叉树；将森林中的每棵树转换成对应的二叉树；将森林中的每棵树转换成对应的二叉树；将森林中的每