《CH6 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《CH6 树和二叉树.ppt（162页珍藏版）》请在金锄头文库上搜索。
1、第六章树和二叉树 数据结构 线性结构 线性表 栈 队列等 非线性结构 至少存在一个数据元素有不止一个直接前驱或后继 树 图等 6 1树的类型定义 6 2二叉树的类型定义 6 3二叉树的存储结构 6 4二叉树的遍历 6 5线索二叉树 6 6树和森林的表示方法 6 7树和森林的遍历 6 8哈夫曼树与哈夫曼编码 6 1树的类型定义 数据对象D D是具有相同特性的数据元素的集合 若D为空集 则称为空树 否则 1 在D中存在唯一的称为根的数据元素root 2 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一棵子集本身又是一棵符合本定义的树 称为根root的子树 数据关系
2、R 树的结构示意图 root T1 T2 T3 2 树的表示方法 1 树形结构表示法 直观表示法 2 凹入表示法树的凹入表示法主要用于树的屏幕和打印显示 3 嵌套集合表示法 4 广义表表示法 形式化表示方法 A B E J K L F C G D H M I 主要用于树的理论描述小结 树的表示方法的多样性 正说明了树结构在日常生活中及计算机程序设计中的重要性 一般来说 分等级的分类方案都可用层次结构来表示 也就是说 都可产生一个树结构 基本术语 结点 结点的度 树的度 叶子结点 分支结点 数据元素 若干指向子树的分支 结点拥有的分支的个数 树中所有结点的度的最大值 度为零的结点 度大于零的结点
3、 D H I J M 从根到结点的 路径 孩子结点 双亲结点兄弟结点 堂兄弟祖先结点 子孙结点 结点的层次 树的深度 由从根到该结点所经分支和结点构成 A B C D E F G H I J M K L 假设根结点的层次为1 第l层的结点的子树根结点的层次为l 1 树中叶子结点所在的最大层次 任何一棵非空树是一个二元组Tree root F 其中 root被称为根结点F被称为子树森林 森林 是m m 0 棵互不相交的树的集合 A root B C D E F G H I J M K L F 基本操作 查找类 插入类 删除类 Root T 求树的根结点 查找类 Value T cur e 求当前
4、结点的元素值 Parent T cur e 求当前结点的双亲结点 LeftChild T cur e 求当前结点的最左孩子 RightSibling T cur e 求当前结点的右兄弟 TreeEmpty T 判定树是否为空树 TreeDepth T 求树的深度 TraverseTree T Visit 遍历 InitTree T 初始化置空树 插入类 CreateTree T definition 按定义构造树 Assign T cur e value 给当前结点赋值 InsertChild T p i c 将以c为根的树插入为结点p的第i棵子树 ClearTree T 将树清空 删除类 D
5、estroyTree T 销毁树的结构 DeleteChild T p i 删除结点p的第i棵子树 对比树型结构和线性结构的结构特点 线性结构 树型结构 第一个数据元素 无前驱 根结点 无前驱 最后一个数据元素 无后继 多个叶子结点 无后继 其它数据元素 一个前驱 一个后继 其它数据元素 一个前驱 多个后继 6 2二叉树的类型定义 二叉树或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不交的二叉树组成 A B C D E F G H K 根结点 左子树 右子树 二叉树的五种基本形态 N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子树均不为空树
6、二叉树的特点和性质 每个结点最多只有两棵子树 即不存结点度大于2的结点 子树有左右之分 不能颠倒 注意 二叉树的定义也是一个递归定义 二叉树与树是两个不同的概念 它不是树的特殊情况 这是因为二叉树的子树有左右之分 而树的子树不必区分次序 二叉树与度为2的有序树也是不同的概念 对于二叉树的子树而言 要么是根的左子树 要么是根的右子树 即使只有一棵子树也要区分是左是右 度为2的有序树中 当一个结点有两棵子树时有左右之分 而只有一棵子树时就无左右之分 问题 1 只有两个结点的二叉树有几种不同的形态 2 只有3个结点的二叉树有几种不同形态 分别画出来 二叉树的主要基本操作 查找类 插入类 删除类 Ro
7、ot T Value T e Parent T e LeftChild T e RightChild T e LeftSibling T e RightSibling T e BiTreeEmpty T BiTreeDepth T PreOrderTraverse T Visit InOrderTraverse T Visit PostOrderTraverse T Visit LevelOrderTraverse T Visit InitBiTree ClearBiTree 二叉树的重要特性 二 二叉树性质性质1 在二叉树的第i层上至多有2i 1个结点 i 1 证明 用归纳法1 当i 1 即
8、第一层只有一个根结点 显然2i 1 20 1成立2 假设对所有的j 1 j i 上述性质成立 即第j层上至多有2j 1个结点 1 j i 3 要证明j i时 命题也成立 由归纳假设 第i 1层上至多有2i 2个结点 又由于二叉树每个结点的度最大为2 所以第i层上结点总数最多为第i 1层上最大结点数的2倍 即2 2i 2 2i 1 性质2 深度为k的二叉树至多有2k 1个结点 k 1 深度一定 二叉树的最大结点数也确定 证明 深度为K的二叉树的最大结点数是二叉树中每层上结点的最大数之和 即K 第i层上结点的最大数 i 1K 2i 1 1 2 22 2k 1 2k 1 等比级数求和 i 1 性质3
9、 对任何一棵二叉树T 若其终端结点数目为n0 度为2的结点数目为n2 则n0 n2 1 证明 设二叉树T的总结点数目为n 度为1的结点数目为n1 则n n0 n1 n2 1 又由于二叉树T中 除根结点以外 每个结点刚好有一个分支指入 设B为分支总数 则B n 1 2 而二叉树的这些分支是由度为1和度为2的结点产生 则B n1 2n2 3 综上三式 可知n0 n2 1成立 练习 1 有一棵三叉树 已知度为1 2 3的结点数分别n1 n2 n3 则该三叉树的叶结点数n0为多少 2 如果一棵树有n1个度数为1的结点 n2个度数为2的结点 nm个度数为m的结点 则终端结点数n0 3 若深为h的一棵树的
10、每个非终端结点的度均为k 则终端结点数n0 n0 2n3 n2 1 n0 m 1 nm n2 1 n0 kh 1 满二叉树 深度为k 且有2k 1个结点的二叉树 特点 1 每一层上结点数都达到最大 2 度为1的结点n1 0结点层序编号方法 从根结点起从上到下逐层 层内从左到右 对二叉树的结点进行连续编号 两类特殊的二叉树 完全二叉树 深度为k 结点数为n的二叉树 当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时 称为完全二叉树 两类特殊的二叉树 完全二叉树的特点 1 每个结点i的左子树的深度Lhi 其结点i的右子树的深度Rhi等于0或1 即叶结点只可能出现在层次最大或次最
11、大的两层上 2 完全二叉树结点数n满足2k 1 1 n 2k 1 3 满二叉树一定是完全二叉树 反之不成立 6 3二叉树概念及性质 LH2 0RH2 1 LH1 3RH1 1LH1 RH1 2 完全二叉树完全二叉树 LH2 RH2 0 1 1 6 3二叉树概念及性质 完全二叉树的任意结点的左右子树深度相差 0或者1 性质4 结点数为n的完全二叉树 其深度为 log2n 1证明 设深度为k 则由性质2和完全二叉树定义有 结点数n满足 2k 1 1 n 2k 1或写为2k 1 n 2k于是有 k 1 log2n k因为k 1和k均为整数显然有 log2n k 1 故k log2n 1 6 3二叉树
12、概念及性质 当i 1 结点i为根结点 无双亲结点 否则其双亲为 若2i n 结点i无左子女 否则其左子女为2i 若2i 1 n 结点i无右子女 否则其右子女为2i 1 性质5 对完全二叉树进行编号 按层次从左到右 编号可以反映二叉树结点之间的关系 如下图 证明 用归纳法证明 2 和 3 1 当i 1 如果2i 2 n 即结点2存在 由完全二叉树定义知 结点1的左孩子是2 即LCHILD i 2i如果2i 2 n 即不存在结点2 结点1也就无左孩子如果2i 1 3 n 即结点3存在 则结点i的右孩子是3 即2i 1如果2i 1 3 n 即不存在结点3 结点1也就无右孩子 2 假设对所有的结点j
13、1 j i 有 j的左孩子为2j 当2j nj无左孩子 当2j nj的右孩子2j 1 当2j 1 nj无右孩子 当2j 1 n3 要证明j i 1时i 1的左孩子为2 i 1 当2 i 1 ni 1无左孩子 当2 i 1 ni 1的右孩子为2 i 1 1 当2 i 1 1 ni 1无右孩子 当2 i 1 1 n成立 根据完全二叉树的结构和编号规则 在i 1的左孩子前面的两个结点是结点i的左 右孩子 由归纳假设有 结点i的左孩子为2i 右孩子为2i 1 i 1的左孩子应为2i 1 1 2 i 1 如果2 i 1 n 则编号为2 i 1 的结点不存在 即i 1无左孩子而i 1的右孩子应为2 i 1
14、 1如果2 i 1 1 n 则编号为2 i 1 1的结点不存在 即i 1无右孩子 2 和 3 得证 最后证明 1 i 1时 结点i是树的根 否则 i 1 结点i的双亲为结点 i 2 当i 1时 显然根结点无双亲 当i 1时 结点i可能是其双亲x的左孩子 也可能是右孩子 若是左孩子 由 3 知 x的左孩子应为2x 即2x i x i 2若是右孩子 由 3 知 x的右孩子应为2x 1 即2x 1 i x i 1 2故i的双亲为 i 2 证毕 6 3二叉树的存储结构 二 二叉树的链式存储表示 一 二叉树的顺序存储表示 6 3 二叉树的存储结构 一 二叉树的顺序存储结构特点 用一组连续的存储单元存储二
15、叉树的数据元素 必须把二叉树的所有结点安排成为一个恰当的序列 结点在这个序列中的相互位置能反映出结点之间的逻辑关系 编号的方法二叉树的顺序存储表示 defineMAX TREE SIZE100typedefElemTypeSqBiTree MAX TREE SIZE 1 二叉树的顺序存储示例一 二叉树的顺序存储示例二 练习 对如下一棵二叉树采用顺序存储结构 需要添加几个空结点 小结 对于完全二叉树来说二叉树中的结点的编号完全可以反映出该二叉树中结点之间的逻辑关系 可将此类二叉树中结点的编号与数组下标建立一一对应关系 所以采用顺序存储结构较好 对于一般的二叉树需要添加 空 结点 使之成为一棵完全
16、二叉树 此时仍可用顺序存储结构表示这棵二叉树 但这样可能造成空间浪费 最坏的情况是 深度为k且只有k个结点的单支树 需要长为2k 1的数组空间 例如 深度为k 且只有k个结点的右单枝树 每个非叶结点只有右孩子 需2k 1个单元 即有2k 1 k个单元被浪费 1 k 二 二叉树的链式存储表示 1 二叉链表 2 三叉链表 3 双亲链表 4 线索链表 typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree lchilddatarchild 结点结构 C语言的类型描述如下 1 二叉链表 如下面的树 A D E B C F root lchilddatarchild 结点结构 6 3二叉树 性质6 含有n个结点的二叉链表中 有n 1个空链域 证明一 空链域数 2n0 n1 n0 n1 n0 1 又有n0 n2 1所以 1 式 n0 n1 n2 1又因为n n0 n1 n2故空链域数 n 1证明二 有n 1个结点有链引入 所以非空链域 n 1有n个结点共有2n个链域 故 空链域
