(8.1)--数据结构第6章树和二叉树.pdf

《(8.1)--数据结构第6章树和二叉树.pdf》由会员分享，可在线阅读，更多相关《(8.1)--数据结构第6章树和二叉树.pdf（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章 树和二叉树章 树和二叉树树型结构树型结构是一类重要的是一类重要的非线性非线性结构，结点之间有结构，结点之间有分支分支，并且具有，并且具有层次层次关系的结构，类似于自然界中的树。关系的结构，类似于自然界中的树。实例实例现实世界：家谱、行政组织机构现实世界：家谱、行政组织机构特点特点一个前驱多个后继一个前驱多个后继提 纲提 纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码树的定义和基本术语树

2、的定义和基本术语树（树（Tree）是是n（n=0）个结点的有限集。在任意一棵非空树中：有且仅有一个特定的称为）个结点的有限集。在任意一棵非空树中：有且仅有一个特定的称为根根的结点的结点(Root)；当；当n1时，其余结点可分为时，其余结点可分为m（m0）个）个互不相交的有限集互不相交的有限集T1,T2,.,Tm，其中每一个集合本身，其中每一个集合本身又是一棵树又是一棵树，并且称为根的子树。，并且称为根的子树。定义定义ADT Tree数据对象：数据对象：D是具有相同特性的数据元素的集合数据关系：基本操作：是具有相同特性的数据元素的集合数据关系：基本操作：TreeDepth(T);Parent(T

3、,cue_e);TraverseTree(T,Visit();ADT Tree;基本术语基本术语结点结点：包含一个数据元素及若干指向其子树的分支。：包含一个数据元素及若干指向其子树的分支。结点的度结点的度：结点拥有的子树数。：结点拥有的子树数。叶子或终端结点叶子或终端结点：度为0的结点。：度为0的结点。非终端结点或分支结点非终端结点或分支结点：度不为0的结点。：度不为0的结点。树的度树的度：树内各结点的度的：树内各结点的度的最大值最大值。孩子和双亲孩子和双亲：结点：结点子树的根子树的根称为该结点的孩子；对应地，该结点称为孩子的双亲结点。称为该结点的孩子；对应地，该结点称为孩子的双亲结点。兄弟兄

4、弟：同一个双亲的孩子之间互称兄弟。：同一个双亲的孩子之间互称兄弟。祖先和子孙祖先和子孙：结点的祖先是从根到该结点所经分支上的所有结点；反之，以某结点为根的子树中的任一结点都称为该结点的子孙。：结点的祖先是从根到该结点所经分支上的所有结点；反之，以某结点为根的子树中的任一结点都称为该结点的子孙。层次层次：结点的层次：结点的层次从根开始定义从根开始定义，根为第一层，根的孩子为第二层，依次类推。，根为第一层，根的孩子为第二层，依次类推。深度深度：树中结点的：树中结点的最大层次最大层次。堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟。：其双亲在同一层的结点互为堂兄弟。森林森林：是：是m（m=0）棵互不相

5、交的）棵互不相交的树的集合树的集合。有序树和无序树有序树和无序树：树中结点的各子树看成从左至右是有次序的（不能互换），则称该树为有序树；否则该树为无序树。：树中结点的各子树看成从左至右是有次序的（不能互换），则称该树为有序树；否则该树为无序树。提 纲提 纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码二叉树二叉树二叉树在树结构的应用中起着非常重要的作用。二叉树在树结构的应用中起着非常重要的作用。为

6、什么？为什么？二叉树二叉树存储容易实现，操作算法简单！存储容易实现，操作算法简单！树，森林树，森林以某种方式转换以某种方式转换注：注：有效控制了树和森林的存储结构及其运算中存在的有效控制了树和森林的存储结构及其运算中存在的复杂性复杂性！二叉树的定义二叉树的定义每个结点至多只有每个结点至多只有二棵子树二棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。，并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的性质二叉树的性质性质性质1 在二叉树的第在二叉树的第i层至多有层至多有2i-1个结点（个结点（i1）。）。性质性质2 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点（个结

7、点（k1）。）。证明证明：20+21+.+2k-1=2k-1性质性质3 对任何一棵二叉树对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0，度为，度为2的结点数为的结点数为n2，则，则n0=n2+1。证明证明：设：设n1为度为为度为1的结点数的结点数n=n0+n1+n2(6-1）设）设B为分支数，有为分支数，有n=B+1；又有分支由；又有分支由1、2度结点射出，度结点射出，B=n1+2n2得，得，n=n1+2n2+1(6-2)由（由（6-1）（）（6-2）得）得n0=n2+1。两种特殊形态的二叉树两种特殊形态的二叉树满二叉树和完全二叉树满二叉树和完全二叉树满二叉树满二叉树：一棵深度

8、为：一棵深度为k有有2k-1个结点的二叉树。个结点的二叉树。完全二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点编号从1至n的结点一一对应时，称为完全二叉树。一一对应时，称为完全二叉树。完全二叉树特点完全二叉树特点：（：（1）叶子结点只可能出现在）叶子结点只可能出现在层次最大层次最大的两层上；（的两层上；（2）对任一结点，若其右分支下的子孙的最大层次为）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为，则其左分支下的子孙的最大

9、层次为l或或l+1。性质性质4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1。证明证明：设深度为：设深度为k，2k-1-1 n 2k-1 2k-1 n 2k k-1 log2n 1,则其双亲则其双亲PARENT(i)是是结点结点i/2。（。（2）如果）如果2in，则结点，则结点i无左孩子（结点无左孩子（结点i为叶子结点）；否则，其左孩子为叶子结点）；否则，其左孩子LCHILD（i）是）是结点结点2i。（。（3）如果）如果2i+1n，则结点，则结点i无右孩子；否则，其右孩子无右孩子；否则，其右孩子RCHILD（i）是结点）是结点2i+1证明证明：i=1时，是根结点

10、，左右孩子的编号是时，是根结点，左右孩子的编号是2,3，两条性质是成立的。假设，两条性质是成立的。假设i=k时成立，时成立，i左孩子编号是左孩子编号是2k，右孩子是，右孩子是2k+1。那么。那么i=k+1时就有两种情况。时就有两种情况。1.k是某层最后一个结点，那么，编号是某层最后一个结点，那么，编号k+1的结点是下层的第的结点是下层的第1个结点，证明如图所示。个结点，证明如图所示。2.k+1是是k同层的下一个结点，基于归纳假设和编号原则，同层的下一个结点，基于归纳假设和编号原则，k+1的左孩子编号是的左孩子编号是2k+2=2（k+1），右孩子编号是），右孩子编号是2k+3=2(k+1)+1，

11、两条性质成立。，两条性质成立。提提 纲纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构用一组用一组连续的存储单元连续的存储单元存储二叉树的数据元素。因此，存储二叉树的数据元素。因此，必须把二叉树的所有结点必须把二叉树的所有结点安排成为一个恰当的序列安排成为一个恰当的序列，结点在，结点在这个序列中的这个序列中的相互位置能反映出结点之间的逻辑关系

12、相互位置能反映出结点之间的逻辑关系（用相（用相对位置描述双亲和左右孩子的关系）。对位置描述双亲和左右孩子的关系）。例：完全二叉树的顺序存储结构例：完全二叉树的顺序存储结构完全二叉树结点编号完全二叉树结点编号（1n），按编号次序依次把对应按编号次序依次把对应结点存入下标结点存入下标1n，依二叉树性质依二叉树性质5，暗示结点之间的关系暗示结点之间的关系注：注：这种结构较适合存储完全二叉树这种结构较适合存储完全二叉树。可能对存储空间造成可能对存储空间造成极大的浪费极大的浪费，在最坏的情况下在最坏的情况下，一个深度为一个深度为H且只有且只有H个结个结点的右单支树点的右单支树，需要需要2h-1个结点存储

13、空间个结点存储空间。而且而且，若经常需若经常需要要插入与删除插入与删除树中结点时树中结点时，顺序存储方式不是很好顺序存储方式不是很好。7链式存储结构链式存储结构typedef struct BiTNodeTElemTypedata;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;lchilddatarchildlchilddata parent rchild含含2个指针域的结点个指针域的结点含含3个指针域的结点个指针域的结点例：例：链式存储结构示意图链式存储结构示意图注：注：在含有在含有n n个结点的二叉链表中个结点的二叉链表中有有n+n+1 1个空

14、链域个空链域。例：三叉链表例：三叉链表 静态二叉链表静态二叉链表有时也可用有时也可用数组的下标来模拟指针数组的下标来模拟指针,即开辟三个一维数组即开辟三个一维数组Data,lchild,rchild 分别存储结点的元素及其左分别存储结点的元素及其左,右指针域右指针域。#define MAX 100ElemType data MAX;int root,lchildMAX,rchildMAX;提提 纲纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转

15、换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码遍历二叉树遍历二叉树遍历二叉树遍历二叉树在二叉树的一些应用中在二叉树的一些应用中，常常要求在树中常常要求在树中查找查找具有某种具有某种特征的结点特征的结点，或者对树中或者对树中全部结点全部结点逐一进行某种逐一进行某种处理处理。这就引入了这就引入了遍历二叉树遍历二叉树的问题的问题，即如何即如何按某条搜索路径按某条搜索路径巡访树中的每一个结点巡访树中的每一个结点，使得每一个结点均被访问一次使得每一个结点均被访问一次，而而且仅被访问一次且仅被访问一次。遍历对线性结构是遍历对线性结构是容易解决容易解决的！的！二叉树是二叉树是非线性的！非线性的！遍历二叉树

16、：遍历二叉树：按某条搜索路径（策略）巡访每个结点，按某条搜索路径（策略）巡访每个结点，使得每个结点均被访问一次，而且仅一次。使得每个结点均被访问一次，而且仅一次。原问题：原问题：遍历二叉树遍历二叉树递归分解递归分解访问根访问根遍历左子树遍历左子树遍历右子树遍历右子树 三种遍历策略三种遍历策略（递归递归）若二叉树为空若二叉树为空，则空操作；则空操作；先序：先序：根根，先序遍历左子树先序遍历左子树，先序遍历右子树先序遍历右子树中序：中序遍历左子树中序：中序遍历左子树，根根，中序遍历右子树中序遍历右子树后序：后序遍历左子树后序：后序遍历左子树，后序遍历右子树后序遍历右子树，根根例：访问序列例：访问序

17、列先序：先序：ABDEGCF中序：中序：DBGEAFC后序：后序：DGEBFCA例：例：已知二叉树的先序和中序序列已知二叉树的先序和中序序列，画出该二叉树画出该二叉树原问题：原问题：画二叉树画二叉树递归分解：递归分解：画根画根画左子树画左子树画右子树画右子树Status PreOrderTraverse(BiTree T,Status(*visit)(TelemType e)if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)return OK;return ERR

18、OR;else return OK;例：例：编写递归算法编写递归算法，计算二叉树中叶子结点的数目计算二叉树中叶子结点的数目int CountLeaves(BiTree bt)if bt=NULL return(0);else if(bt-lchild=NULL&bt-rchild=NULL)return(1);elsereturn(CountLeaves(bt-lchild)+CountLeaves(bt-rchild);例：例：编写按编写按层次顺序层次顺序（同层结点自左至右同层结点自左至右）遍历二叉树的算法遍历二叉树的算法提提 纲纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质

19、二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码线索二叉树线索二叉树问题问题：遍历是二叉树操作中的重要问题：遍历是二叉树操作中的重要问题，基本方法是递归基本方法是递归，递归的效率不高递归的效率不高，如何如何提高遍历的效率提高遍历的效率？分析分析：遍历是：遍历是依照访问次序依照访问次序，依次访问树中的每个结点依次访问树中的每个结点。如如果能果能从访问系列中的前一个结点从访问系列中的前一个结点“找到找到”后一个结点后一个结点（代价代价合理合理），则遍历的过程可以

20、通过则遍历的过程可以通过循环实现循环实现。解决方法解决方法：建立线索二叉树：建立线索二叉树线索线索物质基础：物质基础：n个结点的二叉链个结点的二叉链表中有表中有n+1个空指针个空指针建立线索：建立线索：利用空指针利用空指针，指向指向访问序列的前驱访问序列的前驱（若左指针空若左指针空）或后继或后继（若右指针空若右指针空）例：例：中序序列中序序列:DBFEAC规定规定：若结点有左子树若结点有左子树，则其则其lchildlchild域指示其域指示其左孩子左孩子，否则令其否则令其lchildlchild域指示域指示其其前驱前驱；若结点有右子树若结点有右子树，则其则其rchildrchild域指示其域指

21、示其右孩子右孩子，否则令其否则令其rchildrchild域指示域指示其其后继后继；其中其中：域指示结点的后继域指示结点的右孩子域指示结点的前驱域指示结点的左孩子rchildrchildRTaglchildlchildLTag1010lchildLTagdataRTagrchild例：中序线索二叉树例：中序线索二叉树中序：中序：D B F EAC约定：约定：头结点的头结点的lchild指向根结点；指向根结点；rchild指向中序遍历指向中序遍历的最后一个结点；同时的最后一个结点；同时，二叉树中序遍历的第一个结点的二叉树中序遍历的第一个结点的lchild和最后一个结点的和最后一个结点的rchil

22、d指向头结点指向头结点中序线索二叉树的遍历中序线索二叉树的遍历如何在中序线索二叉树中如何在中序线索二叉树中利用利用循环实现中序遍历循环实现中序遍历？lchildLTagdataRTagrchild利用指针利用指针p，从第，从第1个访问的结个访问的结点出发，通过循环不断找后继的点出发，通过循环不断找后继的方式实现遍历。方式实现遍历。当当p回到头结点，回到头结点，循环结束循环结束。p从树根结点出发，从树根结点出发，不断向左，不断向左，找到最左下的结点找到最左下的结点，例中是结点，例中是结点D，这是中序第，这是中序第1个访问的结点，个访问的结点，访问它；随后找后继，分两种情访问它；随后找后继，分两种

23、情况：况：1，目前访问结点的，目前访问结点的Rtag=1，说，说明明rchild指向后继，则：指向后继，则：p=p-rchild 即可。即可。2.目前访问结点的目前访问结点的Rtag=0，说明，说明有右子树，有右子树，rchild指向右孩子，指向右孩子，则则p=p-rchild，让，让p指向右子树指向右子树根，然后不断向左，找到右子树根，然后不断向左，找到右子树最左下的结点，就是下一个要访最左下的结点，就是下一个要访问的结点。问的结点。后序线索二叉树的遍历后序线索二叉树的遍历找后继：设找后继：设x x为树中的结点为树中的结点 若结点若结点x x是二叉树的根是二叉树的根，则则后继为空；后继为空；

24、若结点若结点x x是其双亲的是其双亲的右孩子或右孩子或是双亲的左孩子且其双亲没有右是双亲的左孩子且其双亲没有右子树子树，则其后继为双亲结点；则其后继为双亲结点；若结点若结点x x是是其双亲的左孩子其双亲的左孩子，且其双亲有右子树且其双亲有右子树，则其后继为双则其后继为双亲的右子树上按后序遍历的第一个亲的右子树上按后序遍历的第一个结点；结点；提 纲提 纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码

25、树的存储结构树的存储结构 双亲表示法双亲表示法顺序存储，每个结点附设顺序存储，每个结点附设一个指示器一个指示器指示其双亲（双亲唯一）指示其双亲（双亲唯一）nodes#define MAX_TREE_SIZE 100typedef struct /结点结构结点结构ElemType data;int parent;/双亲位置域双亲位置域 PTNode;typedef struct/树结构树结构PTNode nodesMAX_TREE_SIZE;int r,n;/根的位置和结点数根的位置和结点数 PTree;孩子表示法孩子表示法（指出每个结点的孩子）（指出每个结点的孩子）1每个结点含指向孩子的每个结

26、点含指向孩子的多个指针域多个指针域。datachild1child2.childd2 每个结点的每个结点的孩子排成一个单链表孩子排成一个单链表，所有结点存在一个顺序表中，所有结点存在一个顺序表中孩子表示法孩子表示法存储结构定义存储结构定义孩子兄弟表示法孩子兄弟表示法二叉链表表示法，结点中二叉链表表示法，结点中两个链域两个链域分别指向该结点的分别指向该结点的第一个孩子结点和下一个兄弟结点第一个孩子结点和下一个兄弟结点。typedef struct CSNodeElemTypedata;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;例：例

27、：提提 纲纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码森林和二叉树的转换森林和二叉树的转换1.给定一棵树给定一棵树，可以找到可以找到唯一一棵二叉树与之对应唯一一棵二叉树与之对应。2.森林和二叉树的森林和二叉树的对应关系对应关系（第二棵树的根结点是第一棵树根第二棵树的根结点是第一棵树根结点的兄弟结点的兄弟,以次类推以次类推）树和森林的遍历树和森林的遍历 树的遍历树的遍历先序：先序：根根，依次先序

28、遍历根的每棵子树依次先序遍历根的每棵子树后序：依次后序遍历根的每棵子树后序：依次后序遍历根的每棵子树，根根例：例：先序：先序：ABCDE后序：后序：BDCEA当当以二叉链表作为树的存储结构以二叉链表作为树的存储结构后后树的先序树的先序=二叉树的先序二叉树的先序树的后序树的后序=二叉树的中序二叉树的中序森林的遍历森林的遍历先序：先序：第一棵树的根第一棵树的根，先序遍历第一棵树中根的子树森林先序遍历第一棵树中根的子树森林，先序遍历其余树组成先序遍历其余树组成的森林的森林。中序：中序遍历第一棵树中根的子树森林中序：中序遍历第一棵树中根的子树森林，第一棵树的根第一棵树的根，中序遍历其余树组成中序遍历其

29、余树组成的森林的森林。例：例：森林的先序和中序序列森林的先序和中序序列先序：先序：ABCDEFGHIJ中序：中序：BCDAFEHJIG提 纲提 纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码赫夫曼树及其应用赫夫曼树及其应用概念定义概念定义路径路径：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度路径长度：路径上的分

30、支数目。：路径上的分支数目。树的路径长度树的路径长度：从树根到每个结点的路径长度之和。：从树根到每个结点的路径长度之和。结点的带权路径长度结点的带权路径长度：结点到根的路径长度乘以结点的权值。：结点到根的路径长度乘以结点的权值。树的带权路径长度树的带权路径长度：所有叶结点的带权路径长度之和。：所有叶结点的带权路径长度之和。最优二叉树（赫夫曼树）最优二叉树（赫夫曼树）假设有假设有n个权值个权值w1,w2,.,wn，试构造一棵有，试构造一棵有n个叶子结点个叶子结点的二叉树，每个叶子结点的二叉树，每个叶子结点带权为带权为wi，则其中带权路径长度，则其中带权路径长度WPL最小最小的二叉树称做的二叉树称

31、做最优二叉树或赫夫曼树最优二叉树或赫夫曼树。WPL=72+52+22+42=36 WPL=73+53+21+42=46WPL=71+52+23+433=35例：例：4个叶子结点个叶子结点a,b,c,d，分别带权值，分别带权值7、5、2、4，三棵树的带权路径长度分别为。，三棵树的带权路径长度分别为。例：例：转换五分制的判定树转换五分制的判定树if(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b=“general”;else if(a90)b=“good”;else b=“excellent”;分数分数0-5960-6970-7980-8990-100

32、比例数比例数0.050.150.40.30.1人数人数5001500400030001000比较次数比较次数=500+1500*2+4000*3+3000*4+1000*4=31500比较次数比较次数：22000次比较次比较赫夫曼树的构造赫夫曼树的构造（1）根据给定的）根据给定的n个权值个权值w1,w2,.,wn构成构成n棵二叉树的集合棵二叉树的集合F=T1,T2,.,Tn，其中每棵二叉树，其中每棵二叉树Ti中中只有一个带权为只有一个带权为wi的根结点的根结点，其左右子树均空。（，其左右子树均空。（2）在）在F中中选取两棵根结点的权值最小的树选取两棵根结点的权值最小的树作为左右子树构造一棵新的

33、二叉树，且置新的二叉树的根结点的权值为其作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和左、右子树上根结点的权值之和。（。（3）在）在F中中删除删除这两棵树，同时将新得到的二叉树加入这两棵树，同时将新得到的二叉树加入F中。（中。（4）重复（）重复（2）（）（3），直到），直到F只含有一棵树为止。这棵树便是赫夫曼树。只含有一棵树为止。这棵树便是赫夫曼树。例：例：Huffman树的构造实例：权值树的构造实例：权值2、5、6、7、9提 纲提 纲 树的定义和基本术语树的定义和基本术语 二叉树和二叉树的性质二叉树和二叉树的性质 二叉树的存储结构二叉树的存储结构

34、 遍历二叉树遍历二叉树 线索二叉树线索二叉树 树的存储树的存储 树的转换与遍历树的转换与遍历 赫夫曼树赫夫曼树 赫夫曼编码赫夫曼编码赫夫曼编码例：赫夫曼编码例：A B C D 四个字符的编码四个字符的编码等长编码：等长编码：AB C D为为00，01，10，11ABACCDA 00010010101100不等长编码不等长编码（出现多的字符用较短的编码）（出现多的字符用较短的编码）AB C D为为0，00，1，01ABACCDA 000011010问题：译码有二义性。问题：译码有二义性。000011010 可以译为：可以译为：AAAACCDABBCCACA 等不同电文等不同电文前缀编码前缀编码：

35、要设计不等长编码，则必须是任一个字符的编码都：要设计不等长编码，则必须是任一个字符的编码都不是不是另一个字符编码的前缀。另一个字符编码的前缀。二叉树用于编码二叉树用于编码设每种字符在电文中出现的次数为设每种字符在电文中出现的次数为wi，其编码长度为，其编码长度为li，电文中只有，电文中只有n种字符，则电文的总长度为种字符，则电文的总长度为电文总长度电文总长度=iinilw1若置若置wi为叶子结点，为叶子结点，li恰为从根到叶子的路径长度恰为从根到叶子的路径长度，则电文总长度为二叉树上的带权路径长度。，则电文总长度为二叉树上的带权路径长度。目的：目的：设计电文总长度最短的设计电文总长度最短的二进制二进制前缀编码的问题，前缀编码的问题，转换为转换为以以n种字符出现的频率作权，种字符出现的频率作权，设计一棵赫夫曼树设计一棵赫夫曼树的问题。的问题。每个字符的译码都是从每个字符的译码都是从赫夫曼树根开始赫夫曼树根开始，用一个指针指向，用一个指针指向赫夫曼树根赫夫曼树根的根的根1.读入电文编码，如果是读入的是读入电文编码，如果是读入的是0，p指针走向左孩子；读入指针走向左孩子；读入1，p走到右孩子。随后读入下一个。走到右孩子。随后读入下一个。2.重复重复1，直到走到一个叶子，叶子对应的字符就是译码的结果，直到走到一个叶子，叶子对应的字符就是译码的结果怎样译码怎样译码