第06章树和二叉树

1、第六章第六章 树和二叉树树和二叉树数据结构数据结构: 线性结构线性结构(线性表线性表, 栈栈,队列等队列等) 非线性结构非线性结构: 至少存在一个数据元素有不至少存在一个数据元素有不止一个直接前驱或后继止一个直接前驱或后继(树树,图等图等)第六章第六章 树和二叉树树和二叉树6.1 6.1 树的定义树的定义 树是树是n n个数据元素的有限集个数据元素的有限集( (记为记为T)T)，对，对任意一棵树任意一棵树T T有：有： 存在唯一一个称为存在唯一一个称为根根 的数据元素；的数据元素； 当当n n1 1时，其它数据元素可分为时，其它数据元素可分为m(mm(m0) 0) 个互不相交的有限集个互不相交

2、的有限集T T1 1,T,T2 2,T,Tm m，其中每个，其中每个集合集合T Ti i(i=1,2,(i=1,2,m),m)本身又是一棵树，并称本身又是一棵树，并称树树 T Ti i是根的是根的子树子树. .第六章第六章 树和二叉树树和二叉树树的表示法树的表示法1. 1. 分支图表示法分支图表示法2. 2. 嵌套集合表示法嵌套集合表示法3. 广义表表示法(A(B(D),C)第六章第六章 树和二叉树树和二叉树树的基本术语树的基本术语1. 1. 树的结点树的结点: :包含一个包含一个DEDE和指向其子树的所有分支和指向其子树的所有分支; ;2. 2. 结点的度结点的度: :一个结点拥有的子树的个

3、数一个结点拥有的子树的个数, ,度为零度为零的结点称为的结点称为叶结点叶结点; ;3. 3. 树的度树的度: :树中所有结点的度的最大值树中所有结点的度的最大值Max(D(I)Max(D(I) 含义含义: :树中最大分支数为树的度树中最大分支数为树的度; ;4. 4. 结点的层次及树的深度结点的层次及树的深度: :根为第一层根为第一层, ,根的孩子根的孩子为第二层为第二层, ,若某结点为第若某结点为第k k层层, ,则其孩子为则其孩子为k+1k+1层层. . 树中结点的最大层次称为树的深度或高度树中结点的最大层次称为树的深度或高度5.5.森林森林: :是是m(m=0)m(m=0)棵互不相的树的

4、集合棵互不相的树的集合 森林与树概念相近森林与树概念相近, ,相互很容易转换相互很容易转换. .第六章第六章 树和二叉树树和二叉树6.2 6.2 树的基本运算树的基本运算 初始化操作初始化操作INITIATE(T)INITIATE(T)：创建一棵空树。：创建一棵空树。 求根函数求根函数ROOT(T)ROOT(T)：求树：求树T T的根；的根；ROOT(X)ROOT(X)：求：求结点结点x x所在树的根。所在树的根。 求双亲函数求双亲函数PARENT(T,x)PARENT(T,x)：在树：在树T T中求中求x x的双亲。的双亲。 求第求第i i个孩子函数个孩子函数CHILD(T,x,i)CHIL

5、D(T,x,i)：在树：在树T T中求结中求结点点x x的第的第i i个孩子。个孩子。 求兄弟函数：在求兄弟函数：在T T中求中求x x的左兄弟的左兄弟LSIBLING(T,x)LSIBLING(T,x)；在树在树T T中求中求x x的右兄弟的右兄弟RSIBLING(T,x)RSIBLING(T,x)。第六章第六章 树和二叉树树和二叉树 建树函数建树函数CRT-TREE(x,F)CRT-TREE(x,F)：建立以结点：建立以结点x x为根，为根，森林森林F F为子树的树。为子树的树。 插入子树操作插入子树操作INS-CHILD(y,i,x)INS-CHILD(y,i,x)：将：将x x作为作为

6、y y的的第第i i根子树。根子树。 删除子树操作删除子树操作DEL-CHILD(x,i)DEL-CHILD(x,i)：删除：删除x x的第的第i i棵棵子树。子树。 遍历树操作遍历树操作TRAVERSE(T)TRAVERSE(T)：按顺序访问树：按顺序访问树T T中各中各个结点。个结点。 置空树操作置空树操作CLEAR(T)CLEAR(T)：将树：将树T T置为空树。置为空树。第六章第六章 树和二叉树树和二叉树6.3 6.3 二叉树概念及性质二叉树概念及性质一一. . 二叉树概念二叉树概念 二叉树是结点数为二叉树是结点数为0 0或每个结点最多只有或每个结点最多只有左右两棵子树的树。二叉树是一

7、种特殊的树，左右两棵子树的树。二叉树是一种特殊的树，它的特点是：它的特点是：每个结点最多只有两棵子树，即不存结点每个结点最多只有两棵子树，即不存结点度大于度大于2 2的结点；的结点；子树有左右之分，不能颠倒。子树有左右之分，不能颠倒。6.3 二叉树二叉树二二. . 二叉树性质二叉树性质性质性质1.1. 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点( (i1)i1)。性质性质2.2. 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点( (k)k)。（深度一定，二叉树的最大结点数也确定）（深度一定，二叉树的最大结点数也确定）性质性质

8、3.3. 二叉树中二叉树中, ,终端结点数终端结点数n n0 0与度为与度为2 2的结点数的结点数n n2 2有如下关系有如下关系: : n n0=0=n n2 2+1+16.3 二叉树二叉树满二叉树满二叉树: :深度为深度为k k，且有，且有2 2k k-1-1个结点的二叉树。个结点的二叉树。特点：（特点：（1 1）每一层上结点数都达到最大）每一层上结点数都达到最大 （2 2）度为）度为1 1的结点的结点n n1 1=0=0 结点层序编号方法：从根结点起从上到下逐层结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。（层内从左到右）对二叉树的结点进行连续编号。

9、1237654K=3n=23-1=7 满二叉树 6.3 二叉树二叉树完全二叉树完全二叉树: :深度为深度为k k，结点数为，结点数为n n的二叉树，当的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树且仅当每个结点的编号都与相同深度的满二叉树中从中从1 1到到n n的结点一一对应时，称为完全二叉树。的结点一一对应时，称为完全二叉树。452136.3 二叉树二叉树完全二叉树的特点完全二叉树的特点: :（1 1）每个结点）每个结点i i的左子树的深度的左子树的深度LhLhi i- -其结点其结点i i的右的右子树的深度子树的深度RhRhi i等于等于0 0或或1 1，即叶结点只可能出现在，即叶

10、结点只可能出现在层次最大或次最大的两层上。层次最大或次最大的两层上。（2 2）完全二叉树结点数）完全二叉树结点数n n满足满足2 2k-1k-1-1-1n2n2k k-1 -1 （3 3）满二叉树一定是完全二叉树，反之不成立。）满二叉树一定是完全二叉树，反之不成立。452136.3 二叉树二叉树LHLH2 2=0=0RHRH2 2=1=11324653241LH1=3RH1=1LH1 -RH1=2 非完全二叉树非完全二叉树 非完全二叉树非完全二叉树LH2-RH2=0-1=-16.3 二叉树二叉树性质性质4.4. 结点数为结点数为n n的完全二叉树，其深度为的完全二叉树，其深度为 loglog2

11、 2n n + 1+ 16.3 二叉树二叉树性质性质5.5. 在按层序编号的在按层序编号的n n个结点的完全二叉树中，个结点的完全二叉树中，任意一结点任意一结点i(1in)i(1in)有：有： i=1 i=1时，结点时，结点i i是树的根；否则是树的根；否则(i1)(i1)，结点，结点i i的的双亲为结点双亲为结点i/2i/2。 2i 2in n时，结点时，结点i i无左孩子，为叶结点；否则，无左孩子，为叶结点；否则，结点结点i i的左孩子为结点的左孩子为结点2 2i i。 2i+1 2i+1n n时，结点时，结点i i无右孩子；否则，结点无右孩子；否则，结点i i的的右孩子为结点右孩子为结点

12、2 2i+1i+1。6.3 二叉树二叉树 完全二叉树完全二叉树DCGFEBA三、二叉树的存储结构三、二叉树的存储结构 顺序存储结构顺序存储结构 用一组地址连续的存储单元，以层序顺序存放二叉树用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，的数据元素， 结点的相对位置蕴含着结点之间的关系。结点的相对位置蕴含着结点之间的关系。 bt3的双亲为的双亲为3/23/2=1， 即在即在b t1中；中； 其左孩子在其左孩子在bt2i=bt6中；中； 其右孩子在其右孩子在bt2i+1=bt7中。中。1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 06.3 二叉

13、树二叉树 这种存储结构适合于完全二叉树，既不浪费存这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。可能造成存储空间的浪费。D 二叉树CGFEBA1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G 0 0 0 0 一般二叉树也按完全二叉树形式存储,没结点处用0表示。6.3 二叉树二叉树例如，深度为例如，深度为k k，且只有，且只有k k个结点的右单枝树个结点的右单枝树

14、(每个每个非叶结点只有右孩子非叶结点只有右孩子) )，需，需2 2k k-1-1个单元，即有个单元，即有2 2k k-1-k-1-k个单元被浪费。个单元被浪费。1k6.3 二叉树二叉树 链式存储结构链式存储结构 设计不同的结点结构，可以构成不同的链式存设计不同的结点结构，可以构成不同的链式存储结构。常用的有：储结构。常用的有： 二叉链表二叉链表 三叉链表三叉链表 线索链表线索链表 用空链域存放指向前驱或后继的线索用空链域存放指向前驱或后继的线索 6.3 二叉树二叉树二叉链表的结点结构二叉链表的结点结构 lchild data rchildD 二叉树二叉树CEBAACBDE二叉链表二叉链表6.3

15、 二叉树二叉树 三叉链表的结点结构三叉链表的结点结构 lchild data parent rchildD 二叉树二叉树CEBAACBDE三叉链表三叉链表6.3 二叉树二叉树性质性质6.6. 含有含有n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空链域。个空链域。6.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树一、遍历二叉树 遍历二叉树是指遍历二叉树是指按一定的规律按一定的规律对二叉树的每个结对二叉树的每个结点，点，访问访问且仅访问一次的处理过程。且仅访问一次的处理过程。 访问访问是一种抽象操作，是对结点的某种处理，例如是一种抽象操作，是对结点的某种处理，例

16、如可以是求结点的度、或层次、打印结点的信息，或做可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。其他任何工作。 一次遍历后，使树中结点的非线性排列，按访问的一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。先后顺序变为某种线性排列。 遍历的次序遍历的次序：若设二叉树根为：若设二叉树根为D D，左子树为，左子树为L L，右子，右子树为树为R R，并限定先左后右，则有以下三种遍历次序：，并限定先左后右，则有以下三种遍历次序：LDR LDR 中序遍历中序遍历；LRD LRD 后序遍历后序遍历；DLR DLR 先序遍历先序遍历6.4 遍历二叉树和线索二叉树遍历二叉树和线

17、索二叉树1.1.中序遍历二叉树中序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树非空，则：1）中序遍历左子树）中序遍历左子树2）访问根结点）访问根结点3）中序遍历右子树）中序遍历右子树算法描述算法描述:PROC inorder (bt：bitreptr)；bt为BT根结点指针IF btNIL THEN inorder (btlchild) ; visit (bt data)； inorder (btrchild) ; ENDP; inorder6.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树2.2.后序遍历二叉树后序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树

18、非空，则：1）后序遍历左子树）后序遍历左子树2）后序遍历右子树）后序遍历右子树3）访问根结点）访问根结点算法描述算法描述:PROC postorder (bt：bitreptr)；bt为BT根结点指针IF btNIL THEN postorder (btlchild) ; postorder (btrchild) ; visit (bt data)； ENDP; postorder6.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树3.3.先序遍历二叉树先序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树非空，则：1）访问根结点）访问根结点2) 先序遍历左子树先序遍历左子树3）先序

19、遍历右子树）先序遍历右子树算法描述算法描述:PROC preorder (bt：bitreptr)；bt为为BT根结点指针根结点指针IF btNIL THEN visit (btdata)； preorder (btlchild) ; preorder (btrchild) ; ENDP; preorder6.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树例：表达式例：表达式a+b (c-d)-e/facdefb+遍历结果遍历结果:中序中序: a+b c d e /f后序后序: abcd +ef / 先序先序: +a b cd /ef6.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树三种遍

20、历过程示意图例三种遍历过程示意图例 acbab*c-ba*-cab*c-abc 虚线表示执行过程虚线表示执行过程: 向下表示更深层的递归调用向下表示更深层的递归调用; 向上表示递归调用返回向上表示递归调用返回; 沿虚线记下各类符号沿虚线记下各类符号,便得到遍历的结果便得到遍历的结果.6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树PROCPROC inorder(bt:bitreptr)；中序遍历非递归算法中序遍历非递归算法,s,s为存储二叉树结点指针栈为存储二叉树结点指针栈 INISTACK(s)； push(s,bt)； WHILEWHILE NOT EMPTY(s) DODO WHI

21、LEWHILE GETTOP(s)NIL DODO PUSH(s,GETTOP(s).lchild)； p:=POP(s)； IFIF NOT EMPTY(s) THENTHEN visit(GETTOP(s).data)； p:=POP(s)； PUSH(s, p.rchild)ENDPENDP；inorder 根结点先进栈，根结点先进栈， 左结点紧跟根后面左结点紧跟根后面进栈进栈,右结点在根右结点在根出栈后入栈出栈后入栈 每个结点都要进每个结点都要进一次和出一次栈，一次和出一次栈， 并且总是访问栈顶并且总是访问栈顶元素，元素， 因此，因此， 算算法正确，法正确， 时间复时间复杂度为杂度为

22、O(n)。6.4 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二、线索二叉树二、线索二叉树 问题的提出问题的提出：通过遍历二叉树可得到结点：通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在结点的一个线性序列，在线性序列中，就存在结点和前驱和后继，但是在二叉树上只能找到结点和前驱和后继，但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在的左孩子、右孩子，结点的前驱和后继只有在遍历过程中才能得到，那么，能否通过结点的遍历过程中才能得到，那么，能否通过结点的两个链域查找出任一结点的前驱和后继两个链域查找出任一结点的前驱和后继? ?6.4 遍历二叉树和线索二叉树遍历二叉树和

23、线索二叉树2. 2. 分析分析： n n个结点有个结点有n-1n-1个前驱和个前驱和n-1n-1个后继；个后继； 一共有一共有2n2n个链域，其中：个链域，其中：n+1n+1个空链域，个空链域，n-1n-1个指针域；个指针域； 因此因此, , 必须用空链域来存放结点的前驱必须用空链域来存放结点的前驱和后继。线索二叉树就是利用和后继。线索二叉树就是利用n+1n+1个空链域个空链域来存放结点的前驱和后继结点的信息。来存放结点的前驱和后继结点的信息。6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树3. 3. 线索二叉树线索二叉树： 结点结构结点结构在二叉链表中增加在二叉链表中增加 ltag lt

24、ag 和和 rtag rtag 两个标志域两个标志域 lchild ltag data rtag rchild 若结点有左子树，则左链域若结点有左子树，则左链域lchildlchild指示其左孩子指示其左孩子（ltag=0ltag=0）；否则，令左链域指示其前驱（）；否则，令左链域指示其前驱（ltag=1ltag=1）；）； 若结点有右子树，则右链域若结点有右子树，则右链域rchildrchild指示其右孩子指示其右孩子（rtag=0rtag=0）；否则，令右链域指示其后继（）；否则，令右链域指示其后继（rtag=1rtag=1）；）；6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树 称这

25、种结点结构为称这种结点结构为线索链表线索链表； 其中指示前驱和后继的链域称为其中指示前驱和后继的链域称为线索线索； 加上线索的二叉树称为加上线索的二叉树称为线索二叉树线索二叉树； 对二叉树以对二叉树以某种次序某种次序遍历使其变为线索二叉树遍历使其变为线索二叉树的过程称为的过程称为线索化线索化。 按中序遍历得到的线索二叉树称为按中序遍历得到的线索二叉树称为中序线索二中序线索二叉树叉树；按先序遍历得到的线索二叉树称为；按先序遍历得到的线索二叉树称为先序线先序线索二叉树索二叉树；按后序遍历得到的线索二叉树称为；按后序遍历得到的线索二叉树称为后后序线索二叉树序线索二叉树；6.4 遍历二叉树和遍历二叉树

26、和线索二叉树线索二叉树（2 2）整体结构）整体结构 增设一个头结点，令其增设一个头结点，令其lchildlchild指向二叉树的根指向二叉树的根结点，结点，ltag=0ltag=0、rtag=1rtag=1； 并将该结点作为遍历访问的第一个结点的前驱并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；和最后一个结点的后继； 最后用头指针指示该头结点。最后用头指针指示该头结点。acb0 10 01 c 10 01 b 11 a 16.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树4. 4. 遍历线索二叉树遍历线索二叉树： 有了线索二叉树，就容易遍历二叉树了有了线索二叉树，就容易遍历二

27、叉树了只要只要（）先找要遍历的第一个结点；（）先找要遍历的第一个结点；（）然后依次找结点的后继；（）然后依次找结点的后继；（）重复（）直到其后继为头结点（）重复（）直到其后继为头结点 所有问题归为如何在线索二叉树中找结所有问题归为如何在线索二叉树中找结点的后继？点的后继？6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树1 1）遍历中序线索二叉树）遍历中序线索二叉树（1 1）中序线索二叉树中，找结点的后继算法）中序线索二叉树中，找结点的后继算法算法思想算法思想: : 对任意结点对任意结点p p，若，若rtag=1rtag=1，则，则rchildrchild指向该结点的后继；若指向该结点的后继

28、；若rtag=0rtag=0，则，则rchildrchild指向该指向该结点的右孩子，此时，应从右孩子开始，沿左指结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点针前进，直到找到没有左孩子的结点s s（ltag=1ltag=1）, ,则则s s就是就是p p的后继，即后继是中序遍的后继，即后继是中序遍历右子树时，访问的第一个结点；历右子树时，访问的第一个结点；6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树中序线索二叉树中，找结点的后继中序线索二叉树中，找结点的后继算法算法FUNCFUNC in_next(p,thrt:thlinktp):thlinktp；在以t

29、hrt为头指针的中序线索二叉树上,查找指针p所指结点的后继 s:=p.rchild； IFIF p.rtag=0 THEN THEN WHILE WHILE s.ltag=0 DODO s:= s.lchild； RETURN(s)ENDIFENDIF；in_nextp1sp010s6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树（2 2）遍历中序线索二叉树算法）遍历中序线索二叉树算法PROCPROC thrt_inorder(thrt:thlinktp)；遍历以遍历以thrtthrt为头指针的中序线索二叉树为头指针的中序线索二叉树 p:=thrt.lchild； WHILE p.lchi

30、ldthrt DO p:= p.lchild; 定位要遍历的第一个结点定位要遍历的第一个结点. WHILEWHILE pthrt DODO visit(p.data)； p:=in_next(p,thrt)ENDPENDP；thrt_inorder p.ltag=0 6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树2 2）遍历后序线索二叉树）遍历后序线索二叉树（1 1）后序线索二叉树中，找结）后序线索二叉树中，找结点的后继算法点的后继算法算法思想算法思想: : 对任意结点对任意结点p p， 若若p p为二叉树的根，则无后继为二叉树的根，则无后继; ; 若若p p是双亲的右孩子、或是独是双亲

31、的右孩子、或是独生左孩子，则后继为双亲；生左孩子，则后继为双亲； 若若p p是有兄弟的左孩子，则后是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历继为双亲的右子树上按后序遍历时，访问的第一个结点时，访问的第一个结点( (叶结点叶结点) )；spspsps6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树后序线索二叉树中，找结点的后继后序线索二叉树中，找结点的后继算法算法FUNCFUNC post_next(p,thrt:thlinktp):thlinktp；在以在以thrtthrt为头指针的后序线索二叉树上为头指针的后序线索二叉树上, ,查找指针查找指针p p所指所指结点的后继结点的后继

32、s:=parent（thrt，p）；在在thrtthrt上查找上查找p p的双亲的双亲 IF s=thrt THEN RETURN(thrt)； IFIF s.rchild=p OR s.rtag=1 THEN THEN RETURN(s)； WHILEWHILE s.rtag=0 DODO s:= s.rchild； WHILEWHILE s.ltag=0 DO DO s:= s.lchild； RETURN(s)ENDIFENDIF；post_next6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树（2 2）遍历后序线索二叉树算法）遍历后序线索二叉树算法PROCPROC thrt_po

33、storder(thrt:thlinktp)；遍历以遍历以thrtthrt为头指针的后序线索二叉树为头指针的后序线索二叉树 IFIF thrtthrt.lchild THENTHEN p:=thrt.lchild； search:=true； WHILEWHILE search DODO WHILEWHILE p.ltag=0 DODO p:= p.lchild； IFIF p.rtag=0 THENTHEN p:= p.rchild ELSEELSE search:=false； WHILEWHILE pthrt DODO visit(p.data)； p:=post_next(p,thrt

34、)ENDPENDP；thrt_postorder6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树3 3）遍历先序线索二叉树）遍历先序线索二叉树（1 1）先序线索二叉树中，找结点的后继算法）先序线索二叉树中，找结点的后继算法算法思想算法思想: : 对任意结点对任意结点p:p: 若若p p有左孩子，则后继为左孩子有左孩子，则后继为左孩子; ; 若若p p无左孩子无左孩子, ,有右孩子，则后继为右孩子；有右孩子，则后继为右孩子； 若若p p无左孩子无左孩子, ,也无右孩子，则后继为右线索；也无右孩子，则后继为右线索；6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树先序线索二叉树中，找结点的后

35、继先序线索二叉树中，找结点的后继算法算法FUNCFUNC pre_next(p,thrt:thlinktp):thlinktp；在以在以thrtthrt为头指针的先序线索二叉树上为头指针的先序线索二叉树上, ,查找指针查找指针p p所指所指结点的后继结点的后继 IFIF p.ltag=0 THEN THEN RETURN(p.lchild)； ELSEELSE RETURN(p.rchild)ENDIFENDIF;pre_next6.4 遍历二叉树和遍历二叉树和线索二叉树线索二叉树（2 2）遍历先序线索二叉树算法）遍历先序线索二叉树算法PROCPROC thrt_preorder(thrt:t

36、hlinktp)；遍历以遍历以thrtthrt为头指针的先序线索二叉树为头指针的先序线索二叉树 p:=thrt.lchild； WHILEWHILE pthrt DODO visit(p.data)； p:=pre_next(p,thrt)ENDPENDP;thrt_preorder6.树和森林树和森林一树的存储结构一树的存储结构双亲表示法双亲表示法 用一组地址连续的存储单元来存放树的结点，用一组地址连续的存储单元来存放树的结点，每个结点有两个域：每个结点有两个域：datadata域域-存放结点的信息；存放结点的信息；parentparent域域-存放该结点双亲结点的位置存放该结点双亲结点的位

37、置 data parent特点：求结点特点：求结点的双亲很容易，的双亲很容易，但求结点的孩但求结点的孩子需要遍历整子需要遍历整个向量。个向量。6.树和森林树和森林孩子表示法孩子表示法 每个结点的孩子用单链表存储，称为孩子链表。每个结点的孩子用单链表存储，称为孩子链表。 n n个结点可以有个结点可以有n n个孩子链表（叶结点的孩子链个孩子链表（叶结点的孩子链表为空表）。表为空表）。 n n个孩子链表的头指针用一个向量表示。个孩子链表的头指针用一个向量表示。如图：头指针向量孩子链表如图：头指针向量孩子链表特点：与相反，求孩子易，求特点：与相反，求孩子易，求双亲难。双亲难。6.树和森林树和森林双亲孩

38、子表示法双亲孩子表示法 在孩子表示法的头指针向量中，增加一项，用来在孩子表示法的头指针向量中，增加一项，用来表示该结点的双亲。表示该结点的双亲。如图：头指针向量孩子链表如图：头指针向量孩子链表6.树和森林树和森林孩子兄弟表示法孩子兄弟表示法用二叉链表作为树的存储结构，每个结点的左链域指用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。向该结点的第一个孩子，右链域指向下一个兄弟结点。如图：如图：双亲只管长子双亲只管长子长子连接兄弟长子连接兄弟6.树和森林树和森林二、森林、树与二叉树的对应关系二、森林、树与二叉树的对应关系、树与二叉树的对应关系、树与二叉

39、树的对应关系树与二叉树均可用二叉链表作为存储结构，树与二叉树均可用二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。应一棵二叉树，反之亦然。 （）顺时针转度）顺时针转度（）孩子兄弟法）孩子兄弟法树解释：解释：B是是A的第一个孩子，的第一个孩子，C、E是是B的兄弟的兄弟，D是是C的第一个孩子的第一个孩子。解释：是的左孩子，解释：是的左孩子，是的右孩子。是的右孩子。6.树和森林树和森林树变为二叉树的方法树变为二叉树的方法（）在兄弟之间加一连线；（）在兄弟之间加一连线；（）对每一个结点，只保留它与第一个孩子的（）对每一个结点

40、，只保留它与第一个孩子的连线，去掉与其他孩子的连线；连线，去掉与其他孩子的连线；（）以树根为轴心，将整棵树顺时针旋转（）以树根为轴心，将整棵树顺时针旋转4545度。度。 特点特点：根无右子树：根无右子树6.树和森林树和森林2.2.森林与二叉树的对应关系森林与二叉树的对应关系（1 1）森林转换为二叉树的方法）森林转换为二叉树的方法 将森林将森林 F=TF=T1 1，T T2 2 . T Tm m 的各棵树分别转成二叉树的各棵树分别转成二叉树BTBT1 1，BTBT2 2 . BTBTm m 将将BTBTi+1i+1作为作为BTBTi i根结点的右子树根结点的右子树（i=1,2,i=1,2,.,m

41、-1,m-1）, ,得到一棵得到一棵BTBT。6.树和森林树和森林如图：如图： F=T1 ，T2， T3DBCABT1FEBT2BCFEJHADIGT1T3T2BT3HJIGJIFEBDAHGC6. 树和森林树和森林(2)二叉树转换森林的方法二叉树转换森林的方法 将当前根结点和其左子树作为森林的一棵树将当前根结点和其左子树作为森林的一棵树,并并将其右子树作为森林的其他子树；将其右子树作为森林的其他子树； 重复上面直到某结点的右子树为空。重复上面直到某结点的右子树为空。JIHGFEBCDAT1BCDAFET2T3JIHG6.6哈夫曼树及其应用哈夫曼树及其应用哈夫曼树（哈夫曼树（Huffman）树

42、是一类带权路径长度最短的树）树是一类带权路径长度最短的树一、一、Huffman树（最优二叉树）树（最优二叉树）1、概念概念 两结点间的路径：从一结点到另一结点所经过的结点序列两结点间的路径：从一结点到另一结点所经过的结点序列 路径长度：路径上的分支树路径长度：路径上的分支树 树的路径长度：从根到每一结点的路径长度之和树的路径长度：从根到每一结点的路径长度之和2763415例-为结点为结点1到到5之间的路径，其之间的路径，其路径长度为路径长度为2，树的路径长度树的路径长度=l12 +l13+ l14 +l15+ l16 +l17 =1+1+2+2+2+2=106.6哈夫曼树及其应用哈夫曼树及其应

43、用 完全二叉树是路径长度最短的二叉树。完全二叉树是路径长度最短的二叉树。 考虑带权时：设树中有考虑带权时：设树中有m个叶结点，每个个叶结点，每个叶结点带一个权值叶结点带一个权值w且根到叶结点且根到叶结点i的路径长的路径长度为度为 Li (=1，2， m），则树的带权路），则树的带权路径长度为树中所有叶结点的权值与路径长度径长度为树中所有叶结点的权值与路径长度的乘积的总和。的乘积的总和。 即：即： 6.6哈夫曼树及其应用哈夫曼树及其应用 例：使使WPL最小的二叉树成为最优二叉树最小的二叉树成为最优二叉树(Huffman 树树)完全二叉树完全二叉树dcab7 5 2 4 cdba2475WPLa=

44、2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2 =36 =466.6哈夫曼树及其应用哈夫曼树及其应用 Huffman 树树WPLc=7*1+5*2+2*3+4*3 =35bdca7524（1）完全二叉树并）完全二叉树并不一定是不一定是Huffman树；树；（2）HT是权值越大是权值越大的越靠近根结点；的越靠近根结点；（3）HT不唯一，但不唯一，但WPL一定相等。一定相等。6.6哈夫曼树及其应用哈夫曼树及其应用2构造构造 Huffman树算法树算法(1) 以权值分别为以权值分别为W1,W2的各结点，构成的各结点，构成n棵棵二叉树二叉树T1,T2,Tn并组成森林并组成森林F=T1,T2,Tn,其中其中每棵二叉树每棵二叉树 Ti仅有一个权值为仅有一个权值为 Wi的根结点；的根结点；(2) 在在F中选取两棵根结点权值最小的树作为左右子树构造中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值根结点的权值之和（根结点的权值=左右孩子权值之和，左右孩子权值之和，叶结点的权值叶