数据结构复习树与二叉树课件.ppt

数据结构复习(树与二叉树)一、二叉树一、二叉树或空，或由根和由互不相交的或空，或由根和由互不相交的　　　　左子树、右子树构成　　　　左子树、右子树构成1、二叉链、二叉链 第六章第六章 树和二叉树树和二叉树abcdfgeabcedfg性质性质1：： 在二叉树的第在二叉树的第i (i>0)层上至多有层上至多有2i-1个结点性质性质2：： 深度为深度为k的二叉树中至多有的二叉树中至多有2k-1个结点个结点(k>0)性质性质3：： 对任何一棵二叉树对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0,度为度为2的结点数为的结点数为n2，则，则 n0=n2+1性质性质4：： 有有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 +12、二叉树的性质、二叉树的性质性质性质5：： 如果对一棵有如果对一棵有n个结点的完全二叉树按层序从个结点的完全二叉树按层序从1开开始编号，则对任一结点始编号，则对任一结点(i<=i<=n), 有：有：(1)如果如果i=1，则结点，则结点i是二叉是二叉 树的根结点；如树的根结点；如果果 i>1, 则其双亲结点是则其双亲结点是[i/2]。

2)如果如果2i<=n, 则结点则结点i的的左孩左孩 子是结点子是结点2i ；；否则结点否则结点i无无 左孩子左孩子3)如果如果2i+1<=n, 则结点则结点i的右的右 孩子是结点孩子是结点2i+1；； 否则结否则结 点点i无右孩子无右孩子 例６例６.１１32个结点的完全二叉树，从根开始，按层次从个结点的完全二叉树，从根开始，按层次从左到右用左到右用1-32编号请回答：编号请回答：（（1）它共有多少层？）它共有多少层？（（2）各层最左边的结点的编号是多少？）各层最左边的结点的编号是多少？（（3）编号为）编号为6的结点的左孩子的编号是多少？的结点的左孩子的编号是多少？ 它的右孩子呢？它的右孩子呢？（（4）编号为）编号为16的结点的左孩子的编号是多少？的结点的左孩子的编号是多少？ 它的右孩子呢？它的右孩子呢？ （（5）对于编号为）对于编号为8的结点，它的父结点的编号是多少？的结点，它的父结点的编号是多少？ 编号为编号为13的结点呢？编号为的结点呢？编号为1的结点呢？的结点呢？ 二叉树的二叉树的遍历遍历：按某条搜索路径访问二叉树中：按某条搜索路径访问二叉树中每一个结点，使得每个结点被访问一次且仅被访问一每一个结点，使得每个结点被访问一次且仅被访问一次。

次 遍历方法遍历方法有有4种：先序遍历，中序遍历，后序遍种：先序遍历，中序遍历，后序遍历，层次历，层次遍历遍历3、二叉树的遍历、二叉树的遍历先序遍历二叉树：先序遍历二叉树：（（1）访问根结点）访问根结点 （（2）先序遍历左子树）先序遍历左子树（（3）先序遍历右子树）先序遍历右子树先序遍历序列：先序遍历序列： abcdfge1 12 23 34 45 56 67 7abcdfge中序遍历二叉树：中序遍历二叉树：（（1）中序遍历左子树）中序遍历左子树 （（2）访问根结点）访问根结点（（3）中序遍历右子树）中序遍历右子树中序遍历序列：中序遍历序列： bafgdceabcdfge1 12 23 34 45 56 67 7后序遍历二叉树：后序遍历二叉树：（（1）后序遍历左子树）后序遍历左子树 （（2）后序遍历右子树）后序遍历右子树（（3）访问根结点）访问根结点后序遍历序列：后序遍历序列： bgfdecaabcdfge1 12 23 34 45 56 67 7abcdfge1 12 23 34 45 56 67 7层次遍历二叉树：层次遍历二叉树： 按层次（按层次（1-k层层)，每，每层从左到右依次访问二叉层从左到右依次访问二叉树中的每一个结点。

树中的每一个结点 层次遍历序列：层次遍历序列： abcdefg 例例6.1 已知二叉树先序遍历序列是已知二叉树先序遍历序列是:abcdefg; 中序遍历序列是中序遍历序列是:cbdaefg; （（1）画出该二叉树）画出该二叉树; （（2）写出后序遍历序列）写出后序遍历序列.(cdbgfea) （（1））（（2）写出后序遍历序列：）写出后序遍历序列：cdbgfeaabcdefg1 12 23 34 45 56 67 7二、树二、树 1、、 树的定义树的定义 树（树（Tree)是是n(n>=0)个结点的有限集个结点的有限集在任意一棵非空树中：在任意一棵非空树中：(1)有且仅有一个根结点；有且仅有一个根结点；(2)除根结点外，其余结点可分为除根结点外，其余结点可分为 m(m>=0)个互不相交的子树个互不相交的子树3、、 树与二叉树的转换树与二叉树的转换树转换成二叉树：树转换成二叉树： (左孩子-右兄弟)OacgbdefOacgbdef2、、 树的存储结构树的存储结构——二叉链二叉链Oacgbdef( (左孩子左孩子左孩子左孩子- -右兄弟右兄弟右兄弟右兄弟) )4、、 树的遍历树的遍历Oacgbdef 先序遍历树：先序遍历树： （（1）访问根结点）访问根结点 （（2）先序遍历每一个子树）先序遍历每一个子树 先序遍历序列：先序遍历序列： o ab cdfe gOacgbdef 后序遍历树：后序遍历树： （（1）后序遍历每一个子树）后序遍历每一个子树 （（2）访问根结点）访问根结点 后序遍历序列：后序遍历序列： ba fdec g 03、哈夫曼码：是一种前缀编码（即任一字符的编、哈夫曼码：是一种前缀编码（即任一字符的编 码都不是另一编码的前缀）。

左支用码都不是另一编码的前缀）左支用0表示，右表示，右 支用支用1表示1 1、、 二叉树的二叉树的带权路径长度带权路径长度 WPL =   wklk k=1其中，其中，n:n:叶子结点个数，叶子结点个数， w wk k : :第第k k个叶个叶子子的权，的权， l lk k : :第第k k个叶个叶子到根的路径长度子到根的路径长度 2 2、、HuffmanHuffman树的构造方法树的构造方法 （（1 1）将）将{w{w1 1,w,w2 2, ,…….,.,w wn n} }看成看成n n个二叉树；个二叉树； （（2 2）选择）选择 2 2 个根结点的值最小的二叉树，个根结点的值最小的二叉树，构造构造1 1个新的二叉树；个新的二叉树；……. .；直至剩；直至剩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 00b:36 01c:2 10000d:5 10001e:8 1001g:10 1010f:14 1011h:50 11。