数据结构之叉树.pptVIP

数据结构复习(树与二叉树) 一、二叉树 或空，或由根和由互不相交的 　　　　左子树、右子树构成。 1、二叉链 第六章 树和二叉树 a b c d f g e a b c e d f g 性质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=i=n), 有： (1)如果i=1，则结点i是二叉 树的根结点；如果 i1, 则其双亲结点是[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）先序遍历右子树 先序遍历序列： abcdfge 1 2 3 4 5 6 7 a b c d f g e 中序遍历二叉树： （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 中序遍历序列： bafgdce a b c d f g e 1 2 3 4 5 6 7 后序遍历二叉树： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 后序遍历序列： bgfdeca a b c d f g e 1 2 3 4 5 6 7 a b c d f g e 1 2 3 4 5 6 7 层次遍历二叉树： 按层次（1-k层)，每层从左到右依次访问二叉树中的每一个结点。 层次遍历序列： abcdefg 例6.1 已知二叉树先序遍历序列是:abcdefg; 中序遍历序列是:cbdaefg; （1）画出该二叉树; （2）写出后序遍历序列.(cdbgfea) （1） （2）写出后序遍历序列：cdbgfea a b c d e f g 1 2 3 4 5 6 7 二、树 1、 树的定义 树（Tree)是n(n=0)个结点的有限集。 在任意一棵非空树中： (1)有且仅有一个根结点； (2)除根结点外，其余结点可分为 m(m=0)个互不相交的子树。 3、 树与二叉树的转换 树转换成二叉树： (左孩子-右兄弟) O a c g b d e f O a c g b d e f 2、 树的存储结构——二叉链 O a c g b d e f (左孩子-右兄弟) 4、 树的遍历 O a c g b d e f 先序遍历树： （1）访问根结点 （2）先序遍历每一个子树  先序遍历序列： o ab cdfe g O a c g b d e f 后序遍历树： （1）后序遍历每一个子树 （2）访问根结点  后序遍历序列： ba fdec g 0 3、哈夫曼码：是一种前缀编码（即任一字符的编 码都不是另一编码的前缀）。左支用0表示，右 支用1表示。 1、 二叉树的带权路径长度 WPL = ? wklk