第7章树和二叉树

1、第7章 树烟台大学计算机学院数据结构课程组树例与特征n社会的组织结构社会的组织结构n家族的族谱家族的族谱n计算机中的目录组织计算机中的目录组织描述层次结构，是一种一对多的逻辑关系描述层次结构，是一种一对多的逻辑关系树的定义 w 树树(Tree)(Tree)是n(n=0)个结点的有限集。n=0时称为空树。w（注：（注：KNUTH定义树不能为空）定义树不能为空）n有且仅有一个称为根的结点（Root）；nn1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每个集合又是一棵树，称为子树(SubTree)ABCDEHFI1234G树定义ACBGFEHIJDMKLAT1T2T3树的抽象

2、数据类型树的抽象数据类型ADT Tree数据对象数据对象 D：D是具有相同特性的数据元素的是具有相同特性的数据元素的集合。集合。 数据关系数据关系 R：若：若D为空集，则称为空树；为空集，则称为空树； 若若D仅含有一个数据元素，则仅含有一个数据元素，则R为空集，否为空集，否则则R=H，H是如下定义的二元关系：是如下定义的二元关系：（1 1）在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无前驱；下无前驱； （转下页）（转下页） 树的抽象数据类型树的抽象数据类型（2）若）若D-root,则存在则存在D-root的一个划分的一个划分D1，D2,Dm（m

3、0）,对任意对任意j k(1 j,k m)有有Dj Dk= ,且对任意的且对任意的i(1 i m ),存在唯一数据元素存在唯一数据元素xi Di , H;（ 3 ） 对 应 于） 对 应 于 D - r o o t 的 划 分 ，的 划 分 ， H -,有唯一的一个划分有唯一的一个划分H1, H2,Hm(m0),对任意对任意j k(1 j,k m)有有Hj Hk= ,且且对任意对任意i(1 i m )，Hi是是Di上的二元关系，（上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根）是一棵符合本定义的树，称为根root的子树。的子树。 （转下页）（转下页）TreeInit(T);TreeC

4、hild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T,y,i,x);ADT Tree树的抽象数据类型树的其它表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示凹入表示ABFEKLGCDHMIJ嵌套集合嵌套集合（文氏图）（文氏图）(A(B(E(K,L),F),C(G),D(H(M),I,J)广义表广义表（括号法）（括号法）w 结点结点：一个数据元素及若干指向其子树

5、的分支；一个数据元素及若干指向其子树的分支；w 结点的度结点的度：结点拥有的子树的数目。结点拥有的子树的数目。w 树的度树的度：树内各结点的度的最大值；：树内各结点的度的最大值；w 叶子叶子（终端结点）：度为（终端结点）：度为0的结点；的结点；w 分支结点分支结点（非终端结点）：度不为（非终端结点）：度不为0的结点；除的结点；除根结点外，也称内部结点；根结点外，也称内部结点；树的概念ACBGFEHIJDMKLw 孩子，双亲，孩子，双亲，兄弟，兄弟，堂兄堂兄：结点的子树的根称：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄

6、弟；一个双亲的孩子之间互称兄弟；其父结点是兄其父结点是兄弟的结点互称堂兄。弟的结点互称堂兄。树的概念ACBGFEHIJDMKL概念w 祖先祖先：从根结点到该结点所经分支上的所：从根结点到该结点所经分支上的所有结点。有结点。w 子孙子孙：以某结点为根的子树中的任一结点：以某结点为根的子树中的任一结点都称为该结点的子孙。都称为该结点的子孙。w 层次层次：结点在树结构中的层（：结点在树结构中的层（一般定义根一般定义根为为1层）层）ACBGFEHIJDMKL概念w 深度深度：树中结点的最大层次称为树的深度；：树中结点的最大层次称为树的深度；w 有序树有序树：结点的子树在树中的位置固定，：结点的子树在树

7、中的位置固定，不能互换，称有序树不能互换，称有序树w 无序树无序树：可以互换：可以互换w 森林森林：m(m0)棵互不相交的树的集合。棵互不相交的树的集合。ACBGFEHIJDMKL二叉树的概念 w 二叉树二叉树(Binary Tree)(Binary Tree)：或者是一棵空树，或者是一棵空树，或者是一棵由一个根结点和两棵互不相交或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树树和右子树又同样都是二叉树 w 特征特征：n每个结点最多只有两棵子树每个结点最多只有两棵子树n子树有左右之分，其次序子树有左右之分，其

8、次序不能任意颠倒，只有一棵子不能任意颠倒，只有一棵子树时也必须分清左右子树。树时也必须分清左右子树。 D D E EB B F F G G C CA A二叉树的抽象数据类型ADT BinTree 数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系R：若：若D= ，则，则R= ，称二叉树为空二叉树；，称二叉树为空二叉树； 若若D，则，则R=H，H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无下无前驱；前驱； （2）若）若D-root,则存在则存在D-r

9、oot=D1,Dr,且且 D1 Dr； （3）若）若D1，则，则D1中存在唯一的元素中存在唯一的元素x1, H,且存在且存在D1上的关系上的关系H1 H；若；若Dr,则则Dr中存在唯一的元素中存在唯一的元素xr, H, 且存在且存在Dr上的关系上的关系Hr H；H=, H1, Hr; （4）（）（D1，H1）是一棵符合本定义的二叉树，称为根的左子）是一棵符合本定义的二叉树，称为根的左子树，（树，（Dr，Hr）是一棵符合本定义的二叉树，称为根的右子）是一棵符合本定义的二叉树，称为根的右子树。树。基本操作如下：基本操作如下：二叉树的抽象数据类型BiTreeInit (BT);BiTreeRoot(

10、BT);BiTreeParent(BT,x);BiTreeLeftChild (BT,x);BiTreeRightChild (BT,x);BiTreeBuild(BT,LBT,RBT);BiTreeInsertLeft(BT,y,x);BiTreeInsertRight(BT,y,x);BiTreeDeleteLeft(BT,x);BiTreeDeleteRight(BT,x);BiTreeClear(BT);BiTraverse(BT);ADT BinTree 二叉树的五种形态(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)二叉树的性质1.1.一个非空二叉树的第一个非空二叉树的

11、第i i层上至多有层上至多有2 2i-1i-1个结个结点（点（i i 1 1） 证明：i = 1, 只有根结点，显然成立设i = k时成立，最多有2k-1当i= k+1时，最多的 结点个数： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-11891011121314154526732.2.深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k(k 1)1) 二叉树的性质证明：二叉树的结点个数为：1 + 2 + + 2k-1= 2k-1189101112131415452673二叉树的性质3.3.对任何一棵二叉树对任何一棵二叉树T T，如果其终端结

12、点数，如果其终端结点数为为n0n0，度为，度为2 2的结点数的结点数为为n2n2，则，则n0=n2+1n0=n2+1。证明：设n1为T中度为1的结点数，则总结点数：n = n0 + n1 + n2 (1) 189101112452673二叉树的性质另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则n= B+1 = n1 + 2 * n2+1 (2) 由(1)和(2)有： n1 + 2 * n2 1 = n0 + n1 + n2 故 n0 = n2 + 1;189101112452673满二叉树w 满二叉树满二叉树：深度为深度为k且有且有2k-1个结点的二叉

13、树个结点的二叉树189101112131415452673满二叉树满二叉树w考虑到有序性，考虑到有序性，任一结点在树中任一结点在树中都有确切的位置，都有确切的位置，因此可以对满二因此可以对满二叉树进行编号。叉树进行编号。编号方式为：从编号方式为：从上到下，从左到上到下，从左到右。右。完全二叉树w 完全二叉树：完全二叉树：深度为深度为k，有，有n个结点的二叉个结点的二叉树，当且仅当树，当且仅当其每一个结点其每一个结点都与深度为都与深度为k的的满二叉树编号满二叉树编号从从1到到n的结点的结点一一对应时，一一对应时，称为完全二叉称为完全二叉树。树。189101112452673完全二完全二叉树叉树完

14、全二叉树w特征：特征：n叶子结点只可能在层次最大的两层上叶子结点只可能在层次最大的两层上出现。出现。n任一结点，若其右分支下的子孙的最任一结点，若其右分支下的子孙的最大层次为大层次为l，则其左分支下的最大层次，则其左分支下的最大层次为为l或或l+1，即若结点，即若结点无左子女无左子女，决不决不应有右子女应有右子女。完全二叉树的特性（1）1.1.具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度 k = k = loglog2 2n n +1 +1 （ x 表示不大于表示不大于x的最大整数的最大整数）证明：设二叉树的深度为证明：设二叉树的深度为k，则：，则： 2k-1 1 n 2k

15、1 2k-1 n 2k k-1 log2n 1,则其双亲结点是则其双亲结点是 i/2 。 （b）如果）如果2in,则结点则结点i无左孩子，无左孩子，i为叶子结点为叶子结点,否则其左孩子是结点否则其左孩子是结点2i。 （c）如果）如果2i+1n，则结点，则结点i无右孩子，否则其右无右孩子，否则其右孩子是结点孩子是结点2i+1。 示意图2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j层j+1层示意图189101112452673性质举例1.1.设一棵完全二叉树共有设一棵完全二叉树共有700700个结点，则该个结点，则该二叉树有几个叶子结点，有几个度为二叉

16、树有几个叶子结点，有几个度为1 1的的结点？结点？2.2.设树设树T T的度为的度为4 4，其中度为，其中度为1 1，2 2，3 3，4 4的结的结点个数分别为点个数分别为4 4，2 2，1 1，1 1。则。则T T中有几个中有几个叶子结点。叶子结点。 350350个，个，1 1个个 8 8个个n=n0+n1+n2+n3+n4n=n0+n1+n2+n3+n4 =B+1=4n4+3n3+2n2+n1 +1 =B+1=4n4+3n3+2n2+n1 +1n0=3n4+2n3+n2+1=3+2+2+1n0=3n4+2n3+n2+1=3+2+2+1完全二叉树性质的推论w n个结点的完全二叉树个结点的完全

17、二叉树中：中：n 度为度为1的结点的结点数为数为(n+1)%2; n 度为度为0的结点数为的结点数为 (n+1)/2 ；n 度为度为2的结点数为的结点数为 (n+1)/2 -1；n 编号最大的分支结点是编号最大的分支结点是 n/2 ；n 编号最小的叶子结点是编号最小的叶子结点是 n/2 +1。w n个结点的二叉树：个结点的二叉树：n高最多为高最多为n；n最低为最低为 log2n +1（完全二叉树）。（完全二叉树）。二叉树的存储储结构w顺序存储结构w链式存储结构二叉树的顺序存储结构n整个二叉树可以按照从上到下，从左到整个二叉树可以按照从上到下，从左到右的顺序编号；右的顺序编号；n对于满对于满/完

18、全二叉树，可以从根结点开始完全二叉树，可以从根结点开始按序号存放；按序号存放；n对于一般的二叉树，可以参照满二叉树对于一般的二叉树，可以参照满二叉树的编号方法进行编号，位置空的结点空的编号方法进行编号，位置空的结点空置。置。顺序存储结构举例A AH HI I J JD DE EB BF FG GC C完全二叉树12345678910ABCDEFGHIJ顺序存储结构举例ABCDEFGHA AG G H HD DE EB BF FC C一般二叉树一般二叉树12345678910顺序存储结构举例非完全二非完全二叉树叉树ABCXABCA B C 二叉树的链式存储结构w 二叉链表二叉链表w 三叉链表三叉

19、链表w （线索链表）（线索链表）lchilddatarchilddatalchild rchildlchilddatarchildparentdatalchild rchildparent链式存储结构示例ACFEDBADBCEFABCDEF二叉链表二叉链表三叉链表三叉链表二叉链表的类C表示 二叉树的二叉链表存储表示二叉树的二叉链表存储表示typedef struct Node ElemType data; struct Node * *lchild, * *rchild; 左右孩子指针左右孩子指针 BTNode,*BiTree；二叉树的遍历二叉树的遍历 二叉树的遍历的定义二叉树的遍历的定义：

20、按某种规律，访问二叉树的结点，使每按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次。访问的含义个结点被访问一次且仅一次。访问的含义包括查询、打印、计算、修改等对结点的包括查询、打印、计算、修改等对结点的操作。操作。 二叉树的遍历二叉树的遍历 遍历的过程，实际上是按某种规律，遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序将一个非线性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱列，使每个结点在这种遍历中有唯一前驱和后继关系。和后继关系。 一棵二叉树的遍历序列（在某种遍历一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不方式下）是唯一

21、的，但一般说，二叉树不能由某一遍历序列唯一确定。能由某一遍历序列唯一确定。二叉树的遍历二叉树的遍历 w 层次遍历层次遍历w 递归遍历递归遍历ACFEDBDLR，DRL，LDR，RDL，LRD，RLDABCDEFDLR二叉树的遍历二叉树的遍历 w 前序遍历二叉树前序遍历二叉树w 中序遍历二叉树中序遍历二叉树w 后序遍历二叉树后序遍历二叉树访问根结点；访问根结点；前序遍历左子树；前序遍历左子树；前序遍历右子树前序遍历右子树； 中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树；中序遍历右子树； 后序遍历左子树；后序遍历左子树；后序遍历右子树；后序遍历右子树； 访问根结点；访问根

22、结点；D DL LR RLDRLDR、LRDLRD、DLRDLRRDLRDL、RLDRLD、DRLDRL若二叉树为空，则空操作，否则：若二叉树为空，则空操作，否则：ADBCD L RAD L RD L RBDCD L R前序遍历序列：前序遍历序列：A B D CA B D C前序遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A CB D A C中序遍历ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列： D B C AD B C A后序遍历B递归遍历举例abcdgefABCDEF前序序列：前序序列：abdefcg

23、中序序列：中序序列：dfebagc后序序列：后序序列：fedbgca前序序列：前序序列：abcdef中序序列：中序序列：cbefda后序序列：后序序列：cfedba中序遍历二叉树的递归算法void InOrder (BTNode *T) if(T) 二叉树非空二叉树非空 InOrder (T-lchild); 中序遍历左子树中序遍历左子树 visit(T-data); 访问根结点访问根结点 InOrder (T-rchild); 中序遍历右子树中序遍历右子树 if InOrder 前序遍历前序遍历(PreOrder)和后序遍历和后序遍历(PostOrder)同同中序遍历的区别只是中序遍历的区别

24、只是visit的位置不同。的位置不同。图例CFEDBABCEF DA二叉树的层次遍历算法void LevelOrder (BTNode *T) BTNode *p; if(T) 二叉树非空二叉树非空 InitQueue (Q); /初始化队列初始化队列 EnQueue (Q,T); 根首先入队根首先入队 while(QueueEmpty (Q)!=true) DeQueue(Q,p); /取出队首元素放入取出队首元素放入p中中 visit(p-data); /访问元素，例如访问元素，例如coutdata if(p-lchild!=NULL) /左孩子非空入队左孩子非空入队 EnQueue (Q

25、,p-lchild); if(p-rchild!=NULL) /右孩子非空入队右孩子非空入队 EnQueue (Q,p-rchild); if ACFEDB二叉树的中序非递归遍历 设设S为一个栈，为一个栈，t为指向根结点的指针，为指向根结点的指针， 其处理其处理过程为：过程为：（1）当）当t非空时，将非空时，将t所指结点的地址进栈，并所指结点的地址进栈，并将将t指向该结点的左子树；指向该结点的左子树；（2）当）当t为空时，弹出栈顶元素，显示结点元素为空时，弹出栈顶元素，显示结点元素，并将，并将t指向该结点的右子树；指向该结点的右子树；（3）重复（）重复（1）、（）、（2）步骤，直到栈空且）步骤

26、，直到栈空且t 也为也为空空。 void inorder (BTNode *t) BTNode *sn+1; top=0; while (t!=null | top!=0) while (t!=null) s+top=t; t=t-lchild ; if (top!=0) t=stop-; coutdata; t=t-rchild; InOrder中序非递归遍历 算法cba非递归中序遍历栈S的变化cbat”t”t”a”at”NULL”a出栈出栈t”NULL”出栈出栈bt”b”t”NULL”b出栈出栈t”NULL”出栈出栈t”c”ct”NULL”c出栈出栈t”NULL”栈空栈空结束结束void

27、preorder (BTNode *t) BTNode *sn+1; top=0; while (t!=null | top!=0) while (t!=null) coutdata; s+top=t; t=t-lchild ; if (top!=0) t=stop-rchild; preorder前序非递归遍历 算法cbavoid postorder (BTNode *t) typedef struct node BTNode *t; int tag; /tag 0.1，0表示表示 stack; /未遍历右子树未遍历右子树 stack sn+1 ; top=0; while (t!=null

28、 | top!=0) while (t!=null) s+top.t=t; stop.tag=0; t=t-lchild; while (top!=0 & stop.tag=1) coutdata; if (top) stop.tag=1; t=stop.t-rchild ; postorder后序非递归遍历 算法cba建立二叉树BTNode* CreatBiTree() 按前序构造二叉链表表示的二叉树按前序构造二叉链表表示的二叉树T BTNode *T; cinch; if(ch= =# ) T=NULLNULL; /以以#表示空表示空 else / T=new BTNode; T-

29、data=ch; 生成根结点生成根结点 T-lchild=CreatBiTree(); 生成左子树生成左子树 T-rchild=CreatBiTree(); 生成左子树生成左子树 if return T; CreatBiTree 输入序列为：输入序列为：- -a#b#c#a#b#c#cba#遍历举例ACFEDB前序序列为：前序序列为：A B E C D FA B E C D F 中序序列为：中序序列为：B E A D F CB E A D F C 后序序列为：后序序列为：E B F D C AE B F D C A 已知前序和中序遍历序列，画出已知前序和中序遍历序列，画出二叉树二叉树，写出后，

30、写出后序序遍历序序列。遍历序序列。若序列为：若序列为：C F D A E B ,C F D A E B ,应如何遍历应如何遍历 二叉树结构的性质w 已知二叉树的已知二叉树的先序序列和中序序列先序序列和中序序列，可，可以唯一确定一棵二叉树。以唯一确定一棵二叉树。w 已知二叉树的已知二叉树的后序序列和中序序列后序序列和中序序列，可，可以唯一确定一棵二叉树；以唯一确定一棵二叉树；w 已知二叉树的已知二叉树的先序序列和后序序列先序序列和后序序列，不，不能唯一确定一棵二叉树；能唯一确定一棵二叉树；(如如AB与与BA)w 已知二叉树的已知二叉树的层次序列和中序序列层次序列和中序序列，可，可以唯一确定一棵二

31、叉树。以唯一确定一棵二叉树。表达式的二叉树表示+*+fhg*+abc+de用二叉树可以表示表达式用二叉树可以表示表达式前序遍历：前序遍历：*+ab*c+def+gh中序遍历：中序遍历：a+b+c*d+e+f*g+h后序遍历：后序遍历：ab+cde+*+f+gh+*表达式表达式: (a+b)+c*(d+e)+f)*(g+h)二叉树遍历算法的应用(1)w 以二叉链表作存储结构，试编写求二叉树深度以二叉链表作存储结构，试编写求二叉树深度的算法。的算法。w int BTHeight(BTNode *T)w if(T=NULL)return 0;w elsel=BTHeight (T-lchild);w

32、 r=BTHeight (T-rchild);w return(lr?l:r)+1);w w ACFEDB二叉树遍历算法的应用(2)w 以二叉链表作为存储结构，试编写求二叉树中叶子数以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。的算法。w int LeafCount(BTNode *T) w if(!T) return 0; /空树没有叶子空树没有叶子 w else if(!T-lchild&!T-rchild) return 1; /叶子结点叶子结点 w else return LeafCount(T-lchild)+LeafCount(T-rchild); /左子树叶子数加

33、上右子树叶子数左子树叶子数加上右子树叶子数 w 二叉树遍历算法的应用(3)w 以二叉链表作为存储结构，试编写求二叉树中叶子数以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。的算法。(与上例不同与上例不同)w int num=0;w void LeafCount(BTNode *T) w if(T) w LeafCount(T-lchild) ; /中序遍历左子树中序遍历左子树w if(!T-lchild & !T-rchild) num+; /访问根结访问根结点点w LeafCount(T-rchild) ; /中序遍历右子树中序遍历右子树w w 二叉树遍历算法的应用(4)w 以

34、二叉链表作为存储结构，设计算法交换二以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。叉树中所有结点的左、右子树。w void change(BTNode *&T)w if(T!=NULL)w change(T-lchild);w change(T-rchild);w t=T-lchild;w T-lchild=T-rchild;w T-rchild=t;ww 二叉树遍历算法的应用(5)w 以二叉链表作为存储结构，设计算法拷贝二叉树。以二叉链表作为存储结构，设计算法拷贝二叉树。w BTNode* copy(BTNode *T)w BTNode *T1;w if(T=nu

35、ll) T1=null;w else w T1=new BTNode; /申请结点申请结点w T1-data=T-data; w T1-lchild=copy(T-lchild);w T1-rchild=copy(T-rchild);ww return T1;w 二叉树遍历算法的应用(6)w 由顺序存储的由顺序存储的n个结点的完全二叉树建立二叉链表存储的二个结点的完全二叉树建立二叉链表存储的二叉树。叉树。w BTNode* creat(ElemType A,int i)w BTNode *T;w if(in) T=null;w else w T=new BTNode; /申请结点申请结点w T

36、-data=Ai; w T-lchild=creat(A,2*i);w T-rchild=creat(A,2*i+1);ww return T;w /初始调用：初始调用：p=creat(A,1);A AH HI IJ JD DE EB BF FG GC C1 2 3 4 5 6 7 8 9 10A B C D E F G H I J二叉树遍历算法的应用(7)w 设一棵二叉树中各结点的值互不相同，其前序序列设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组和中序序列分别存于两个一维数组pre1.n 和和in1.n 中，试遍写算法建立该二叉树的二叉链表。中，试遍写算法建立该

37、二叉树的二叉链表。 BTNode* PreInCreat(char pre,char in,int n)/根据二叉树前序序列根据二叉树前序序列pre和中序序列和中序序列in建立二叉树。建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。是序列第一和最后元素下标。 char *p; int k; if(ndata=*pre; 前序为：前序为：A B E C D F A B E C D F 中序为：中序为：B E A D F CB E A D F C 二叉树遍历算法的应用(7) for(p=in;plchild=PreInCreat (pre+1,in,k)； /递归建立左子树递归建立左子

38、树 root-rchild=PreInCreat (pre+k+1,p+1,n-k-1)； /递归建立递归建立 / 左子树左子树 return b;/结束结束PreInCreat 前序为：前序为：A B E C D F A B E C D F 中序为：中序为：B E A D F CB E A D F C线索二叉树线索二叉树 线索二叉树的提出：线索二叉树的提出： 1、遍历的实质：非线性结构线性化（前驱、遍历的实质：非线性结构线性化（前驱、后继）后继）; 2、前驱和后继是在遍历中得到的、前驱和后继是在遍历中得到的; 3、知道前驱和后继，再遍历时就不需要栈、知道前驱和后继，再遍历时就不需要栈; 4、

39、可以在二叉链表结构中增加前驱和后继两、可以在二叉链表结构中增加前驱和后继两个指针域个指针域; 5、n个结点的二叉树有个结点的二叉树有n1个空指针，可以利个空指针，可以利用。用。线索二叉树线索二叉树 n个结点的二叉链表中含有个结点的二叉链表中含有n+1个空指针域，可以利用这个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息。这些附加的指些空指针域来存放结点的前驱和后继的信息。这些附加的指针称为针称为“线索线索”，加上了线索的二叉链表称为，加上了线索的二叉链表称为线索链表线索链表，加，加上线索的二叉树就是上线索的二叉树就是线索二叉树线索二叉树（Threaded Binary Tree）。

40、）。将二叉树变为线索二叉树的过程称为将二叉树变为线索二叉树的过程称为线索化线索化。 lchildltagdata rtag rchild指向结点前驱指向结点的左孩子lchildlchild:1:0ltag= 指向结点后继指向结点的右孩子rchildrchild:1:0rtag= 线索二叉树线索二叉树 线索化线索化只有空指针才能加线索只有空指针才能加线索线索化按某种遍历顺序进行线索化按某种遍历顺序进行前序前驱线索化前序前驱线索化w 前序前驱线索化前序前驱线索化ABECFGHIDABECFGHID中序（全）线索二中序（全）线索二叉树叉树NULLACFEDBNULLA 00E 11C 01D 11F

41、 11B 00NULLA 为方便起见，在线索链表中增加一个头结点，令其为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的根结点，域指向二叉树的根结点，rchild域指向访问序列的最域指向访问序列的最后一个结点，这样，就建立了一个后一个结点，这样，就建立了一个双向线索链表双向线索链表。Thrt01NULL后序（全）线索化后序（全）线索化AEDCBHGFAEDCBHGFnull类型定义typedef struct Node ElemTyte data; struct Node * *lchild, * *rchild; 左、右孩子指针左、右孩子指针 int ltag, rtag

42、; TBTNode; 前序线索化TBTNode *pre=null;/设置前驱设置前驱void PreOrderThread(TBTNode *T)if (T!=null) if (T-lchild=null) T-ltag=1; T-lchild=pre;/设置左线索设置左线索 if (T-rchild=null) T-rtag=1; /为建立右链作准备为建立右链作准备 if (pre!=null & pre-rtag=1) pre-rchild=T; /设置前驱的右线索；设置前驱的右线索； pre=T;/前驱后移前驱后移 if (T-ltag=0) PreOrderThread(T

43、-lchild); /左子树前序线索化左子树前序线索化 if (T-rtag=0) PreOrderThread(T-rchild); /右子树前序线索化右子树前序线索化 ACFDB中序线索化二叉树TBTNode *pre=null;/设置前驱设置前驱void InOrderThread(TBTNode *T)if (T) InOrderThread(T-lchild); /左子树中序线索化左子树中序线索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左线索为左线索为pre; if (T-rchild=null) T-rtag=1; /置右标记，为右

44、线索作准备置右标记，为右线索作准备 if (pre!=null & pre-rtag=1) pre-rchild=T; /给前驱加后继线索给前驱加后继线索 pre=T;/前驱指针后移前驱指针后移 InOrderThread(T-rchild); /右子树中序线索化右子树中序线索化 /结束结束InOrderThread ACFDB后序线索化二叉树TBTNode *pre=null;/设置前驱设置前驱void PostOrderThread(TBTNode *T)if (T) PostOrderThread(T-lchild); /左子树后序线索化左子树后序线索化 PostOrderThr

45、ead(T-rchild); /右子树后序线索化右子树后序线索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左线索为左线索为pre; if (T-rchild=null) T-rtag=1; /置右标记，为右线索作准备置右标记，为右线索作准备 if (pre!=null & pre-rtag=1) pre-rchild=T; /给前驱加后继线索给前驱加后继线索 pre=T;/前驱指针后移前驱指针后移 /结束结束PostOrderThread ACFDB线索二叉树的中序遍历w void InorderTraverseThr(TBTNode *

46、p)w while(p) 二叉树非空二叉树非空w while (p-ltag=0) p=p-lchild; 找中序序列的开始结点找中序序列的开始结点w coutdata;wwhile(p&p-rtag= =1) w p=p-rchild; coutdata;/找找P的中序后继结点的中序后继结点w if(p) p=p-rchild;w /whilew InorderTraverseThrACFEDB带头结点的线索二叉树的中序遍历w void InorderTraverseThr(TBTNode *thrt)w p=thrt-lchild;w while(p!=thrt) 二叉树非空二叉树

47、非空w while (p-ltag=0) p=p-lchild; 找中序序列的开始结点找中序序列的开始结点w coutdata;wwhile(p-rtag= =1 & p-rchild!=thrt)w p=p-rchild; coutdata;/找找P的中序后继结点的中序后继结点w p=p-rchild;w / while(p!=thrt) w InorderTraverseThr前序线索树上找前驱和后继找前驱：找前驱： 困难困难找后继找后继： 若结点有左子女，则左子女是后继；否则，若结点有左子女，则左子女是后继；否则，rchild指向后继。指向后继。A AB BE EC CF FG

48、GH HI ID D前序线索树上找后继TBTNode* PreorderNext(TBTNode *p) if (p-ltag= =0) 结点有左子女结点有左子女 return(p-lchild); 结点的左子女为其前序后继结点的左子女为其前序后继 else return(p-rchild) ; PreorderNext中序线索树上找前驱和后继 中序的前驱和后继都往上指向祖先找前驱：找前驱： 若左标记为若左标记为1，则，则lchild指向其前驱；否则，其指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。前驱是其左子树上按中序遍历的最后一个结点。找后继找后继： 若右标记为若右标记为1

49、，则，则rchild指向其后继；否则，指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点。其后继是其右子树上按中序遍历的第一个结点。ACFEDB中序线索树上找前驱TBTNode* InorderPre(TBTNode *p)TBTNode *q; if (p-ltag= =1) 结点的左子树为空结点的左子树为空 q=p-lchild; 结点的左指针域为左线索，指向其前驱结点的左指针域为左线索，指向其前驱 else q=p-lchild; p结点的中序前驱是左子树中最右边结点结点的中序前驱是左子树中最右边结点 while (q-rtag=0 ) q=q-rchild; if return

50、 (q); InorderPre中序线索树上找后继TBTNode* InorderNext(TBTNode *p)TBTNode *q; if (p-rtag= =1) 结点的右子树为空结点的右子树为空 q=p-rchild; 结点的右指针域为右线索，指向其后继结点的右指针域为右线索，指向其后继 else q=p-rchild; P结点的中序后继是其右子树中最左边结点结点的中序后继是其右子树中最左边结点 while (q-ltag=0 ) q=q-lchild; if return (q); InorderNext后序线索树上找前驱和后继找前驱：找前驱： 若结点有右子女，则右子女是其前驱；否若

51、结点有右子女，则右子女是其前驱；否则，则，lchild指向其前驱。指向其前驱。找后继找后继： 困难，需要知道其双亲。困难，需要知道其双亲。AEDCBHGFnull后序线索树上找前驱TBTNode* PostorderPre(TBTNode *p) if (p-rtag= =0) 结点有右子女结点有右子女 return(p-rchild); 结点的右子女为其后序前驱结点的右子女为其后序前驱 else return(p-lchild) ; PreorderPre线索化二叉树比较 中序线索二叉树在遍历、中序线索二叉树在遍历、求前驱、后继上要优于前序和求前驱、后继上要优于前序和后序，最有价值。后序，最

52、有价值。线索树上结点的插入与删除 线索二叉树虽然在找前趋结点和后继线索二叉树虽然在找前趋结点和后继结点时优于非线索二叉树，但一般情况下，结点时优于非线索二叉树，但一般情况下，在线索二叉树上进行插入和删除操作时，在线索二叉树上进行插入和删除操作时，都会破坏线索。这样一来，都会破坏线索。这样一来，除修改结点指除修改结点指针外，还需要修改线索。针外，还需要修改线索。与非线索二叉树与非线索二叉树相比，时间消耗大。相比，时间消耗大。中序线索二叉树上插入结点 以中序线索二叉树为例，仅讨论一下插以中序线索二叉树为例，仅讨论一下插入结点的算法。入结点的算法。设一个结点设一个结点x ,x ,插入到线索二插入到线

53、索二叉树的某一结点叉树的某一结点y y与与y y的右孩子之间，作为的右孩子之间，作为y y的的右子树的根结点。右子树的根结点。 插入后在中序序列里插入后在中序序列里x x是是y y的后继。的后继。yyxxACFEDByyGxx中序线索二叉树上插入结点存在两种情况：存在两种情况： 1 1、y y原来的右子树为空，则原来的右子树为空，则x x插入后，一定是插入后，一定是一个叶子结点。一个叶子结点。 2 2、y y原来的右子树非空，则原来的右子树作为原来的右子树非空，则原来的右子树作为x x的右子树。的右子树。 无论哪种情况，无论哪种情况，x x的左子树均为空的左子树均为空，它是作为，它是作为y y

54、的中序后继结点插入的。如果的中序后继结点插入的。如果y y不是中序序列的终端不是中序序列的终端结点，那么它原来应该有一个后继结点结点，那么它原来应该有一个后继结点n,n,插入结点插入结点x x 后，后，n n就变成了就变成了x x的后继结点。的后继结点。 中序线索二叉树上插入结点1 1、y y原来的右子树为空原来的右子树为空yyxxRRN N1 1 插入前插入前yyxxRRN N1 1 插入后插入后x-ltag=1;x-rtag=1;x-lchild=y;x-rchild=y-rchild;y-rchild=x;y-rtag=0;中序线索二叉树上插入结点2 2、y y原来的右子树非空原来的右子

55、树非空yyxx插入前插入前N Nk kNN1 1pp插入后插入后N Nk kNN1 1ppyyxxx-rchild=y-rchild;x-ltag=1;x-lchild=y;y-rchild=x;从从N1开始找以开始找以N1为根为根的子树最左边的结点的子树最左边的结点pif(p-ltag=1) p-lchild=x;树的存储结构w考虑存储结构时，主要考虑逻辑结构：n数据元素n数据元素之间的关系w树的存储结构树的存储结构：n顺序存储结构n链式存储结构树的存储结构ABECDFw双亲表示法双亲表示法 w孩子表示法孩子表示法 w孩子兄弟表示法孩子兄弟表示法 双亲表示法w 使用静态数组（本质是静态链表）

56、静态数组（本质是静态链表）；w 数组的每个数据元素，包括两个域：一个域是数据元素数据元素；另一个域用游标指示该结点的双亲结点在数组中的相对位置位置；根结点的游标为-1。w 特点：n方便找结点的双亲双亲；n顺序存储结构；双亲表示法类型定义#define MAX_NODE 64typedef struct Ptnode ElemTyte data; 数据域 int parent; 双亲指示域 PTreeMAX_NODE;双亲表示示例FGHIABCED数组下标数组下标 0 1 2 3 4 5 6 7 8 data A B C D E F G H Iparent -1 0 0 0 1 1 1 3 3双

57、亲表示法表示的树的深度w int Depth(PTree t)w int maxdepth=0;w for(i=0;i=0) / 求结点求结点i的深度的深度w temp+; f=tf.parent; w if(tempmaxdepth) maxdepth=temp; /最大深度更新最大深度更新w w return(maxdepth); /返回树的深度返回树的深度w /结束结束Depth孩子表示法w 任一数据元素，有任一数据元素，有0个或多个孩子；个或多个孩子；w 因此可以设计一个链式存储结构，其结点除因此可以设计一个链式存储结构，其结点除放置数据元素外，还放置若干指针，分别用放置数据元素外，还

58、放置若干指针，分别用来指示该结点的所有孩子结点在存储空间中来指示该结点的所有孩子结点在存储空间中的位置。的位置。孩子表示法w 方法方法1 1n根据结点的度，设置结点的指针个数，比如若根据结点的度，设置结点的指针个数，比如若结点的度为结点的度为d:d:datachild1child2childd问题问题：n不同的数据元素，结点构造不同；不同的数据元素，结点构造不同；n操作不方便操作不方便孩子表示法w 方法方法2 2n按照树的度定义结点。若树的度为按照树的度定义结点。若树的度为d,定义定义degree，表示该结点的度，表示该结点的度datachild1child2childddegree问题问题：

59、n因因degree为树的度，是所有结点的最大的度，为树的度，是所有结点的最大的度，因此树中有相当部分的指针域为空，浪费空间。因此树中有相当部分的指针域为空，浪费空间。n有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有 n(k-1)+1个。个。孩子表示法w 有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有n(k-1)+1个。个。w 证明：证明：nn个结点的树，除根结点外，每个结点有一个指针个结点的树，除根结点外，每个结点有一个指针指向，也就是树中有指向，也就是树中有n-1个有效链域（指针）个有效链域（指针）n而按该结点定义，而按该结点定义，n个结点总的指针域个结点

60、总的指针域有：有：nk个。个。n因此空链域：因此空链域：nk (n-1) = n ( k - 1 ) + 1w 一个静态数组，存放所有的结点一个静态数组，存放所有的结点w 数组的每个数据元素，包括两部分：数数组的每个数据元素，包括两部分：数据元素，指针；指针指向一个链表，链据元素，指针；指针指向一个链表，链表结点的数据域是一个整数，表示该结表结点的数据域是一个整数，表示该结点的孩子在数组中的相对位置；点的孩子在数组中的相对位置；w 特点：特点：n顺序顺序+链式存储结构；链式存储结构；n找孩子容易，找双亲难找孩子容易，找双亲难；孩子表示法孩子表示法孩子表示法0123456546ABCDEFG312ACFEDBG双亲孩子链表0123456546312GABCDE