第五章 树 5.1 树的定义 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 定义 第五章 树 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 5.1 树的定义 定义 定义：树(tree)是n(n>0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点——根 树中各子树是互不相交的集合

A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树

基本术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m0)棵互不相交的树的集合 树中同一层各结点从左至右看成是有序的（即不能互换），则称该树为有序树，否则称为无序树。

结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点I的双亲：D 结点L的双亲：E 结点A的孩子：B，C，D 结点B的孩子：E，F A B C D E F G H I J K L M 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先 结点A的层次：1 结点M的层次：4

5.2 二叉树 定义 定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态  空二叉树 A 只有根结点 的二叉树 A B 右子树为空 A B 左子树为空 A B C 左、右子树 均非空

几种特殊形式的二叉树 满二叉树 完全二叉树 定义： 特点：每一层上的结点数都是最大结点数 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~ 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1

1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 4 5 6 7 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6

二叉树性质 性质2：深度为k的二叉树至多有 个结点(k1) 性质3：对任何一棵二叉树T，如果其终端结点数为n0， 度为2的结点数为n2，则n0=n2+1 性质4：具有n个结点的完全二叉树的深度为

性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2 (2) 如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1

二叉树性质 性质1： 性质2：深度为k的二叉树至多有 个结点(k1) 证明：用归纳法证明之 i=1时，只有一个根结点， 是对的 假设对所有j(1j<i)命题成立，即第j层上至多有 个结点 那么，第i-1层至多有　　 个结点 又二叉树每个结点的度至多为2  第i层上最大结点数是第i-1层的2倍，即　 故命题得证 性质2：深度为k的二叉树至多有 个结点(k1) 证明：由性质1，可得深度为k 的二叉树最大结点数是

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明：n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1

5.3 树的存储结构 树的存储结构 typedef struct node { datatype data; int parent; 双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难 typedef struct node { datatype data; int parent; }JD; JD t[M];

0号单元不用或 存结点个数 a b c d e f h g i 6 1 2 3 4 5 7 8 9 data parent 9 a c d e f g h i b 1 1 2 2 3 5 5 如何找孩子结点 5

孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D data child1 child2 ………. childD data degree child1 child2 ………. childd 孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表 孩子结点：typedef struct node { int child; //该结点在表头数组中下标 struct node *next; //指向下一孩子结点 }JD; 表头结点：typedef struct tnode { datatype data; //数据域 struct node *fc; //指向第一个孩子结点 }TD; TD t[M]; //t[0]不用

a b c d e f h g i 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 ^ 4 5 ^ 6 ^ ^ 9 7 8 ^ ^ ^ ^ 如何找双亲结点 ^

带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc ^ parent a b c d e f h g i

孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点 操作容易 破坏了树的层次 typedef struct node { datatype data; struct node *fch, *nsib; }JD; a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11

在n个结点的二叉链表中，有n+1个空指针域 链式存储结构 二叉链表 typedef struct BiTNode{   TElemType        data;   Struct BiTNode   * lchild, * rchild;  //左右孩子指针 }BiTNode, * BiTree; lchild data rchild A B C D E F G ^ A B C D E F G ^ ^ ^ ^ ^ ^ ^ 在n个结点的二叉链表中，有n+1个空指针域

建立一棵二叉树 Status CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树， //构造二叉链表表示的二叉树T。 scanf(&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; }//CreateBiTree

三叉链表 typedef struct node {TElemType data; struct node *lchild, *rchild, *parent; }JD; lchild data parent rchild A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^

5.4 树和二叉树的遍历 树的遍历 遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列 常用方法 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点

A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E 先序遍历： A B E F I G C D H J K L N O M 后序遍历： E I F G B C J K N O L M H D A 层次遍历： A B C D E F G H I J K L M N O

二叉树的遍历 方法 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点 D L R LDR、LRD、DLR RDL、RLD、DRL

先序遍历 void PreOrderTraverse(BiTNode *Node) { if(Node!=NULL) printf("%c",Node->data); PreOrderTraverse(Node->lchild); PreOrderTraverse(Node->rchild); }

先序遍历: 先序遍历序列：A B D C D L R D L R A D L R A D B C B > D L R C >

中序遍历 void InOrderTraverse(BiTNode *Node) { if(Node!=NULL) InOrderTraverse(Node->lchild); printf("%c",Node->data); InOrderTraverse(Node->rchild); }

中序遍历: 中序遍历序列：B D A C L D R L D R A L D R A D B C > L D R B > C

后序遍历 void PostOrderTraverse(BiTNode *Node) { if(Node!=NULL) PostOrderTraverse(Node->lchild); PostOrderTraverse(Node->rchild); printf("%c",Node->data); }

后序遍历: 后序遍历序列： D B C A L R D A A L R D L R D C B D > B > > C

- + a * b - c d / e f a + b * c - d - e / f a b c d - * + e f / - - + 先序遍历： a + b * c - d - e / f 中序遍历： a b c d - * + e f / - 后序遍历： 层次遍历： - + / a * e f b - c d

编程练习 求二叉树的深度 求二叉树中叶子结点的数目 交换所有结点的左右子树

求二叉树的深度 int depth(BiTNode *Node){ int dep1,dep2; //若T为空树，则深度为0， //否则其深度等于左子树或右子树的最大深度加1 if(Node==NULL) return 0; else { dep1=depth(Node->lchild); dep2=depth(Node->rchild); return dep1>dep2?dep1+1:dep2+1; }

求二叉树中叶子结点的数目 int LeafCount(BiTNode *Node) { if(Node==NULL) return 0; //空树没有叶子 else if(!Node->lchild&&!Node->rchild) return 1; //叶子结点 else return LeafCount(Node->lchild)+LeafCount(Node->rchild); //左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree

交换所有结点的左右子树 void Bitree_Revolute(BiTNode *Node) { BiTNode *NodeTemp; NodeTemp=Node->rchild; Node->rchild=Node->lchild; Node->lchild=NodeTemp; //交换左右子树 if(Node->lchild) Bitree_Revolute(Node->lchild); if(Node->rchild) Bitree_Revolute(Node->rchild); //左右子树再分别交换各自的左右子树 }//Bitree_Revolute

谢 谢！

void preorder(BiTNode *bt) { if(bt!=NULL) { printf("%d\t",bt->data); preorder(bt->lchild); preorder(bt->rchild); } T A printf(A); pre(T L); A pre(T R); T B printf(B); pre(T L); T C printf(C); pre(T L); B C T > 左是空返回 pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回 主程序 Pre( T ) 返回 pre(T R); 返回 返回 先序序列：A B D C pre(T R); 返回

Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ 1)中序遍历的非递归算法 算法: Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ InitStack(S); // 置空栈 p = T ; // 变量P代替根结点T，起保护根的作用 while ( p ∥! StackEmpty(s)) { // 当结点P存在或栈S不空时重复 if (p) { Push( S, P ); P = P->Lchild;} else { （P为空） Pop(s, p ) ; // 栈不空，退栈 if (! Visit (P->data)) return ERROR; // 若P不存在则错 P = P-> rchild ; // 得到右孩子结点，遍历右子树 } } //while return OK;

ADR B （D） 0 （B） 0 （A） 0 2)后序遍历的非递归算法 (S) 在设计算法前，我们先分析一下后序遍历 与其它遍历有何不同。从先、中序遍历 过程中可以看出每个结点都只需进一次栈。 但，后序遍历的过程中每个结点都必须进 两次栈。第一次进栈保存是为了 遍历该结点的左子树；第二次进栈 保存是为了遍历该结点的右子树； 只有结点第二次从栈中退出时， 才能访问该结点。因而，必须设置 能区分结点两次进栈的标志。设置 标志的方法不是唯一的，在实际应 用中一般都在栈中设置标志位B。 A B C D E F G H I J ADR B （D） 0 （B） 0 （A） 0

（I） 0 （G） 0 （D） 0 （D） 1 （B） 0 （B） 0 （A） 0 （A） 0 图6-15后序遍历的非递归 当某结点第一次进栈时，其标志位置0，第二次进栈时，其标志位置1。当从栈中退出某结点时，同时将其标志位的值退出。然后，通过判别从栈中退出的标志位的值是0、还是1，来决定是否能访问当前结点。是1，则访问该结点。是0，则再将结点进栈，同时， 将标志为置1。如右图6.14D进栈后，应遍历其左子树，但D无左孩子。 ADR B ADR B 此时将结点D与其标志位值0从栈中退出。经过判别不能访问，则将D再次进栈，同时把其标志位置1。然后，遍历D的右子树。 后序遍历的非递归算法: A （I） 0 （G） 0 B C （D） 0 （D） 1 D E F （B） 0 （B） 0 G H （A） 0 （A） 0 I J 图6-15后序遍历的非递归

Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ IniStack(S); // 置空栈 p = T ; // 变量P代替根结点T，起保护根的作用 while ( p ∥! StackEmpty(s)) { // 当结点P存在或栈S不空时重复 if (p) { Push( S, P,B ) // P存在将P进栈， B =0 P = P->Lchild;} // 遍历左子树 else { // P为空 Pop(s, p ,B) ; // 栈不空，退栈 if ( B==0) {Push( S, P,B ); ( B = 1) P = P-> rchild ;} // 遍历右子树 else { if (! Visit (P->data)) return ERROR; // 若P不存在 ，则错 P=null;} } } //while return OK; } PostorderTraverse

非递归算法 A B C D E F G p i P->A (1) A B C D E F G p i P->A P->B (2) A B C D E F G p i P->A P->B P->C (3) p=NULL A B C D E F G i P->A P->B 访问：C (4)

p A B C D E F G i P->A 访问：C B (5) A B C D E F G i P->A P->D 访问：C B p (6) A B C D E F G i P->A P->D P->E 访问：C B p (7) A B C D E F G i P->A P->D 访问：C B E p (8)

A B C D E F G i P->A P->D P->G 访问：C B E P=NULL (9) A B C D E F G i P->A P->D 访问：C B E G p (10) A B C D E F G i P->A P->F 访问：C B E G D p (12) A B C D E F G i P->A 访问：C B E G D p (11)

Ch5_4.c Ch5_40.C A B C D E F G i 访问：C B E G D F A p (14) A B C D E F G p=NULL (13) A B C D E F G i 访问：C B E G D F A p=NULL (15) 后序遍历非递归算法 Ch5_4.c Ch5_40.C

层次遍历 Status LevelOrder(BiTree T){   //按层次遍历二叉树T， Q为队列   InitQueue(Q);   If (T!=NULL){// 若树非空       EnQueue(Q,T);//根结点入队列       While (!QueueEmpty(Q)){         DeQueue(Q,b);     //队首元素出队列       Visit(b->data);   //访问结点         If (b->lchild!=NULL) EnQueue(Q,b->lchild);//左子树非空，则入队列         If (b->rchold!=Null) EnQueue(Q,b->rchild);//右子树非空，则入队列       }//while   }//if }LevelOrder

两棵树相似 若已知两棵二叉树B1和B2皆为空，或者均不为空且B1的左右子树和B2的左右子树分别相似，则称二叉树B1和B2相似。

判断两棵树是否相似的递归算法 int Bitree_Sim(Bitree B1,Bitree B2) {   if(!B1&&!B2) return 1;   else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))     return 1;   else return 0; }//Bitree_Sim

先序遍历二叉树的非递归算法 void PreOrder_Nonrecursive(Bitree T） {   InitStack(S);   Push(S,T); //根指针进栈   while(!StackEmpty(S))   {     while(Gettop(S,p)&&p)     {       visit(p->data);       push(S,p->lchild);     } //向左走到尽头     pop(S,p);     if(!StackEmpty(S))     {      pop(S,p);      push(S,p->rchild); //向右一步     }   }//while }//PreOrder_Nonrecursive

求二叉树T中结点p和q的最近共同祖先

int found=FALSE; Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q) {   Bitree pathp[ 100 ],pathq[ 100 ] //设立两个辅助数组暂存从根到p,q的路径   Findpath(T,p,pathp,0);   found=FALSE;   Findpath(T,q,pathq,0); //求从根到p,q的路径放在pathp和pathq中   for(i=0;pathp[i]==pathq[i]&&pathp[i];i++); //查找两条路径上最后一个相同结点   return pathp[--i]; }//Find_Near_Ancient void Findpath(Bitree T,Bitree p,Bitree path[ ],int i)//求从T到p路径的递归算法 {   if(T==p)   {     found=TRUE;     return; //找到   }   path[i]=T; //当前结点存入路径   if(T->lchild) Findpath(T->lchild,p,path,i+1); //在左子树中继续寻找   if(T->rchild&&!found) Findpath(T->rchild,p,path,i+1); //在右子树中继续寻找   if(!found) path[i]=NULL; //回溯 }//Findpath

判断二叉树是否完全二叉树,是则返回1,否则返回0

int IsFull_Bitree(Bitree T {   InitQueue(Q);   flag=0;   EnQueue(Q,T); //建立工作队列   while(!QueueEmpty(Q))   {     DeQueue(Q,p);     if(!p) flag=1;     else if(flag) return 0;     else     {       EnQueue(Q,p->lchild);       EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列     }   }//while   return 1; }//IsFull_Bitree 分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.

按先序遍历序列建立二叉树的二叉链表，已知先序序列为： 遍历算法应用 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C   D E  G   F    A B C D E F G A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ 统计二叉树中叶子结点个数算法 求二叉树深度算法 Ch5_1.c Ch5_5.c ch5_6.c

5.5 二叉树的应用 哈夫曼树(Huffman)——带权路径长度最短的树 定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~ 路径长度：路径上的分支数 树的路径长度：从树根到每一个结点的路径长度之和 树的带权路径长度：树中所有带权结点的路径长度之和 Huffman树——设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫~

a b c d 7 5 2 4 d c a b 2 4 7 5 WPL=7*2+5*2+2*2+4*2=36 a b c d 7 5 2 4 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 a b c d 7 5 2 4 d c a b 2 4 7 5 WPL=7*2+5*2+2*2+4*2=36 a b c d 7 5 2 4 WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35

构造Huffman树的方法——Huffman算法 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森林中 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树

例 a 7 b 5 c 2 d 4 a 7 b 5 c 2 d 4 6 a 7 b 5 c 2 d 4 6 11 18 a 7 b 5 c 2 d 4 6 11

例 w={5, 29, 7, 8, 14, 23, 3, 11} 29 14 8 7 15 11 3 5 19 23 42 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 11 3 5 8 19 23 42 29 14 7 15 58 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 23 42 29 14 7 15 58 100 11 3 5 8 19 29 23 14 7 15

unsigned int parent,lchild,rchild; }HTNode; /*树中结点的结构*/ Huffman算法实现 一棵有n个叶子结点的Huffman树有2n-1个结点 采用顺序存储结构——一维结构数组 结点类型定义 typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode; /*树中结点的结构*/ typedef struct { char data; /*待编码的字符*/ int weight; /*字符的权值 */ char code[N]; /*字符的编码 */ } HTCode; Ch5_8.c

lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 0 0 0 7 5 2 4 0 0 0 (1) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 0 0 7 5 2 4 6 0 0 0 0 0 0 4 0 0 0 0 5 5 0 0 0 k x1=3,x2=4 m1=2,m2=4 (2) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 0 7 5 2 4 6 11 0 0 0 0 0 4 5 0 0 6 5 5 6 0 0 k x1=2,x2=5 m1=5,m2=6 (3) lc data rc pa 1 2 3 4 5 6 7 0 0 0 0 3 2 1 7 5 2 4 6 11 18 0 0 0 0 4 5 6 7 6 5 5 6 7 0 k x1=1,x2=6 m1=7,m2=11 (4) Ch5_8.c

Huffman树应用 最佳判定树 E A D C 等级 分数段 比例 A B C D E 0~59 60~69 70~79 80~89 90~100 0.05 0.15 0.40 0.30 0.10 a<60 a<90 a<80 a<70 E Y N D C B A 70a<80 a<60 C Y N B D E A 80a<90 60a<70 a<80 a<70 a<60 a<90 E Y N D C B A

Huffman编码：数据通信用的二进制编码 思想：根据字符出现频率编码，使电文总长最短 编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列 例 要传输的字符集 D={C,A,S,T, ; } 字符出现频率 w={2,4,2,3,3} C S 3 6 4 2 8 14 T ; A 1 T : 00 ; : 01 A : 10 C : 110 S : 111

译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束 C S 3 6 4 2 8 14 T ; A 1 T : 00 ; : 01 A : 10 C : 110 S : 111 例 电文是{CAS;CAT;SAT;AT} 其编码 “11010111011101000011111000011000” 电文为“1101000” 译文只能是“CAT”

线索二叉树 定义： 实现 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~ 线索：指向前驱或后继结点的指针称为~ 线索二叉树：加上线索的二叉链表表示的二叉树叫~ 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~ 实现 在有n个结点的二叉链表中必定有n+1个空链域 在线索二叉树的结点中增加两个标志域 lt :若 lt =0, lc 域指向左孩子；若 lt=1, lc域指向其前驱 rt :若 rt =0, rc 域指向右孩子；若 rt=1, rc域指向其后继 结点定义： typedef struct node { int data; int lt, rt; struct node *lc, *rc; }JD; lc lt data rt rc

A B D C E T 先序序列：ABCDE 先序线索二叉树 A B C D E 1 1 1 1 1 1 ^

A B D C E T 中序序列：BCAED 中序线索二叉树 A B C D E ^ 1 1 ^ 1 1 1 1

A B D C E T 后序序列：CBEDA 后序线索二叉树 A B C D E 1 1 ^ 1 1 1 1

A B D C E T 中序序列：BCAED 中序线索二叉树 1 ^ A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 头结点： lt=0, lc指向根结点 rt=1, rc指向遍历序列中最后一个结点 遍历序列中第一个结点的lc域和最后 一个结点的rc域都指向头结点

算法 i P->A A B C D E 按中序线索化二叉树 pr t 0 1 A B D C E bt ^ p Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); i P->A A B C D E 算法 按中序线索化二叉树 pr t 0 1 A B D C E bt ^ p Ch5_20.c

算法 i P->A P->B A B C D E 按中序线索化二叉树 pr t 0 1 A B D C E bt ^ p JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); i P->A P->B A B C D E 算法 按中序线索化二叉树 pr t 0 1 A B D C E bt ^ p Ch5_20.c

算法 A B C D E i P->A P->B 按中序线索化二叉树 pr t 0 1 A B D C E bt ^ JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E i P->A P->B 算法 按中序线索化二叉树 pr t 0 1 A B D C E bt ^ P=NULL Ch5_20.c

算法 P->A A B C D E 按中序线索化二叉树 i pr t 0 1 A B D C E bt ^ P 1 Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); P->A A B C D E 算法 按中序线索化二叉树 i pr t 0 1 A B D C E bt ^ P 1 Ch5_20.c 输出:B

算法 A B C D E 按中序线索化二叉树 P->A i P->C t 0 1 A B D C E bt ^ 1 pr P JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 P->A i P->C t 0 1 A B D C E bt ^ 1 pr P Ch5_20.c 输出:B

算法 A B C D E P->A 按中序线索化二叉树 i P->C t 0 1 A B D C E bt ^ 1 pr JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E P->A 算法 按中序线索化二叉树 i P->C t 0 1 A B D C E bt ^ 1 pr 输出:B Ch5_20.c P=NULL

算法 A B C D E 按中序线索化二叉树 P->A i t 0 1 A B D C E bt ^ 1 pr P 1 JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 P->A i t 0 1 A B D C E bt ^ 1 pr P 1 Ch5_20.c 输出: B C

算法 A B C D E 按中序线索化二叉树 P->A i t 0 1 A B D C E bt ^ 1 pr Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 P->A i t 0 1 A B D C E bt ^ 1 pr Ch5_20.c 输出: B C P=NULL

算法 A B C D E 按中序线索化二叉树 i t 0 1 A B D C E bt ^ P 1 pr 1 Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i t 0 1 A B D C E bt ^ P 1 pr 1 Ch5_20.c 输出: B C A

算法 A B C D E 按中序线索化二叉树 i P->D t 0 1 A B D C E bt ^ pr 1 P Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i P->D t 0 1 A B D C E bt ^ pr 1 P Ch5_20.c 输出: B C A

算法 A B C D E 按中序线索化二叉树 i P->E P->D t 0 1 A B D C E bt ^ pr 1 P JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i P->E P->D t 0 1 A B D C E bt ^ pr 1 P Ch5_20.c 输出: B C A

算法 A B C D E 按中序线索化二叉树 i P->E P->D t 0 1 A B D C E bt ^ pr 1 JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i P->E P->D t 0 1 A B D C E bt ^ pr 1 P=NULL Ch5_20.c 输出: B C A

算法 A B C D E 按中序线索化二叉树 i P->D t 0 1 A B D C E bt ^ pr 1 P 1 JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i P->D t 0 1 A B D C E bt ^ pr 1 P 1 Ch5_20.c 输出: B C A E

算法 A B C D E 按中序线索化二叉树 i P->D t 0 1 A B D C E bt ^ 1 pr 输出: B C A E JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i P->D t 0 1 A B D C E bt ^ 1 pr 输出: B C A E P=NULL Ch5_20.c

算法 A B C D E 按中序线索化二叉树 i t 0 1 A B D C E bt ^ 1 P pr 1 Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); A B C D E 算法 按中序线索化二叉树 i t 0 1 A B D C E bt ^ 1 P pr 1 Ch5_20.c 输出: B C A E D

算法 按中序线索化二叉树 A B C D E i t 0 1 A B D C E bt ^ 1 pr 1 P=NULL Ch5_20.c JD *zxxsh(JD *bt) { JD *p,*pr,*s[M],*t; int i=0; t=(JD *)malloc(sizeof(JD)); t->lt=0; t->rt=1; t->rc=t; if(bt==NULL) t->lc=t; else { t->lc=bt; pr=t; p=bt; do{ while(p!=NULL) { s[i++]=p; p=p->lc; } if(i>0) { p=s[--i]; printf("%c ",p->data); if(p->lc==NULL) { p->lt=1; p->lc=pr;} if(pr->rc==NULL) { pr->rt=1; pr->rc=p;} pr=p; p=p->rc; } }while(i>0||p!=NULL); pr->rc=t; pr->rt=1; t->rc=pr; return(t); 算法 按中序线索化二叉树 A B C D E i t 0 1 A B D C E bt ^ 1 pr 1 P=NULL Ch5_20.c 输出: B C A E D

算法 按中序线索化二叉树 A B C D E A B D C E t 0 1 1 Ch5_20.c 输出: B C A E D

算法 按中序线索化二叉树 遍历中序线索二叉树 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 A B C D E 在中序线索二叉树中找结点后继的方法： （1）若rt=1, 则rc域直接指向其后继 （2）若rt=0, 则结点的后继应是其右子树的左链尾（lt=1)的结点 在中序线索二叉树中找结点前驱的方法： （1）若lt=1, 则lc域直接指向其前驱 （2）若lt=0, 则结点的前驱应是其左子树的右链尾（rt=1)的结点 Ch5_20.c

二叉排序树 定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树： 二叉排序树的插入 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树 二叉排序树的插入 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树

中序遍历二叉排序树可得到一个关键字的有序序列 插入算法 例 {10， 18， 3， 8， 12， 2， 7， 3} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 10 18 3 8 12 2 7 Ch5_9.c 中序遍历二叉排序树可得到一个关键字的有序序列

要删除二叉排序树中的p结点，分三种情况： 二叉排序树的删除 要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改p双亲f的指针f->lchild=NULL f->rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p (1)(2) p只有右子树，用p的右孩子代替p (3)(4) p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5) 若C无右子树，用C取代p (6)

S P PL Q 中序遍历：PL P S Q 中序遍历：PL S Q (1) S Q PL P 中序遍历：Q S PL P 中序遍历：Q S PL (2)

中序遍历：P PR S Q S PR Q 中序遍历：PR S Q (3) P 中序遍历：Q S P PR S Q PR 中序遍历：Q S PR (4) P

F P C PR CL Q QL S SL 中序遍历：CL C ……QL Q SL S P PR F 中序遍历：CL C ……QL Q SL S PR F (5) F P C PR CL 中序遍历：CL C P PR F 中序遍历：CL C PR F (6)

删除算法 例 80 50 120 60 110 150 55 70 53 80 60 120 110 150 55 70 53 80 55 120 110 150 53 70 删除50 删除60 10 4 25 8 13 5 8 4 25 5 13 8 4 25 13 删除5 删除10 Ch5_10.c