《数据结构复习树与二叉树课件.ppt》由会员分享，可在线阅读，更多相关《数据结构复习树与二叉树课件.ppt（18页珍藏版）》请在三一办公上搜索。
1、数据结构复习(树与二叉树),一、二叉树或空，或由根和由互不相交的左子树、右子树构成。1、二叉链,第六章 树和二叉树,a,b,c,d,f,g,e,a,b,c,e,d,f,g,性质1：在二叉树的第i(i0)层上至多有2i-1个结点。性质2：深度为k的二叉树中至多有2k-1个结点(k0)。性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则 n0=n2+1。性质4：有n个结点的完全二叉树的深度为+1。,2、二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树按层序从1开始编号，则对任一结点(i1,则其双亲结点是i/2。(2)如果2i=n,则结点i的左孩 子是结点2i；否则结
2、点i无 左孩子。(3)如果2i+1=n,则结点i的右 孩子是结点2i+1；否则结 点i无右孩子。,例.32个结点的完全二叉树，从根开始，按层次从左到右用1-32编号。请回答：（1）它共有多少层？（2）各层最左边的结点的编号是多少？（3）编号为6的结点的左孩子的编号是多少？它的右孩子呢？（4）编号为16的结点的左孩子的编号是多少？它的右孩子呢？（5）对于编号为8的结点，它的父结点的编号是多少？编号为13的结点呢？编号为1的结点呢？,二叉树的遍历：按某条搜索路径访问二叉树中每一个结点，使得每个结点被访问一次且仅被访问一次。遍历方法有4种：先序遍历，中序遍历，后序遍历，层次遍历。,3、二叉树的遍历,
3、先序遍历二叉树：（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序遍历序列：abcdfge,1,2,3,4,5,6,7,a,b,c,d,f,g,e,中序遍历二叉树：（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树中序遍历序列：bafgdce,a,b,c,d,f,g,e,1,2,3,4,5,6,7,后序遍历二叉树：（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点后序遍历序列：bgfdeca,a,b,c,d,f,g,e,1,2,3,4,5,6,7,a,b,c,d,f,g,e,1,2,3,4,5,6,7,层次遍历二叉树：按层次（1-k层)，每层从左到右依次访问二叉树中的每一
4、个结点。层次遍历序列：abcdefg,例6.1 已知二叉树先序遍历序列是:abcdefg;中序遍历序列是:cbdaefg;（1）画出该二叉树;（2）写出后序遍历序列.(cdbgfea)（1）（2）写出后序遍历序列：cdbgfea,a,b,c,d,e,f,g,1,2,3,4,5,6,7,二、树,1、树的定义 树（Tree)是n(n=0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个根结点；(2)除根结点外，其余结点可分为 m(m=0)个互不相交的子树。,3、树与二叉树的转换树转换成二叉树：,(左孩子-右兄弟),O,a,c,g,b,d,e,f,O,a,c,g,b,d,e,f,2、树的存储结
5、构二叉链,O,a,c,g,b,d,e,f,(左孩子-右兄弟),4、树的遍历,O,a,c,g,b,d,e,f,先序遍历树：（1）访问根结点（2）先序遍历每一个子树 先序遍历序列：o ab cdfe g,O,a,c,g,b,d,e,f,后序遍历树：（1）后序遍历每一个子树（2）访问根结点 后序遍历序列：ba fdec g 0,3、哈夫曼码：是一种前缀编码（即任一字符的编 码都不是另一编码的前缀）。左支用0表示，右 支用1表示。,1、二叉树的带权路径长度 WPL=wklk k=1其中，n:叶子结点个数，wk:第k个叶子的权，lk:第k个叶子到根的路径长度。,2、Huffman树的构造方法（1）将w1
6、,w2,.,wn看成n个二叉树；（2）选择 2 个根结点的值最小的二叉树，构造1个新的二叉树；.；直至剩1个树止。,n,三、Huffman树,(1)构造huffman树 以小值为左孩子(2)在哈夫曼树的所有左分支上编上号码“0”,右分支上编上号码“1”；(3)将根结点到每个叶子结 点的路径编码串起来,得到字符集的哈夫曼编码。,(4)=(25+36+50)*2+(8+10+14)*4+(2+5)*5=385,例6.8 设通信用8个字符abcdefgh,各字符使用的相对频率分别为 25,36,2,5,8,14,10,50,设计哈夫曼编码,求该树的带树路径长度。,a:25 00,b:36 01,c:2 10000,d:5 10001,e:8 1001,g:10 1010,f:14 1011,h:50 11,
