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

数据结构复习树与二叉树 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望一、二叉树一、二叉树或空，或由根和由互不相交的或空，或由根和由互不相交的左子树、右子树构成。左子树、右子树构成。1、二叉链、二叉链 第六章第六章 树和二叉树树和二叉树abcdfgeabcedfg性质性质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开开始编号，则对任一结点始编号，则对任一结点(i=i1,则其双亲结点是则其双亲结点是i/2。(2)如果如果2i=n,则结点则结点i的的左孩左孩 子是结点子是结点2i；否则结点否则结点i无无 左孩子左孩子。(3)如果如果2i+1=0)个结点的有限集。个结点的有限集。在任意一棵非空树中：在任意一棵非空树中：(1)有且仅有一个根结点；有且仅有一个根结点；(2)除根结点外，其余结点可分为除根结点外，其余结点可分为 m(m=0)个互不相交的子树。个互不相交的子树。3、树与二叉树的转换树与二叉树的转换树转换成二叉树：树转换成二叉树：(左孩子-右兄弟)OacgbdefOacgbdef2、树的存储结构树的存储结构二叉链二叉链Oacgbdef(左孩子左孩子左孩子左孩子-右兄弟右兄弟右兄弟右兄弟)4、树的遍历树的遍历Oacgbdef 先序遍历树：先序遍历树：（1）访问根结点）访问根结点（2）先序遍历每一个子树）先序遍历每一个子树 先序遍历序列：先序遍历序列：o ab cdfe gOacgbdef 后序遍历树：后序遍历树：（1）后序遍历每一个子树）后序遍历每一个子树（2）访问根结点）访问根结点 后序遍历序列：后序遍历序列：ba fdec g 03、哈夫曼码：是一种前缀编码（即任一字符的编、哈夫曼码：是一种前缀编码（即任一字符的编 码都不是另一编码的前缀）。左支用码都不是另一编码的前缀）。左支用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）将）将ww1 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