图论讨论课(二叉树的理论)

1、 二叉树问题 小组成员：刘化庆 胥栋宽 唐珊珊内容概要 基本概念基本概念 二叉树的定义与典型性质二叉树的定义与典型性质 二叉树的存储二叉树的存储 二叉树的遍历二叉树的遍历 线索二叉树线索二叉树 Huffman树树基本概念 树根 树叶 孩子 双亲 兄弟 堂兄弟 祖先 子孙 层数 树高 左子树vs右子树 有序树vs无序树 t叉树 树的表示方法： 直观法 集合法 文氏图 目录法二叉树的定义与典型性质定义定义典型性质：典型性质：(a)二叉树的第 i 层上至多有 2i 1个结点(b)(b)深度为深度为 k k 的二叉树至多有的二叉树至多有 2 2 k k-1-1个结点个结点(k(k 1)1)(c)对任何

2、一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0n21（叶子和分支点的关系)(d)设T是高为h的 v 阶二叉树，则(e)设T是高为h的 v 阶二叉树，则满二叉树满二叉树完全二叉树完全二叉树二叉树的存储顺序存储结构：顺序存储结构：二叉链式存储结构：二叉链式存储结构：三叉链式存储结构：三叉链式存储结构：二叉树的遍历 先序：树根、左子树、右子树 中序：左子树、树根、右子树 后序：左子树、右子树、树根 例： 先序：- + a * b c d / e f 中序：a + b * c d e / f 后序：a b c d - * + e f / -二叉树的遍历 void InOrde

3、rTraverse(BiTree T, Status(*Visit) /采用二叉链表存贮二叉树,visit()是访问结点的函数 /中序遍历二叉树 /对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回InOrderTraverse(T-lchild, Visit); /遍历左子树Visit(T-data)； /访问根结点InOrderTraverse(T-rchild, Visit); /遍历右子树 / InOrderTraverse 线索二叉树二叉树的遍历存在如下问题： (a)遍历算法要复杂的多，费时的多； (b)为检索或查找二叉树中某结点在某种遍历下的后继，必须从

4、根开始遍历，直到找到该结点及后继 如果能将二叉树线性化，就可以减化遍历算法，如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度提高遍历速度线索二叉树 lchildLTagdataRTagrchild 0 0 lchild域指示结点的左孩子域指示结点的左孩子 ，表示，表示为左孩子指针为左孩子指针 LTagLTag= 1 = 1 域指示结点的前驱，域指示结点的前驱， 表示表示为线索为线索 0 域指示结点的右孩子，表示域指示结点的右孩子，表示为右孩子指针为右孩子指针 RTagRTag= 1 = 1 域指示结点的后驱，域指示结点的后驱， 表示表示为线索为线索中序线索二叉树举例中序线索二叉树举例AB

5、CDE A B D C ET中序序列：BCAED中序线索二叉树0000111111遍历Huffman树又称最优二叉树，它是n个带权叶子结点构成的所 有二叉树中，带权路径长度WPL最小的二叉树WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 =35 222444555777 问题： 已知已知t个权值，个权值，w1、w2、wt，如何构造，如何构造Huffman树？树？定理例例9已知权值 W= 5, 6, 2, 9, 7 56275276976713952767139527952716671329 Huffman编码编码 问题描述问题描述: 电报传送 A(00) B(01) C(10) D(11) “ABACCDA” = “00010010101100” (a)尽可能短 A(0) B(00) C(1) D(01) (b)单一解释 “ABACCDA” = “000011010”（多种解释）前缀编码前缀编码 互不为前缀互不为前缀 例： 是：1,00,01001 不是：1,00,00101 定理定理 由一棵树给定的由一棵树给定的2叉树可以产生一个二元前缀码叉树可以产生一个二元前缀码例 在