数据结构-第6章树和二叉树

1、第第 6 6 章树和二叉树章树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树 6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.4 6.4 树和森林树和森林 6.5 6.5 赫夫曼树及其应用赫夫曼树及其应用6.1 6.1 树的定义和基本术语树的定义和基本术语6.1.1 6.1.1 树的定义树的定义6.1.2 6.1.2 基本术语基本术语6.1.3 6.1.3 树的表示树的表示1.1.树的定义树的定义 树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则：（1）有且仅有一个特定的称为根根（root）的结点。它只有直接后继，

2、但没有直接前驱；（2）当n1时,其余结点可以划分为m（m0）个互不相交的有限集合T1，T2，Tm，每个集合又是一棵树，称为根的子树子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图6-1。6.1.1 6.1.1 树的定义树的定义一棵树的逻辑结构可以用二元组描述为：tree =(k,R) k=ki 1in;n0,kielemtype R=r其中，n为树中结点个数，若 n=0，则为一棵空树， n0时称为一棵非空树，而关系 r 应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除

3、根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。2. 2. 树的逻辑结构描述树的逻辑结构描述例如，对图6-1(c )的树结构,可以二元组表示为：K=A，B，C，D，E，F，G，H，I，J，K，L，MR=rr=，(1) InitTree(&T) 初始化树T。(2) Root(T) 求树T的根结点(3) Parent(T,x) 求树T中，值为x的结点的双亲。(4) Child(T,x,i) 求树T中，值为x的结点的第i个孩子。(5) AddChild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6) DelChild

4、(x,i) 删除值为x的结点的第i个孩子。(7) TraverseTree(T) 遍历或访问树T。 3. 3. 树的基本运算树的基本运算1.1.结点结点: : 树的结点包含一个数据元素及若干指向其子树的分支2.2.度度: : 一个结点包含子树的数目，称为该结点的度。3.3.叶子（终端）结点叶子（终端）结点度为0的结点，称为叶子结点或树叶，也叫终端结点。 4.4.孩子结点孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。 5.5.双亲结点双亲结点 若结点X有子女Y，则X为Y的双亲结点。6.1.2 6.1.2 基本术语基本术语

5、 6.6.祖先结点祖先结点 从根结点到该结点所经过分支上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D ，H 。7.7.子孙结点子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8.8.兄弟结点兄弟结点 具有同一个双亲的结点，称为兄弟结点。9.9.分支结点分支结点 除叶子结点外的所有结点，为分支结点，也叫非终端结点。(度不为0的结点)1010层数层数( (层次层次) ) 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11. 11. 树的高度（深度）树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度1。12

6、.12.树的度树的度 树中结点度的最大值称为树的度。13. 13. 有序树有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 14. 14. 无序树无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。1515森林（树林）森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。 1 1树形结构表示法树形结构表示法6.1.3 6.1.3 树的表示树的表示2. 2. 凹入法表示法凹入法表示法 3. 3. 嵌套集合表示法嵌套集合表示法4. 4. 广义表表示法广义表表示法（A（B（E（J，K，L），F），C（G），D（H（M），I） 6.2

7、二叉树二叉树6.2.1 6.2.1 二叉树的定义二叉树的定义6.2.2 6.2.2 二叉树的性质二叉树的性质6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.2.1 6.2.1 二叉树的定义二叉树的定义1 1 二叉树的定义二叉树的定义 和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。因此，二叉树有五种不同的形态。 (a) 空二叉树(b) 仅

8、有一个根结点的二叉树(c) 右子树为空的二叉树(d) 左子树为空的二叉树(e) 左、右子树均非空的二叉树二叉树的五种基本形态二叉树的五种基本形态（1）InitBitree(&T) 二叉树的初始化。 （2）Root(T) 求二叉树的根结点（3）Parent(T,x) 求二叉树T中值为x的结点的双亲（4）Lchild(T,x) 求二叉树T中值为x的结点的左孩子。 （5）Rchild(T,x) 求二叉树T中值为x的结点的右孩子。 （6）Lbrother(T,x) 求二叉树T中值为x的结点的左兄弟。 （7）Rbrother(T,x) 求二叉树T中值为x的结点的右兄弟。2. 2. 二叉树的基本运

9、算二叉树的基本运算（8）Traverse(T) 遍历二叉树T。（9）CreateBiTree(&T) 建立一棵二叉树T。（10）AddLchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。 （11）AddRchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。 （12） DelLchild(&T,x) 在二叉树T中，删除值为x 的结点的左孩子。 （13）DelRchild(&T,x) 在二叉树T中，删除值为x 的结点的右孩子。 性质性质1 1 若二叉树的层数从1开始，则二叉树的第i层结点数

10、，最多为2 2i-1i-1个（i1）。6.2.2 6.2.2 二叉树的性质二叉树的性质20=121=222=423=8 深度（高度）为k的二叉树最大结点数为2 2k k-1-1（k1）。证明:最大结点个数=20+21+22+2k-1=2k-1性质性质2 2 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设n0,n1和n2分别为二叉树中度为0,度为1和度为2的结点个数，则二叉树中总的结点个数n满足： n=n0+n1+n2 再有除了根结点之外，每个结点都由一个分支射入，则分支数B与总的结点数之间的关系为： n=B+1 另外，由于这些分支是由度为1或2的

11、结点射出的，则有 B=n1+2n2则由上三式得： n0=n2+1性质性质3 3 为继续给出二叉树的其它性质，先定义两种特殊的二叉树：满二叉树满二叉树 深度为k具有2 2k k-1-1个结点的二叉树，称为满二叉树。完全二叉树完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1- n的结点一一对应，则称这棵二叉树为完全二叉树。 11 12 13 14 15 具有n个结点的完全二叉树完全二叉树的深度深度为 log2n +1 +1证明：设深度为k,则由性质2和完全二叉树的性质有： 2k-1-1n2k-1即 2k-1 n 2k 则有 k-1 log2n 1，

12、则其父结点编号为 i/2 。(2) 如果2in，则其左儿子结点编号为2i；若2in，则无左儿子结点。(3) 如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。性质性质5 5 11 12 13 14 15 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构1.1.顺序存储结构顺序存储结构2.2.链式存储结构链式存储结构1.1.顺序存储结构顺序存储结构思想思想:用一个一维数组来存储二叉树的各个结点C C语言表示语言表示#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;

13、 /0号单元存储根结点SqBiTree bt; 分析分析: :显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。例:对应的顺序存储结构:下标123456789100123456789完全二叉树的顺序表示:例:对应的顺序存储结构:一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组.非完全二叉树的顺序表示: A B C E F G D A

14、 B D C E G F 总结总结: :顺序存储结构适合存储完全二叉树对于非完全二叉树，采用链式存储结构更合适2. 2. 二叉链表二叉链表结点结构结点结构: :通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。 lchilddatarchild 存储表示存储表示typedef struct BiTNodetypedef struct BiTNode TElemType data; TElemType data; struct Bi

15、TNode struct BiTNode * *lchild, lchild, * *rchild;rchild; BiTNode, BiTNode, * *BITreeBITree; 这里的TElemType可以是任何相应的数据类型如int、float或char等。 二叉链表例: 链式存储: A B E C D G F 3. 3. 三叉链表三叉链表通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲

16、结点。 lchilddata rchildparent 6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.3.1 6.3.1 遍历二叉树遍历二叉树定义定义:二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。本节仅讨论二叉链表的遍历过程。 一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序：左、

17、根、右左、根、右；根、左、右根、左、右；左、右、根左、右、根；右、根、左；根、右、左；右、左、根；由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中、三种遍历次序，分别称为中序遍历中序遍历、先序遍历先序遍历和后序遍历后序遍历。(1) 中序（InOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。(2) 先序（PreOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 访问根结点； 先序遍历左子树； 先序遍历右子树。三种遍历次序以递归的形式定义：三种遍历次序以递归的形式定义：(3) 后序（PostOrd

18、er）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。 中序遍历序列： 先序遍历序列： 后序遍历序列： 二叉树遍历举例HDIBEAFCG B C D E F G A H I ABDHIECFGHIDEBFGCA中序遍历递归算法voidInOrder(BITreeT)if(T)InOrder(T-lchild);visit(T-data);InOrder(T-rchild);先序遍历递归算法voidPreOrder(BITreeT)if(T)visit(T-data);PreOrder(T-lchild);PreOrder(T-rchi

19、ld);后序遍历递归算法voidPostOrder(BITreeT)if(T)PostOrder(T-lchild);PostOrder(T-rchild);visit(T-data);遍历算法的应用遍历算法的应用二叉树的遍历算法是一个重要的应用注意注意:1.理解访问根结点的意义2.对具体问题需要考虑遍历的顺序1.1.先序创建二叉链表先序创建二叉链表StatusCreateBiTree(BITree&T)scanf(&ch);if(ch=)T=Null;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-dat

20、a=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);returnOK;2.2.输出二叉树的结点输出二叉树的结点voidPreOrder(BITreeT)if(T)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);3.3.输出二叉树的叶子结点输出二叉树的叶子结点voidPreOrder(BITreeT)if(T)if(T-lchild=NULL&T-rchild=NULL)printf(T-data);PreOrder(T-lchild);PreOrder(T-rchild);4.4

21、.统计二叉树的叶子结点个数统计二叉树的叶子结点个数intn=0;voidleafcount(BITreeT)if(T)if(T-lchild=NULL&T-rchild=NULL)n+;leafcount(T-lchild);leafcount(T-rchild);5.5.求二叉树的高度求二叉树的高度intPostTreeDepth(BITreeT)if(T)hl=PostTreeDepth(T-lchild);hr=PostTreeDepth(T-rchild);max=hlhr?hl:hr;return(max+1);elsereturn0;二叉树的非递归遍历可利用堆栈将递归算法改

22、写成非递归的形式。下面以中序遍历为例来具体说明。T-*caba*-cb&-&*&a&b&ca*b -c中序非递归遍历算法分析：1.栈初始化,根指针入栈2.当栈非空时 (1)当栈顶元素非空时,左指针入栈向左走向尽头 (2)栈顶空指针出栈 (3)当栈非空时, 栈顶元素出栈并访问且将其右指针入栈算法实现算法实现：void InOrder(BiTree T)void InOrder(BiTree T)InitStack(S);Push(S,T);InitStack(S);Push(S,T);while (!StackEmpty(S)while (!StackEm

23、pty(S) while(GetTop(S,p)&p) while(GetTop(S,p)&p) Push(S,p-lchild); Push(S,p-lchild); Pop(S,p); Pop(S,p); if(!StackEmpty(S) if(!StackEmpty(S) Pop(S,p);visit(p-data); Pop(S,p);visit(p-data); Push(S,p-rchild);/if Push(S,p-rchild);/if/while/while 6.3.2 6.3.2 线索二叉树线索二叉树相关概念相关概念:在一个n结点的链式存储二叉树中，有n

24、+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。线索线索:在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。线索二叉树线索二叉树:对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。在一个线索二叉树中，必须设法将线索与指向结点左、右儿子结点的指针加以区别。可给每个结点增加两个标志域，即左线索标志域LTag，右线索标志域RTag。左线索域是指向其前驱结点的的指针域是指向其左儿子结点leftleftltag10右线索域是指向其后继结点的的指针域是指向其右儿子结点rig

25、htrightrtag10LTagRTaglchildlchild域指示结点的左孩子域指示结点的左孩子lchildlchild域指示结点的前趋域指示结点的前趋rchildrchild域指示结点的右孩子域指示结点的右孩子rchildrchild域指示结点的后继域指示结点的后继 增加线索标志域后的结点结构为：这种结点类型和相应结点的指针类型定义如下：typedef enum PointerTagLink,Thread; typedef struct BiThrNode ElemType data; PointerTag LTag,RTag; /*ltag和rtag只能取值为0或1*/ struct

26、 BiThrNode *lchild,*rchild; BiThrNode,*BiThrTree; lchild LTag data RTag rchild 中序线索树 A C F G B D E H I T11中序遍历线索树思想思想: 先由头结点指针找到根结点，从根结点起沿左指针逐结点一直向左查找，找到左线索标志为1的结点(“最左”的结点)即为遍历中需首先访问的结点。由此结点开始，反复进行寻找后继结点的过程，并陆续访问这些结点，直至结束。中序遍历线索二叉树非递归算法void thinorder(BiThrTree T)/二叉树附加了头结点,T指向头结点p= T-lchild;/p指向根结点w

27、hild(p!=T) /*空树或遍历结束时,p=T*/ while(p-LTag=Link) p=p-lchild; /*从根往下找到最左的结点，即中序序列的开始结点*/ visit(p-data);/访问左子树为空结点 while(p-Rtag=Thread&p-rchild!=T) p=p-rchild;visit(p-data);/*访问后继结点*/ p=p-rchild; return OK; 中序线索化思想思想：一边中序遍历一边建立线索。若访问结点的左儿子结点为空，则建立前趋线索；若右儿子结点为空，则建立后继线索。 为此附设一个指针pre始终指向刚刚访问过的结点，而用指针p指

28、示当前正在访问的结点。pre的初始值为NULL。中序线索化算法void inthread (BiThrTree &p,void inthread (BiThrTree &p,* *pre)pre) if(p) if(p) inthread(p-lchild,pre); / inthread(p-lchild,pre); /* *左子树线左子树线索化索化* */ / if(p-lchild=NULL) if(p-lchild=NULL) / /* *若当前结点的左子树为空，则建立指若当前结点的左子树为空，则建立指向其前趋结点的前趋线索向其前趋结点的前趋线索* */ / p-lta

29、g=1; p-ltag=1; p-lchild=pre; p-lchild=pre; else else p-ltag=0; p-ltag=0; 中序线索化算法续 if (pre!=NULL & pre-right=NULL) if (pre!=NULL & pre-right=NULL) / /* *若前趋结点不为空，且其右指针域为空，则建若前趋结点不为空，且其右指针域为空，则建立该前趋结点指向当前结点的后继线索立该前趋结点指向当前结点的后继线索* */ / pre-RTag=1; pre-RTag=1; pre-rchild=p; pre-rchild=p; else el

30、se pre-RTag=0; pre-RTag=0; pre=p; / pre=p; /* *中序向后遍历一个结点中序向后遍历一个结点* */ / inthread (p-rchild,pre); inthread (p-rchild,pre); 6.4 6.4 树和森林树和森林6.4.1 6.4.1 树的存储结构树的存储结构6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换6.4.3 6.4.3 树和森林的遍历树和森林的遍历6.4.1 6.4.1 树的存储结构树的存储结构1 1双亲表示法双亲表示法2. 2. 孩子表示法孩子表示法 3 3孩子兄弟表示法孩子兄弟表示法 1 1双亲表示法

31、双亲表示法这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置 .其结点的结构如下： 数据域双亲位置域dataparent双亲表示法的形式说明如下：#define MAX 100#define MAX 100typedef struct PTNode /typedef struct PTNode /结点结构结点结构 TElemType data; TElemType data; int parent; int parent;PTNode;PTNode;typedef struct /typedef struct /树结构树结构 PTNode

32、nodesMAX; PTNode nodesMAX; int r,n; / int r,n; /根的位置和结点数根的位置和结点数PTree;PTree;双亲表示法举例2. 2. 孩子表示法孩子表示法这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表. 类型说明类型说明 typedef struct CTNode/ 孩子链表结点的定 int child; / 该孩子结点在线性表中的位置 struct CTNode * next;/指向下一个孩子结点 *ChildPtr

33、; typedef struct/ 顺序表结点的结构定义 TElemType data;/ 结点的信息 ChildPtr firstChild ; / 孩子链表的头指针CTBox;typedef struct / 树的定义 CTBox nodesMAX; / 顺序表 int n,r;/ 结点数和根的位置 CTree;孩子表示法举例674563. 3. 孩子兄弟表示法孩子兄弟表示法这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。形式说明typedef struct CSNode

34、 ElemType data; /*结点信息*/ Struct CSNode *firstChild, *Nextsibling; /*第一个孩子,下一个兄弟*/CSNode, *CSTree;孩子兄弟表示法举例6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换树的孩子兄弟链表结构与二叉树的二叉链表结构在物理结构上是完全相同的，只是它们的逻辑含义不同，所以树和森林与二叉树之间必然有着密切的关系。本节我们就介绍树和森林与二叉树之间的相互转换方法。方法如下： (1)在所有兄弟结点之间加一连线； (2) 对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。

35、 (3)以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。1树转换为二叉树树转换成二叉树举例森林是若干棵树的集合。树可以转换为二叉树，森林同样也可以转换为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。方法如下方法如下：（1） 将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。2.森林转换为二叉树森林转换成二叉树举例6.4.3 树与森林的遍历1.1.树的遍历树的遍历方法主要有以下两种：（1） 先根遍历若树非空，则遍历方法为

36、：访问根结点。从左到右，依次先根遍历根结点的每一棵子树。（2）后根遍历若树非空，则遍历方法为：从左到右，依次后根遍历根结点的每一棵子树。访问根结点。树的遍历举例如右图树先根遍历序列为ABECFHGD后根遍历序列为EBHFGCDA2.2.森林的遍历森林的遍历森林的遍历方法主要有以下两种：(1) 先序遍历若森林非空，则遍历方法为：访问森林中第一棵树的根结点。先序遍历第一棵树的根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。 (2) 后序遍历若森林非空，则遍历方法为： 后序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点。 后序遍历除去第一棵树之后剩余的树构成的森林。森林的

37、遍历举例如右图森林先序遍历序列为ABCDEFGHIJ后序遍历序列为BCDAFEHJIG6.5 6.5 赫夫曼树及其应用赫夫曼树及其应用6.5.1赫夫曼树赫夫曼树( (最最优优二叉树二叉树) )6.5.2赫夫曼编码赫夫曼编码6.5.1赫夫曼树赫夫曼树( (最优二叉树最优二叉树) )1. 1. 基本术语基本术语：路径路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度路径长度：路径上的分支数称为这两点之间的路径长度。树的路径长度树的路径长度：树的路径长度是从树的根到每一结点的路径长度之和，一般记作pl。 在结点数目相同的二叉树中，完全二叉树或满二叉树的路径长度最短。pl=0+1+1+2+2+2+2=10 pl=0+1+1+2+2+2+3=11 结点的权结点的权：在许多实际应用中，常常将树中结点赋予一个有某种意义的