数据结构树与二叉树课件

1、数据结构树与二叉树1第第5章章 树和二叉树（树和二叉树（ Tree & Binary Tree ）特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继。直接后继。（一对多或（一对多或1:n1:n）5.1 树的概述树的概述5.2 二叉树定义和性质二叉树定义和性质5.3 遍历二叉树遍历二叉树5.4 线索二叉树线索二叉树5.5 树和森林树和森林5.6 哈夫曼及其应用哈夫曼及其应用数据结构树与二叉树25.1 树的基本概念1. 树的定义树的定义2. 若干术语若干术语3. 逻辑结构逻辑结构4.存储结构存储结构5. 树的运算树的运算数据结构树与二叉树3注注

2、1：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。由一个或多个由一个或多个( (n0n0) )结点组成的有限集合结点组成的有限集合T T，有且，有且仅有仅有一个结点称为根一个结点称为根（rootroot），），当当n1n1时，其余的结时，其余的结点分为点分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根的每个集合本身又是棵树，被称作这个根的子树子树 。数据结构树与二叉树4树的表示法主要有树的表示法主要有5种：种：v 图形表示法图形表示法v 嵌套集合表示法嵌套集合表示法v 广义表表示法广义表表

3、示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法数据结构树与二叉树5教师教师学生学生其他人员其他人员20022002级级20032003级级20042004级级20052005级级华科大武昌分校华科大武昌分校电信系电信系计算机系计算机系自控系自控系叶子叶子根根子树子树数据结构树与二叉树6数据结构树与二叉树7( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个

4、链域麻烦问题：应当开设多少个链域?数据结构树与二叉树8(又称目录表示法又称目录表示法)数据结构树与二叉树9左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩子 右兄弟右兄弟数据结构树与二叉树102. 若干术语若干术语即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为非终端结点）的结点（也称为非终端结点）所有结点度中的最

5、大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度，亦称（有几个直接后继就是几度，亦称“次数次数”）ABCGEIDHFJFLK数据结构树与二叉树11一对多（一对多（1:n1:n），），有多个直接后继（如家谱树、有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且目录树等等），但只有一个根结点，且子树子树之间互不相交之间互不相交。 讨论讨论1：树是非线性结构，该怎样存储？树是非线性

6、结构，该怎样存储？特点：特点：仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 数据结构树与二叉树125.2 5.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？ 二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的定义二叉树的定义2. 二叉树的性质二叉树的性质3. 二叉树的存储结构二叉树的存储结构（二叉树的运算见（二叉树的运算见5.3节）节）数据结构树与二叉树13定义：定义：是是

7、n（n0）个结点的有限集合，由一个根结点以及两棵）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成 。逻辑结构：逻辑结构： 一对二（一对二（1:2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。 基本形态：基本形态：一般的一般的树有几树有几种？种？数据结构树与二叉树14讨论讨论1 1：第：第i i层的结点数最多是多少？层的结点数最多是多少？ （利用二进制性质可轻松求出）（利用二进制

8、性质可轻松求出） 性质性质1: 1: 性质性质2: 2: 再提问：第再提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，最多有多少个结点？的二叉树，最多有多少个结点？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出）数据结构树与二叉树15讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1 （即（即n0

9、=n2+1）二叉树中全部结点数二叉树中全部结点数nn0+n1+n2( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) )二叉树中全部结点数二叉树中全部结点数nB+1 ( ( 总分支数根结点总分支数根结点 ) ) （除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）总分支数总分支数B= n1+2n2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1数据结构树与二叉树162.2.深度为的二叉树的结点总数，最多为深度为的二叉

10、树的结点总数，最多为 个。个。 ) )k-1k-1 ) log) log2 2k k ) ) k k ) )k k1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度DCC3. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 1课堂练习：课堂练习：数据结构树与二叉树17满二叉树：满二叉树：一棵深度为一棵深度为k 且有且有2k -1个结点的二叉树。个结点的二叉树。 （特点：每层都（特点：每层都“充满充满”了结点）了结点）完全二

11、叉树：完全二叉树：深度为深度为k 的的、有有n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k 的满二叉树中编号从的满二叉树中编号从1至至n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树完全二叉树完全二叉树ABCGEIDHFJ为何要研究为何要研究这两种特殊这两种特殊形式？形式？完全二叉树的特点是只有最后一层叶子不满，完全二叉树的特点是只有最后一层叶子不满，且全部集中在左边。但这其实是且全部集中在左边。但这其实是顺序二叉树顺序二叉树的含义。而的含义。而图论图论中的中的“完全二叉树完全二叉树”是指是

12、指n1=0的情况。的情况。因为它们在顺序存储因为它们在顺序存储方式下可以复原！方式下可以复原！数据结构树与二叉树18对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树）, ,还特别具备以下还特别具备以下2 2个性质：个性质：证明：证明：根据性质根据性质2 2，深度为，深度为k k的二叉树最多只有的二叉树最多只有2 2k k-1-1个结点，且个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，层满二叉树容量之间

13、，即即2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n2n2k k三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk n1)f=n*fact(n-1); else f=1; return(f); 用递归形式格外简单！用递归形式格外简单！回忆回忆1 1：二叉树结点二叉树结点的数据类型定义：的数据类型定义：则三种遍历算法可写出则三种遍历算法可写出: :数据结构树与二叉树28LDR(node *root)if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rc

14、hild); return(0);LRD (node *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);typedef struct nodeint data; struct node *lchild,*rchild； node;node *root; DLR( node *root )if (root !=NULL) /非空二叉树非空二叉树 printf(“%d”,root-data); /访问访问D DDLR(root-lchild); /递归遍历左子树递归

15、遍历左子树DLR(root-rchild); /递归遍历右子树递归遍历右子树 return(0); 数据结构树与二叉树29对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，只是访问结点的时机不同访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问，是经过时

16、访问，是先根先根遍历遍历第第2次次经过时访问，是经过时访问，是中根中根遍历遍历第第3次次经过时访问，是经过时访问，是后根后根遍历遍历2. 2. 二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率: : /每个结点只访问一次每个结点只访问一次空间效率空间效率: : /栈占用的最大辅助空间栈占用的最大辅助空间精确值：树深为精确值：树深为k k的递归遍历需要的递归遍历需要k+1k+1个辅助单元个辅助单元数据结构树与二叉树30用空格字符表示用空格字符表示无孩子无孩子或指针或指针为空为空注：注：要实现遍历运算，必须先把二叉树存入电脑内要实现遍历运算，必须先把二叉树存入电脑内怎样

17、建树？怎样建树？例：将下面的二叉树以二叉链表形式存入计算例：将下面的二叉树以二叉链表形式存入计算机内。机内。考虑考虑1 1：输入结点时怎样表示输入结点时怎样表示“无孩子无孩子”？考虑考虑2 2：以何种遍历方式来输入和建树？以何种遍历方式来输入和建树？将二叉树按先序遍历次序输入：将二叉树按先序遍历次序输入：A B C D E G F 以先序遍历最为合适，以先序遍历最为合适，让每个结点都能及时让每个结点都能及时被连接到位。被连接到位。数据结构树与二叉树31建树算法：建树算法：Status CreateBiTree( BiTree &T ) /构造二叉树构造二叉树T Tscanf(“%c”,

18、&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输入序列：输入序列： A B C D E G F 数据结构树与二叉树32问：问：用二叉链表法（用二叉链表法（l_child, r_child）存储包含）存储包含n个结点的个结点的二叉树，结点的

19、指针区域中会有多少个二叉树，结点的指针区域中会有多少个空空指针？指针？思考：思考：二叉链表空间效率这么低，能否利用这些空闲区存放二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？有用的信息或线索？ 我们可以用它来存放当前结点的直接前驱和后继等我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。线索，以加快查找速度。所以，所以， 空指针数目空指针数目2n(n-1)=n+1个个。分析：分析：用二叉链表存储包含用二叉链表存储包含n n个结点的二叉树，结点必有个结点的二叉树，结点必有2n个链域个链域（见二叉链表数据类型说明）（见二叉链表数据类型说明）。除根结点外，二叉树中每

20、一个结点除根结点外，二叉树中每一个结点有且仅有一个双亲有且仅有一个双亲（直接前驱），所以只会有（直接前驱），所以只会有n n1 1个结点的链域存放指针，指个结点的链域存放指针，指向非空子女结点（即直接后继）。向非空子女结点（即直接后继）。数据结构树与二叉树33思考：思考：二叉链表空间效率这么低，能否利用这些空二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？闲区存放有用的信息或线索？我们可以用它来存放当前结点的我们可以用它来存放当前结点的直接前驱和后直接前驱和后继继等线索，以加快查找速度。等线索，以加快查找速度。用二叉链表法存储包含用二叉链表法存储包含n n个结点的二叉树，结点的

21、指个结点的二叉树，结点的指针区域中会有针区域中会有n+1n+1个空指针。个空指针。这就是这就是线索二叉树线索二叉树（Threaded Binary Tree）数据结构树与二叉树345.4 线索二叉树线索二叉树（Threaded Binary Tree）二叉树中容易找到结点的二叉树中容易找到结点的左右孩子左右孩子信息，但该结点的直信息，但该结点的直接前驱和直接后继只能在某种遍历过程中接前驱和直接后继只能在某种遍历过程中动态动态获得。获得。先依先依遍历规则遍历规则把每个结点对应的把每个结点对应的前驱前驱和和后继线索后继线索预存预存起起来，这叫做来，这叫做“线索化线索化”。意义：从意义：从任一结点任

22、一结点出发都能快速找到其前驱和后继，且出发都能快速找到其前驱和后继，且不必借助堆栈。不必借助堆栈。 对二叉树进行某种遍历之后，将得到一个线性有序的序列。对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的例如对某二叉树的中序遍历中序遍历结果是结果是B D C E A F H GB D C E A F H G，意味着，意味着已将该树转为线性排列，显然其中结点已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后具有唯一前驱和唯一后继。继。在此前提下，那在此前提下，那n+1个空链域才可能装得下个空链域才可能装得下“线索线索”。讨论讨论1 1：二叉树是二叉树是1:21:2的非线性结构

23、，其直接后继可能不止一的非线性结构，其直接后继可能不止一个，如何存放？个，如何存放？讨论讨论2.2.如何获得这种如何获得这种“直接前驱直接前驱”或或“直接后继直接后继”？有何意？有何意义？义？数据结构树与二叉树35 每个结点增加两个域：每个结点增加两个域：fwd和和bwd；存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存这类信息？有两种解决方法：如何预存这类信息？有两种解决方法： 与原有的左右孩子指针域与原有的左右孩子指针域“复用复用”，充分利用那，充分利用那n+1个空链域。个空链域。规规 定：定：1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子； 否则

24、，否则， lchild指向其直接前驱指向其直接前驱(即线索即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子； 否则，否则，rchild指向其直接后继指向其直接后继(即线索即线索) 。datalchildrchildfwdbwddatalchildrchild缺点：空间效率太低！缺点：空间效率太低！问题：计算机如何问题：计算机如何判断是孩子指针还判断是孩子指针还是线索指针？是线索指针？如何区别？如何区别？数据结构树与二叉树36lchildLTagdataRTag rchild约定约定:当当Tag域为域为0时时,表示表示正常正常情况情况;当当Tag域为域为

25、1时时,表示表示线索线索情况情况.前驱前驱(后继后继)左左(右右)孩子孩子为区别两种不同情况，特增加两个标志域：为区别两种不同情况，特增加两个标志域：问：问：增加了前驱和后继等线索有什么好处？增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。堆栈（递归）也能遍历整个树。各各1bit1bit数据结构树与二叉树371. 有关线索二叉树的几个术语：有关线索二叉树的几个术语： 线索链表：线索链表： 线线 索：索：线索二叉树：线索二叉树： 线线 索索 化：化：用用含含Tag的结点样式所构成的二叉链表的结点样式所构成的二叉

26、链表指向结点前驱和后继的指针指向结点前驱和后继的指针加上线索的二叉树加上线索的二叉树对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索使其变为线索二叉树的过程二叉树的过程yyyyyy线索化过程就是在遍历过程中修改空指针的过程：线索化过程就是在遍历过程中修改空指针的过程：将空的将空的lchildlchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的rchildrchild改为结点的直接后继。改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）数据结构树与二叉树38dataAGEIDJHCFBltag0011110101rt

27、ag0001010111AGEIDJHCFB例：例：带了带了两个标志两个标志的某的某先序遍历先序遍历结果如下表所示，结果如下表所示，请画出对应的二叉树。请画出对应的二叉树。A数据结构树与二叉树39ABCGEIDHFroot悬空？悬空？ NILNIL悬空？悬空？ NILNIL解：解：对该二叉树中序遍历的结果为对该二叉树中序遍历的结果为: : H, D, I, B, E, A, F, C, G所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点例例1 1：画出以下二叉树对应的画出以下二叉树对应的中序中序线索二叉树。线索二叉树。

28、2. 2. 线索二叉树的生成线索二叉树的生成线索化线索化线索化过程就是在遍历过线索化过程就是在遍历过程中修改空指针的过程程中修改空指针的过程数据结构树与二叉树4000A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为: : H, D, I, B, E, A, F, C, G0root0对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：数据结构树与二叉树41线索二叉树的生成算法线索二叉树的生成算法（递归算法见教材）递归算法见教材）实质：实质：在遍历二叉树的过程中修改空指针，添加前驱或后继在遍历二叉树的过程中修改空指针，添加前驱

29、或后继的线索，使之成为线索二叉树。的线索，使之成为线索二叉树。为了记下遍历过程中访问结点的先后次序，需要设置两个指针：为了记下遍历过程中访问结点的先后次序，需要设置两个指针：p指针指针当前结点之指针；当前结点之指针；pre指针指针当前结点的前趋结点指针。当前结点的前趋结点指针。设计技巧设计技巧：依某种顺序：依某种顺序遍历二叉树，对每个结点遍历二叉树，对每个结点p，判断其左指，判断其左指针是否为空，以及其针是否为空，以及其前驱结点的前驱结点的右指针是否为空。右指针是否为空。每次只修改前驱结点的右指针（后继）和本结点的左指针（前每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见算法。

30、驱），参见算法。若若p-lchildNULL, ,则则p-Ltag=1;p-Ltag=1;p-lchildp-lchildpre;pre; /p/p的前驱线索应存的前驱线索应存p p结点的左边结点的左边若若pre-rchildNULL, 则则pre-Rtagpre-Rtag1;1;pre-rchild=ppre-rchild=p; /pre /pre的后继线索应存的后继线索应存prepre结点的右边结点的右边数据结构树与二叉树423. 3. 线索二叉树的遍历线索二叉树的遍历（无需堆栈）（无需堆栈）对于线索二叉树的遍历，只要找到序列中的对于线索二叉树的遍历，只要找到序列中的第一个第一个结结点，然

31、后点，然后依次访问结点的后继依次访问结点的后继直到后继为空为止。直到后继为空为止。（因为建立线索时已遍历一次，相当于线性化了！）（因为建立线索时已遍历一次，相当于线性化了！）难点：难点：在线索化二叉树中，并不是每个结点都能在线索化二叉树中，并不是每个结点都能直接找到其后继的，直接找到其后继的，当标志为当标志为0 0时，则需要通过一时，则需要通过一定运算才能找到它的后继。定运算才能找到它的后继。以以中根线索二叉树中根线索二叉树为例：为例：当当RTag=1时，直接后继指针就在其时，直接后继指针就在其rchild域内；域内；当当RTag=0时，直接后继是当前结点时，直接后继是当前结点的结点的结点；请

32、注意中序遍历规则是请注意中序遍历规则是LDR，数据结构树与二叉树435.5 树和森林1.树和森林的存储方式树和森林的存储方式2.树和森林与二叉树的转换树和森林与二叉树的转换3. 树和森林的遍历树和森林的遍历数据结构树与二叉树441. 1. 树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子孩子兄弟表示法兄弟表示法 1 1、用双亲表示法存储、用双亲表示法存储思路：思路：用一组用一组连续空间连续空间来存储树的结点，同时在每个来存储树的结点，同时在每个结点中结点中附设一个指示器附设一个指示器，指示其双亲结点在链表中的，指示

33、其双亲结点在链表中的位置。位置。parentdata结点结构结点结构dataparent1树结构树结构 23n数据结构树与二叉树45RABCDEFGHK-1000例例1: 双亲表示法双亲表示法缺点：求结点的孩子缺点：求结点的孩子时需要遍历整个结构时需要遍历整个结构1136668976543210数据结构树与二叉树46思路：思路：对对n n个结点分别设立个结点分别设立n n个孩子链表，结点为个孩子链表，结点为表头；表头； 再将再将n n个表头用数组存放个表头用数组存放起来，形成一个起来，形成一个混合结构混合结构。例如例如：abecdfhgdefghgfedcbah123456782 2、用孩子表

34、示法存储、用孩子表示法存储bc数据结构树与二叉树47思路：思路：用二叉链表用二叉链表来表示树，但链表中的两个指针来表示树，但链表中的两个指针域含义不同。域含义不同。 左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3 3、用孩子、用孩子兄弟表示法存储兄弟表示法存储指向左孩子指向左孩子指向右兄弟指向右兄弟数据结构树与二叉树48abecdfhgbacedfgh问：问：树树二叉树的二叉树的“连线连线抹线抹线旋转旋转” ” 如如何由计算机自动实现？何由计算机自动实现？答：

35、答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。例如例如：数据结构树与二叉树492. 树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1: step1: 将树中同一结点的兄弟相连将树中同一结点的兄弟相连; ;加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？孩子孩子兄弟兄弟表示法表示法step2: step2: 保留结点的最左孩子连线，保留结点的最左孩子连线，删除其它孩子连线；删除其它孩子连线；step3: step3: 将同一孩子的连线绕左孩子将同一孩子的连线绕左孩子旋转旋转4545度角。度角。数据结构树与二叉树50

36、方法：方法：加加线线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左数据结构树与二叉树51讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：要点：逆操作，把所有右孩子变为兄弟！逆操作，把所有右孩子变为兄弟！ abdefhgic数据结构树与二叉树52法一：法一： 各森林先各自转为二叉树；各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？即即F=TF=T1 1, T, T2 2, ,T

37、, ,Tm m B=root, LB, RB B=root, LB, RB法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材，两种方法都有转换示意图）（参见教材，两种方法都有转换示意图）法一和法二得到的二叉法一和法二得到的二叉树是完全相同的、惟一树是完全相同的、惟一的、的、数据结构树与二叉树53ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举例：森林转二叉树举例：（采用法二）（采用法二）兄弟相连兄弟相连 长兄为父长兄为父头树为根头树为根 孩子靠左孩子靠左数据结构树与二叉树54BCDEFGHJI讨论讨论4 4：二叉树如何还原为森林？：二叉树如何

38、还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 即即B=root, LB, RB F=TB=root, LB, RB F=T1 1, T, T2 2, ,T, ,Tm m ABCDEFGHJIEFABCDGHJI数据结构树与二叉树555.65.6 Huffman Huffman树及其应用树及其应用一、一、HuffmanHuffman树树二、二、HuffmanHuffman编码编码最优二叉树最优二叉树HuffmanHuffman树树HuffmanHuffman编码编码带权路径带权路径长度最短长度最短的树的树不等长编码不等长编码是通信是

39、通信中最经中最经典的压典的压缩编码缩编码数据结构树与二叉树56一、最优二叉树一、最优二叉树（HuffmanHuffman树）树）路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：HuffmanHuffman树树：由一结点到另一结点间的分支所构成。由一结点到另一结点间的分支所构成。路径上的分支数目。路径上的分支数目。从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积（结点到根的路径长度与结点上权的乘积（WPLWPL）若干术语：若干术语：debacf g树中所有树中所有叶子结点叶子结点

40、的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 21010HuffmanHuffman常译为常译为赫夫曼赫夫曼、霍夫曼霍夫曼、哈夫曼哈夫曼等等Weighted Path LengthWeighted Path Length数据结构树与二叉树57树的带权路径长度树的带权路径长度如何计算？如何计算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：经典之例：WPL=WPL=WPL=Huffman树是树是WPL WPL 最小的树最小的

41、树树中所有叶子结树中所有叶子结点的带权路径长点的带权路径长度之和度之和364635数据结构树与二叉树581. 1. 构造构造Huffman树的基本思想：树的基本思想：设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为，出现的频度分别为7,5,2,47,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？怎样编码才能使它们组成的报文在网络中传得最快？法法1 1：等长编码：等长编码（如二进制编码）（如二进制编码）令令d=d=0000，i=i=0101，a=a=1010，n=n=1111，则：，则：WPLWPL1 12bit2bit(7(75 52 24 4）3636法

42、法2 2：不等长编码：不等长编码（如（如HuffmanHuffman编码）编码）令令d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111，则：，则：明确：要实现明确：要实现HuffmanHuffman编码，就要先构造编码，就要先构造HuffmanHuffman树树讨论：讨论：HuffmanHuffman树有什么用？树有什么用？权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。WPLWPL最小的树最小的树频度高的信息频度高的信息用短码，反之用短码，反之用长码，传输用长码，传输效率肯定高！效率肯定高！信息高效传输信息高效传输WPL

43、WPL2 2= =1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535数据结构树与二叉树592. 2. 构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：怎样证明它就是怎样证明它就是WPL最小的最优二叉树？最小的最优二叉树？ 参考参考信源编码信源编码数据结构树与二叉树60step1step1：在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权具体操作步骤：具体操作步骤：a. 初始初始方框表示外结点方框表示外结点（叶子，字符）（叶子，字符）圆框

44、表示内结点（合并圆框表示内结点（合并后的权值）后的权值）b. 合并合并2 4c. 合并合并5 6d. 合并合并7 11数据结构树与二叉树61step2step2：d da ai in n1 11 11 10 00 00 0HuffmanHuffman编码结果：编码结果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=WPL=1bit1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535（小于等长码的（小于等长码的WPL=36WPL=36）HuffmanHuffman编码也编码也HuffmanHuffman树树 与与 HuffmanHuffman编码编码 挂钩挂钩数据结构树与二叉树62二、二、HuffmanHuffman编码编码由于由于哈夫曼树的哈夫曼树的WPLWPL最小，说明编码所需要的比特数最少。这最小，说明编码所需要的比特数最少。这种编码已广泛应用于