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

1、数据构造复习(树与二叉树)一、二叉树一、二叉树或空，或由根和由互不相交的或空，或由根和由互不相交的左子树、右子树构成。左子树、右子树构成。1、二叉链、二叉链abcdfgeabcedfg性质性质1： 在二叉树的第在二叉树的第i (i0)层上至多有层上至多有2i-1个结点。个结点。性质性质2： 深度为深度为k的二叉树中至多有的二叉树中至多有2k-1个结点个结点(k0)。性质性质3： 对任何一棵二叉树对任何一棵二叉树T，假设其终端结点数为，假设其终端结点数为n0,度为度为2的结点数为的结点数为n2，那么，那么 n0=n2+1。性质性质4： 有有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为

2、+1。性质性质5： 假设对一棵有假设对一棵有n个结点的完全二叉树按层序从个结点的完全二叉树按层序从1开场编号，那么对任一结点开场编号，那么对任一结点(i=i1, 那么其双亲结点是那么其双亲结点是i/2。(2)假设假设2i=n, 那么结点那么结点i的左孩的左孩 子是结点子是结点2i ；否那么结点；否那么结点i无无 左孩子。左孩子。(3)假设假设2i+1=0)个结点的有限集。个结点的有限集。在恣意一棵非空树中：在恣意一棵非空树中：(1)有且仅有一个根结点；有且仅有一个根结点；(2)除根结点外，其他结点可分为除根结点外，其他结点可分为 m(m=0)个互不相交的子树。个互不相交的子树。 (左孩子-右兄

3、弟)OacgbdefOacgbdefOacgbdefOacgbdef 先序遍历树： 1访问根结点 2先序遍历每一个子树 先序遍历序列： o ab cdfe gOacgbdef 后序遍历树： 1后序遍历每一个子树 2访问根结点 后序遍历序列： ba fdec g 03、哈夫曼码：是一种前缀编码即任一字符的编、哈夫曼码：是一种前缀编码即任一字符的编 码都不是另一编码的前缀。左支用码都不是另一编码的前缀。左支用0表示，右表示，右 支用支用1表示。表示。1 1、 二叉树的带权途径长度二叉树的带权途径长度 WPL = WPL = wklk wklk k=1k=1其中，其中，n:n:叶子结点个数，叶子结点

4、个数， wk : wk :第第k k个叶子的权，个叶子的权， lk : lk :第第k k个叶子到根的途径长度。个叶子到根的途径长度。 2 2、HuffmanHuffman树的构造方法树的构造方法 1 1将将w1,w2,.,wnw1,w2,.,wn看成看成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, 设设计哈夫曼编码计哈夫曼编码, 求该树的带树途径长度。