chapter树和二叉树实用.pptx

6.1 树6.1.1 树的定义（1）定义 树（Tree）：是n（n0）个结点的有限集。定义一：（递归定义）：在任意一棵非空树中，有且仅有一个特定的称为根（root）的结点；当n1时，其余结点可分为m（m0）个互不相交的有限集 T1,T2,Tm，其中每一个集合本身又是一棵树。并且 T1,T2,Tm，称为根的子树（SubTree）。定义二：（形式定义）任何一棵树是一个二元组Tree=(root,F)。其中：root是数据元素，称做树的根结点；F是m（m0）棵树的森林，F（T1,T2,Tm），其中Ti=(ri,Fi)称做根root的第i棵子树；当m0 时，在树根和其子树森林之间存在下列关系：RF=|i=1,2,m;m 0第1页/共63页（2）表示形式 该树有13个结点。其中，A是树根，其余结点分成3个互不相交的子集：T1=B,E,F,K,L，T2=C,G，T3=D,H,I,J,M;T1、T2和T3都是A的子树，其本身也是一棵树。层次A 1B C D 2E F G H I J 3K L M 4 图6.1一般的树第2页/共63页该树又可表示为如下三种形式：(a)嵌套集合表示(c)凹入表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)(b)广义表表示 ABCDEFGHIJKLMABCDEFGHIJKLM图6.2树的其他3种表示法 第3页/共63页（3）树的抽象数据类型定义 ADT Tree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若Droot，则存在Droot的一个划分D1,D2,Dm(m0),对任意jk(1j,km)有DjDk，且对任意的i(1im)，唯 一存在数据元素xiDi，有H；（3）对应于Droot的划分，H,有唯一 的一个划分H1,H2,Hm(m0)，对任意jk(1j,km)有 HjHk，且对任意i(1im)，Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。基本操作：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。第4页/共63页 CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree(&T);初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。第5页/共63页 Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。InsertChild(&T,&P,i,c);初始条件：树T存在，p指向T中某个结点，1ip所指结点的度1，非空 树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。DeleteChild(&T,&P,i);初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除T中p所指结点的第i棵子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ADT Tree第6页/共63页6.1.2 基本术语 结点：包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个圆圈。结点的度（Degree）：结点拥有的子树树。叶子（或终端结点）（Leaf）：度为0的结点。即没有子树的结点。分支结点（或非终端结点）：度不为0的结点。内部结点：除根结点之外的分支结点。树的度：树内各结点的度的最大值。孩子（Child）：结点的子树的根，称为该结点的孩子。双亲（Parent）：结点的子树的根，称为该结点的孩子，该结点称为孩子的双亲。兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。第7页/共63页子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。森林（Forest）：是m（m0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。层次（Level）：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第k层，则其子树的根就在第k1层。堂兄弟：其双亲在同一层的结点互为堂兄弟。深度（高度）（Depth）：树中结点的最大层次。有序树：若将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。第8页/共63页6.2 二叉树6.2.1 二叉树的定义（1）定义 二叉树（Binary Tree）：是另一种树型结构。特点：每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。子树有左右之分，其次序不能任意颠倒。（2）图形表示 (a)(b)(c)(d)(e)图6.3二叉树的5种基本形态(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(d)左、右子树均非空的二叉树(e)左子树为空的二叉树第9页/共63页（3）二叉树的抽象数据类型定义 H，且存在Dl上的关系Hr H；H=,Hl,Hr；（4）(Dl,Hl)是一棵符合本定义的二叉树，称为根的左子树，(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。基本操作：ADT BinaryTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称BinaryTree为空二叉树；若D，则R=H,H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若Droot，则存在Droot=Dl,Dr，Dl且Dm=；（3）若Dl，则Dl中存在唯一的元素x1，有H，且存在Dl 上的关系Hl H;若 Dr,则Dr中存在唯一的元素xr,有 InitBiTree(&T);操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。第10页/共63页 CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree(&T);初始条件：二叉树T存在。操作结果：将二叉树T清为空树。BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。BiTreeDepth(T);初始条件：二叉树T存在。操作结果：返回T的深度。Root(T);初始条件：二叉树T存在。操作结果：返回T的根。Value(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的值。Assign(T,&e,value);初始条件：二叉树T存在，e是T中某个结点。操作结果：结点e赋值为value。第11页/共63页 Parent(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。LeftSibling(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。RightSibling(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。InsertChild(T,P,LR,c);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉 树c与T不相交且右子树为空。操作结果：根据LR为0或1，插入c为T中p指结点的左或右子树。p所指 结点的原有左或右子树则成为c的右子树。第12页/共63页 DeleteChild(T,P,LR);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。PreOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：先序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：中序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：后序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。LevelOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：层序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。ADT BinaryTree第13页/共63页（4）特殊形态的二叉树满二叉树：一棵深度为k且有2k1个结点的二叉树称为满二叉树。特点：每一层上的结点数都是最大结点数。完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l1。8 9 10 11 12 13 14 15 12 34 5 6 7(a)满二叉树(b)完全二叉树8 9 10 11 12 12 34 5 6 7第14页/共63页图6.4特殊形态的二叉树6 7 1 12 3 2 34 5 4 5 6(c)非完全二叉树 (d)非完全二叉树第15页/共63页6.2.2 二叉树的性质性质一：在二叉树的第i层上至多有2i-1个结点，(i1)。性质二：深度为k的二叉树至多有2k1个结点，(k1)。性质三：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结 点数为n2，则n0=n2+1。性质四：具有n个结点的完全二叉树的深度为 。）性质五：如果一棵有n个结点的完全二叉树（其深度为的结点按层序编号(从第1层到第 到右),则对任一结点i(1in),有层，每层从左（1）如果i1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT(i)是结点 。（2）如果2i n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。（3）如果2i1 n，则结点i无右孩子；否则其右孩子 RCHILD(i)是结点2i1。第16页/共63页6.3 二叉树的存储结构6.3.1 顺序存储结构 /-二叉树的顺序存储表示-#define MAX_TREE_SIZE100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTree bt;用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i1的分量中。例如，图6.5所示为图6.4(b)所示完全二叉树和图6.4(c)所示二叉树的顺序存储结构。图6.5二叉树的顺序存储结构1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 0 0 0 0 6 7(a)完全二叉树(b)一般二叉树图中以“0”表示不存在此结点第17页/共63页结点结构 lchild data rchild其中，data：数据域；lchild：左指针域，指向该结点的左孩子；rchild：右指针域，指向该结点的右孩子。6.3.2 链序存储结构（1）二叉链表定义 二叉链表：用上述结点结构所得二叉树的存储结构称之为二叉链表。第18页/共63页图形表示 A AB BC CD DC D C DA AB BE F E F G G(a)单支树的二叉链表 (b)二叉链表图6.7二叉链表存储结构易知，在含有n个结点的二叉链表中有n1个空链域。第19页/共63页typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree二叉链表的存储表示Status CreateBiTree(BiTree&T);/按先后次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树T。Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉链表存储结构，Visit是对结点操作的应用函数。/先序遍历T，对每个结点调用函数Visit()一次且仅一次。/一旦Visit()失败，则操作失败。Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉链表存储结构，Visit是对结点操作的应用函数。/中序遍历T，对每个结点调用函数Visit()一次且仅一次。/一旦Visit()失败，则操作失败。/-基本操作的函数原型说明（部分）-第20页/共63页lchild data parent rchild Status PostreOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉链表存储结构，Visit是对结点操作的应用函数。/后序遍历T，对每个结点调用函数Visit()一次且仅一次。/一旦Visit()失败，则操作失败。Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉链表存储结构，Visit是对结点操作的应用函数。/层序遍历T，对每个结点调用函数Visit()一次且仅一次。/一旦Visit()失败，则操作失败。其中，data：数据域；lchild：左指针域，指向该结点的左孩子；rchild：右指针域，指向该结点的右孩子；parent：双亲指针域，指向该结点的双亲结点。（2）三叉链表结点结构第21页/共63页定义 三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表 图形表示图6.8三叉链表存储结构 A B C DE FGA B C DE FG第22页/共63页6.4 二叉树的遍历与线索化6.4.1 二叉树的遍历 遍历二叉树（traversing binary tree）：按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。例如，图6.9所示的二叉树表示下述表达式：a+b*(cd)e/f。先序遍历：+a*bc d/e f表达式的前缀表示（波兰式）中序遍历：a+b*cde/f表达式的中缀表示后序遍历：a b c d*+e f/表达式的后缀表示（逆波兰式）层序遍历：+/a*e f bcd图6.9(a+b*(cd)e/f)表达式的二叉树-+/a *e fb -c d第23页/共63页（1）递归算法先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则访问根结点；先序遍历左子树；先序遍历右子树。中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树；访问根结点。层序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则按从上到下，从左到右的次序访问各结点。第24页/共63页Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存储结构，visit是对数据元素操作的应用函数。/先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。/最简单的Visit函数是：/Status PrintElement(TElemType e)/输出元素e的值/printf(e);/实用时，加上格式串/return OK;/调用实例：PreOrderTraverse(T,PrintElement);if(T)if(Visit(Tdata)if(PreOrderTraverse(Tlchild,Visit)if(PreOrderTraverse(Trchild,Visit)return OK;return ERROR;elsereturn OK;/PreOrderTraverse若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法6.1如下：第25页/共63页（2）非递归算法以中序遍历为例说明二叉树遍历的非递归算法。仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应的非递归算法：工作记录中包含两项，其一是递归调用的语句编号，其二是指向根 结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指 向左子树树根的指针进栈；若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回,则应访问当前层即栈顶记录中指针所指的根结点；若是从右子树返回，则表明当前层的遍历结束，应继续退栈。第26页/共63页由上述分析可得两个中序遍历二叉树的非递归算法如下所示：算法6.2如下：Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存储结构，visit是对数据元素操作的应用函数。/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);Push(S,T);/根指针进栈while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,plchild);/向左走到尽头Pop(S,p);if(!StackEmpty(S)/访问结点，向右一步Pop(S,p);if(!Visit(pdata)return ERROR;Push(S,prchild);/if/whilereturn OK;/InOrderTraverse第27页/共63页算法6.3如下：Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存储结构，visit是对数据元素操作的应用函数。/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);P=T;while(p|!StackEmpty(S)if(p)/根指针进栈，遍历左子树Push(S,p);p=plchild;/ifelse/根指针退栈，访问根结点，遍历右子树Pop(S,p);if(!Visit(pdata)return ERROR;p=prchild);/else/whilereturn OK;/InOrderTraverse第28页/共63页（3）二叉树的建立算法6.4是一个按先序序列建立二叉树的二叉链表的过程。算法6.4如下：Status CreateBiTree(BiTree&T)/按先序次序输入二叉树中结点的值（一个字符），/空格字符表示空树，构造二叉链表表示的二叉树T。scanf(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit (OVERFLOW);Tdata=ch;/生成根结点CreateBiTree(Tlchild);/构造左子树CreateBiTree(Trchild);/构造右子树return OK;/CreateBiTree第29页/共63页图6.10 二叉树例如，对图6.10所示二叉树，按下列次序顺序读入字符：A B C D E F G A B CD EG F第30页/共63页6.4.2 二叉树的线索化 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放结点的前驱和后继信息。作如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。（1）线索链表的结点结构lchild LTag data RTag rchild其中：data：数据域；lchild：左指针域，指向该结点的左孩子；rchild：右指针域，指向该结点的右孩子；第31页/共63页 0 lchild域指示结点的左孩子 LTag=1 lchild域指示结点的前驱 0 rchild域指示结点的右孩子 RTag=1 rchild域指示结点的后继（2）线索链表的定义 线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之为线索链表。（3）相关术语线索化：对二叉树以某种次序遍历使其变为线性二叉树的过程。线索二叉树（Threaded Binary Tree）：加上线索的二叉树。线索：在线索链表中指向结点前驱和后继的指针。第32页/共63页（4）图形表示-+/a *e fb -c d-+/NIL NILa *e fb -c d(a)(a+b*(cd)e/f)表达式的二叉树(b)中序线索二叉树第33页/共63页图6.11线索二叉树及其存储结构thrt 0 1bt0 0 0 0 0 /0 1 a 1 0 *0 1 e 1 1 f 10 01 b 11 c 11 d 1(c)中序线索链表图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。第34页/共63页（5）C语言描述 /-二叉树的二叉线索存储表示-typedef enum PointerTag Link,Thread;/Link=0:指针，Thread=1:线索typedef struct BiThrNode TElemTypedata;struct BiThrNode*lchild,*rchild;/左右孩子指针PointerTagLTag,RTag;/左右标志 BiThrNode,*BiThrTree;（6）遍历算法 仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。这就为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。下述算法正是以双向线索链表为存储结构时对二叉树进行遍历的算法。第35页/共63页算法6.5如下：Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)/T指向头结点，头结点的左链lchild指向根结点，可参加线索化算法。/中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。p=Tlchild;/p指向根结点while(p!=T)/空树或遍历结束时，p=Twhile(pLTag=Link)p=plchild;if(!Visit(pdata)return ERROR;/访问其左子树为空的结点while(pRTag=Thread&prchild!=T)p=prchild;Visit(pdata);/访问后继结点p=prchild;return OK;/InOrderTraverse_Thr第36页/共63页（7）二叉树的线索化算法算法6.6如下：Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/中序遍历二叉线索树T，并将其中序线索化，Thrt指向头结点。if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit (OVERFLOW);ThrtLTag=Link;ThrtRTag=Thread;/建头结点Thrtrchild=Thrt;/右指针回指if(!T)/若二叉树空，则左指针回指Thrtlchild=Thrt;else Thrtlchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化prerchild=Thrt;preRTag=Thread;/最后一个结点线索化Thrtrchild=pre;/elsereturn OK;/InOrderThreading指针pre始终指向刚刚访问过的结点,若指针p指向当前访问的结点,则pre指向它的前驱 第37页/共63页 算法6.7如下：void InThreading(BiThrTree p)if(p)InThreading(plchild);/左子树线索化if(!plchild)/前驱线索pLTag=Thread;plchild=pre;if(!prerchild)/后继线索preRTag=Thread;prerchild=p;pre=p;InThreading(prchild);/右子树线索化 /if /InThreading线索化的过程是在遍历过程中修改二叉链表中的空指针为指向前驱或后继的线索的过程。第38页/共63页6.5 树和森林6.5.1 树的存储结构（1）双亲表示法C语言描述 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。#defineMAX_TREE_SIZE100 typedef struct PTNode/结点结构TElemTypedata;int parent;/双亲位置域 PTNode typedef struct/树结构PTNodenodesMAX_TREE_SIZE;intr,n;/根的位置和结点数 PTree;第39页/共63页图形表示 数组下标图6.12树的双亲表示法示例RABCDEFGKH数组下标0 R -11 A 02 B 03 C 04 D 15 E 1 6 F 37 G 68 H 69 K 6第40页/共63页（2）孩子表示法定义 孩子表示法：把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。C语言描述typedef struct CTNode/孩子结点int child;struct CTNode*next;*ChildPtrtypedef struct TElemType data;ChildPtr firstchild;/孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置；CTree 第41页/共63页RABCDEFGKH 图形表示(a)原树(b)孩子链表0 A 3 51 B2 C 63 D4 R 0 1 25 E6 F 7 8 97 G8 H9 K第42页/共63页 上图(c)是把双亲表示法和孩子表示法结合起来，即将双亲表示和孩子链表合在一起的存储结构。(c)带双亲的孩子链表图6.13树的另外两种表示法0 4 A 3 5 1 4 B2 4 C 6 3 0 D4 -1 R 0 1 26 2 F 7 8 95 0 E7 6 G8 6 H9 6 K第43页/共63页（3）孩子兄弟表示法定义 孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点。C语言描述typedef struct CSNode TElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree第44页/共63页RABCDEFGKH 图形表示图6.14树的二叉链表表示法 R ABDEFGKHC第45页/共63页6.5.2 森林与二叉树的转换（1）森林转换成二叉树 如果F=T1,T2,Tm是森林，则可按如下规则转换成一棵二叉树B=(root,LB,RB)。若F为空，即m0，则B为空树；若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林F1=T11,T12,T1m转换而 成的二叉树;其右子树RB是从森林F=T2,T3,Tm转换而成的二叉树。（2）二叉树转换成森林 如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F=T1,T2,Tm。若B为空，则F为空；若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中 的根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外 其余树组成的森林F=T2,T3,Tm是由B的右子树RB转换而成的森林。第46页/共63页例，图6.15展示了森林与二叉树之间的对应关系。图6.15 森林与二叉树的对应关系 森林与二叉树对应 A B C DEF 树与二叉树对应 A BCD树根相连EFGH IJGJIHB E A JIHCDGF第47页/共63页6.5.3 树和森林的遍历树的遍历方法：先根（次序）遍历，即：先访问树的根结点，然后依次先根遍历根的每 棵子树；后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。例如，对图6.16的树进行遍历，可得树的序列为：先根遍历：A B C D E后根遍历：B D C E A 图6.16 ACDEB第48页/共63页森林的遍历方法：先序遍历森林 若森林非空，则可按下述规则遍历之：1访问森林中第一棵树的根结点；2先序遍历第一棵树中根结点的子树森林；3先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历森林 若森林非空，则可按下述规则遍历之：1中序遍历森林中第一棵树的根结点的子树森林；2访问第一棵树的根结点；3中序遍历除去第一棵树之后剩余的树构成的森林。例如，对图6.15中森林进行遍历，得到森林的序列为：先序遍历：A B C D E F G H I J中序遍历：B C D A F E H J I G第49页/共63页6.6 赫夫曼树及其应用6.6.1 最优二叉树（赫夫曼树）（1）基本概念路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度：路径上分分支数目。树的路径长度：从树根到每一结点的路径长度之和。结点的带权路径长度：指从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：最优二叉树（或赫夫曼树）：带权路径长度WPL最小的二叉树。第50页/共63页 例1，图6.17中3棵二叉树，都有4个叶子结点a、b、c、d，分别带权7、5、2、4，它们的带权路径长度分别为：(a)WPL=7252224236(b)WPL=7353214246(c)WPL=7152234335图6.17具有不同带权路径长度的二叉树 2 7 e a7 5 2 4 4 5a b c d d b 7 5 2 4a b c d(a)(b)(c)例2，利用赫夫曼树得到最佳判定树（见书P144）。第51页/共63页（2）赫夫曼树的构造赫夫曼算法：根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且 置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是赫夫曼树。例如，图6.18展示了图6.17的赫夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。7 5 2 4a b c d(a)(b)7 5 6a bc d第52页/共63页b7 11 c da18 bc da(c)(d)图6.18 赫夫曼树的构造过程 第53页/共63页6.6.2 赫夫曼编码（1）前缀编码 前缀编码：任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。约定：在二叉树中，左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。例如，假设有图6.19所示的二叉树，其4个叶子结点分别表示A、B、C、D这4个字符。由图6.19所得A、B、C、D的二进制前缀编码分别为0、10、110、111 编码 A(0)0 1 B(10)A C(110)0 1 D(111)B C D 图6.19前缀编码示例第54页/共63页（2）赫夫曼编码 由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码便称为赫夫曼编码。假设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种。对应到二叉树上，若置wi为叶子结点的权,li字符，则电文总长为恰为从根到叶子的路径长度，则恰为二叉树上带权路径长度。（3）赫夫曼树和赫夫曼编码的存储表示typedef struct unsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree/动态分配数组存储赫夫曼树typedef char*HuffmanCode;/动态分配数组存储赫夫曼编码表第55页/共63页（4）求赫夫曼编码的算法 void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)/w存放n个字符的权值(均0)构造赫夫曼树HT，/并求出n个字符的赫夫曼编码HC。if(n=1)return;m=2*n 1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用for(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;for(;i=m;+i,+p)*p=0,0,0,0;for(i=n+1;i=m;+i)/建赫夫曼树/在HT1.i-1选择parent为0且weight最小的两个结点，/其序号分别为s1和s2 Select(HT,i 1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight