第06章_二叉树遍历.ppt

第六章 树、二叉树 6.1 树的定义和基本术语 树的定义 6.2 二叉树 二叉树的定义 度不大于2的树称为二叉树。 相关术语 左子结点、右子结点 二叉树的性质 二叉树的性质 例:请分别写出二叉树的先序、中序和后序序列 6.3 遍历二叉树和线索二叉树 二叉树的遍历 遍历序与二叉树的对应 前序遍历序+中序遍历序唯一确定二叉树 后序遍历序+中序遍历序唯一确定二叉树 线索二叉树 定义 线索二叉树 中序线索二叉树的遍历 树的存储结构 双亲表示法 森林与二叉树的转换 树=根+子树森林 森林与二叉树的转换 二叉树与树的转换 森林与二叉树的转换 赫夫曼树（最优二叉树） 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度：路径上的分支数称为这两点之间的路径长度。 树的路径长度：树的路径长度是从树的根到每一结点的路径长度之和。 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点带权路径长度之和，通常记作 赫夫曼树（最优二叉树） 赫夫曼算法 赫夫曼编码 定长编码与变长编码 若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。 可以利用二叉树来设计二进制的前缀编码。 赫夫曼编码 编码构造 信息编码 信息解码 树和森林的遍历 森林的遍历 中序遍历森林 (1)中序遍历森林中第一棵树的根结点的子树森林 (2)访问第一棵树的根结点 (3)中序遍历除去第一棵树之后剩余的树构成的森林 6.4 树和森林 A B D G J E H C F I 中序序列：B C D A F E H J I G 森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。 当以二叉链表的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历算法实现。 6.6 赫夫曼树及其应用 赫夫曼树：假设有n个权值{w1,w2…wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树。 6.6 赫夫曼树及其应用 (a)WPL=7*2+5*2+2*2+2*4=36 (b)WPL=4*2+7*3+5*3+2*1=46 (c)WPL=7*1+5*2+2*3+4*3=35 6.6 赫夫曼树及其应用 (1)根据给定的n个权值{ W1，W2，…，W n}构成n棵二叉树的集合F={T1，T2，…，T n }，其中每一棵二叉树T i中只有一个带权为Wi的根结点，其左右子树均空； (2)在F中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树，且置新二叉树根结点的权值为两棵子树根结点的权值之和； (3)从F中删去这两棵树，同时把新二叉树加入F中； (4)重复(2)和（3），直到F中只有一棵树为止，此树便是哈夫曼树。 6.6 赫夫曼树及其应用 A B C D 0 0 0 1 1 1 编码：A(0) B(10) C(110) D(111) 第 六 章 树 和 二 叉 树 * 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 树(Tree)是n(n0)个结点的有限集T，非空树满足以下条件: 有且仅有一个特定的称为根的结点; (2) 除根结点外的其余结点可分为m(m0)个互不相交的有限集T1,T2...Tm,其中,每一个集合本身 又是一棵树, 并且称为根的子树 6.1 树的定义和基本术语 树的定义 (b)是只有一个根结点的树; (a)是有13个结点的树,其中A是根,其余结点分成三个互不相交的子树； 6.1 树的定义和基本术语 树的基本术语 树的结点：包含一个数据元素及若干个指向其子树的分支 结点的度：结点拥有的子树数 树的度：树内各结点的度的最大值 叶子（终端结点）：度为零的结点 非终端结点（分支结点）：度不为零的结点 孩子、双亲及兄弟结点： 结点的祖先、子孙和堂兄弟： 结点的层次和树的深度： 有序树和无序树： 森林：是m棵互不相交的树的集合 (a) 空二叉树 A (b) 根和空的左右子树 A B (c) 根和左子树 A B (d) 根和右子树 A C B (e) 根和左右子树 性质1：在二叉树的第i层上至多有2i-1个结点(i=1) 性质2：深度为k的二叉树至多有2k-1个结点 性质3：对于任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1 满二叉树：一棵深度为k且有2k-1个结点的二叉树 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时 6.2 二叉树 6.2 二叉树 性质4：具有n个