Chapter06 树和二叉树.ppt

数据结构 C语言版 姓名 薛均晓办公室 302 63887286 Email xuejx 2 127 数据结构 C语言版 第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章内部排序 3 127 第六章树和二叉树 内容 6 1树的定义和基本术语6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 6赫夫曼树及其应用 4 127 第六章树和二叉树 内容 6 1树的定义和基本术语6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 6赫夫曼树及其应用 5 127 概述 线性结构 每个元素都只有一个前驱和后继结点 现实许多事物的关系没有这么简单 如社会机构组成 城市交通通讯等 事物的联系是非线性的 数据元素具有两个以上的前驱或后继结点 树型结构是一类重要的非线性数据结构 是以分支关系定义的层次结构 6 127 概述 例 单位组织机构 7 127 概述 例 单位组织机构 8 127 概述 例 程序结构 10 127 家谱 12 127 定义 树 tree 是由n n 0 个结点组成的有限集合 n 0的树称为空树 n 0的树T是n n 0 个结点的有限集T 其中 有且仅有一个特定的结点 称为树的根 root 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 称为根的子树 subtree 树的定义 13 127 树的定义 特点 根结点没有前驱结点 只有后继结点除根结点外 其余的每一个结点都有且仅有一个直接前驱结点 有零个或多个直接后继结点树中各子树是互不相交的集合 14 127 根 子树 15 127 树的定义 A B F D E G I C H K A 树 非树 思考 16 127 树可以用二元组描述为 Group D R 有限个数据元素的集合 这些数据元素间关系的集合 D A B C D E F G H I J R 树的描述 17 127 1 树形图法2 嵌套集合法3 广义表形式4 凹入表示法 A B C E F D G 树的表示方法 18 127 练习 分别使用树形图和嵌套集合表示下列树 A B E F I J C D G H 19 127 C E G H D B I J F A 20 127 树的基本术语 父母 孩子与兄弟结点度结点层次 树的高度边 路径无序树 有序树森林 21 127 1 父母 孩子与兄弟结点 结点的直接前驱结点称为父母 parents 结点 结点的直接后继结点称为孩子 child 结点 拥有同一个父母结点的多个结点之间称为兄弟 sibling 结点 结点的祖先 ancestor 是指从根结点到其父母结点所经过的所有结点 结点的后代 descendant 是指该结点的所有孩子结点 以及孩子的孩子等 祖先与后代的关系则是对父子关系的延伸 其定义了树中结点的纵向次序 22 127 2 度 结点的度 degree 是指结点所拥有子树的棵数 度为零的结点称为叶子 leaf 或者终端结点度不为零的结点称为分支结点或者非终端结点 非叶结点 树的度是指树中各结点度的最大值 23 127 3 结点层次 树的高度 结点的层次 level 属性反映结点处于树中的层次位置 约定根结点的层次为1 其余结点的层次是其父母结点的层次加1 树的高度 height 或深度 depth 是树中结点的最大层次数 24 127 4 边 路径 设树中X结点是Y结点的父母结点 有序对 X Y 称为连接这两个结点的分支 也称为边 edge 设 X0 X1 Xk 1 是由树中结点组成的一个序列 且 Xi Xi 1 0 i k 1 都是树中的边 则该序列称为X0到Xk 1的一条路径 path 路径长度 pathlength 为路径上的边数 25 127 5 无序树 有序树 若把树中每个结点的各子树看成从左到右有次序的 即不能互换 则称该树为有序树 OrderedTree 否则称为无序树 UnorderedTree 如果规定k1和k2是兄弟 且k1在k2的左边 则k1的任一子孙都在k2的任一子孙的左边 则定义了树中结点的横向次序 A B C D E F G H J I A B C A C B 26 127 6 森林 森林 Forest 是m m 0 棵互不相交树的集合 给森林加上一个根结点就变成一棵树 将树的根结点删除就变成森林 B C D E F G H J I 树 森林 27 127 结点A的度 3结点B的度 2结点M的度 0 叶子 K L F G M I J 结点A的孩子 B C D结点B的孩子 E F 结点I的双亲 D结点L的双亲 E 结点B C D为兄弟结点K L为兄弟 树的度 3 结点A的层次 1结点M的层次 4 树的深度 4 结点F G为堂兄弟结点A是结点F G的祖先 28 127 树的抽象数据类型定义 ADTTree 数据对象D D是具有相同特性的数据元素的集合 数据关系R 若D为空集 则称为空树 否则 1 在D中存在唯一的称为根的数据元素root 2 3 基本操作P ADTTree Page118 29 127 树的基本操作 查找类插入类删除类 30 127 树的基本操作 查找类 Root T 求树的根结点 Value T cur e 求当前结点的元素值 Parent T cur e 求当前结点的双亲结点 LeftChild T cur e 求当前结点的最左孩子 TreeEmpty T 判定树是否为空树 TreeDepth T 求树的深度 TraverseTree T Visit 遍历 RightSibling T cur e 求当前结点的右兄弟 31 127 树的基本操作 插入类 InitTree T 初始化置空树 CreateTree T definition 按定义构造树 Assign T cur e value 给当前结点赋值 InsertChild T p i c 将以c为根的树插入为结点p的第i棵子树 32 127 树的基本操作 删除类 ClearTree T 将树清空 DestroyTree T 销毁树的结构 DeleteChild T p i 删除结点p的第i棵子树 33 127 树和线性结构对比 线性结构 树型结构 第一个数据元素 无前驱 根结点 无前驱 最后一个数据元素 无后继 多个叶子结点 无后继 其它数据元素 一个前驱 一个后继 其它数据元素 一个前驱 多个后继 34 127 第六章树和二叉树 内容 6 1树的定义和基本术语6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 6赫夫曼树及其应用 35 127 二叉树 许多实际问题抽象出来的数据结构往往是二叉树的形式 36 127 一个简单的二叉树模型 股票的现价为 20三个月之后股票的价格或为 22或为 18 StockPrice 22 StockPrice 18 Stockprice 20 37 127 二叉树的定义与性质 二叉树 BinaryTree 是有限个元素的集合 或者为空或者是由一个根结点加上两棵互不相交的二叉树组成 分别称为左子树和右子树 38 127 二叉树是有序的 二叉树的子树有左右之分 二叉树有5种基本形态 二叉树的定义与性质 39 127 思考 3个结点的无序树和二叉树的各有几种基本形态 分别将其画出来 40 127 41 127 思考 二叉树是度为2的有序树吗 一棵度为2的有序树与二叉树有何区别 树 有序树 二叉树的区别 42 127 答 不对 二叉树是有序树不错 但也可能是度为1的单枝树 或度为0的空树 答 一棵度为二的有序树与二叉树的区别在于 有序树的结点次序是相对于另一结点而言的 如果有序树中的子树只有一个孩子时 这个孩子结点就无须区分其左右次序 而二叉树无论其孩子数是否为2 均需确定其左右次序 也就是说二叉树的结点次序不是相对于另一结点而言而是确定的 答 树的子树没有左右之分 二叉树 有序树分左右顺序 在只有一棵子树的情况下 二叉树有左右之分 有序树无左右之分 43 127 ADTBinaryTree 数据对象D 具有相同特性的数据元素的集合 数据关系R 若D 则R 称BinaryTree为空二叉树 若D 则R H H是如下二元关系 1 在D中存在唯一的根root 它在关系H下无前驱 2 若D root 则存在D root Dl Dr 且Dl Dr 3 若Dl 则Dl中存在唯一的元素xl H 且存在Dl上的关系H1为H的子集 Dr同样 H Hl Hr 4 Dl Hl 是一棵符合本定义的二叉树 称为根的左子树 Dr Hr 是一棵符合本定义的二叉树 称为根的右子树 运算 ADTBinaryTree 二叉树的抽象数据类型 44 127 二叉树的性质 45 127 性质1二叉树的第i层上至多有2i 1个结点 i 1 利用归纳法容易证得此性质 1 i 1时 只有一个根结点 显然 2i 1 20 1 2 假定对所有的j 1 j i 命题成立 即第j层上至多有2j 1个结点 那么 现在来证明j i时命题也成立 3 由归纳假设 第i 1层上至多有2i 2个结点 由于二叉树的每个结点的度至多为2 故在第i层上的最大结点数为第i 1层上的最大结点数的2倍 即2 2i 2 2i 1 46 127 性质2深度为k的二叉树至多有2k 1个结点 k 1 由性质1 二叉树的第i层上至多有2i 1个结点 i 1 则深度为k的二叉树的结点总数为 47 127 性质3对任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1 设n1为二叉树T中度为1的结点数 因为二叉树中所有结点的度均小于或等于2所以其结点总数为n n0 n1 n2 6 1 再看二叉树中的分支数 除了根结点外 其余结点都有一个分支进入 设B为分支总数 则n B 1 由于这些分支是由度为1或2的结点射出的 所以又有B n1 2n2 n n1 2n2 1 6 2 于是得由式 6 1 和 6 2 得n0 n2 1 48 127 证明2 因为二叉树中所有结点的度均不大于2 所以结点总数 记为n 应等于0度结点数 1度结点和2度结点数之和 n n0 n1 n2 1 另一方面 1度结点有一个孩子 2度结点有两个孩子 故二叉树中孩子结点总数是 n1 2n2树中只有根结点不是任何结点的孩子 故二叉树中的结点总数又可表示为 n n1 2n2 1 2 由式子1和式子2得到 n0 n2 1 A B C E F 49 127 Review 使用与教材上不同的方法证明二叉树的性质3 50 127 两种特殊的二叉树 满二叉树 所有的分支结点都有左右子树 所有的叶子结点都在同一层上 A B C D E F G A B C D E F G 满二叉树 非满二叉树 51 127 A B C D E F G 非满二叉树 非满二叉树 A B C D F G 52 127 满二叉树的特点 1 每一层上的结点数都达到最大值 即对给定的高度 它是具有最多结点数的二叉树 2 满二叉树中不存在度数为1的结点 每个分支结点均有两棵高度相同的子树 且树叶都在最下一层上 53 127 两种特殊的二叉树 完全二叉树 叶子结点只出现在最下层和次下层 除了最下一层和次下一层其余结点的度均为2 并且最下层的叶子结点集中在树的左边 A B C D E F G 完全二叉树 A B C D E F G 非完全二叉树 54 127 完全二叉树的特点 1 满二叉树是完全二叉树 完全二叉树不一定是满二叉树 2 在满二叉树的最下一层上 从最右边开始连续删去若干结点后得到的二叉树就是一棵完全二叉树 3 在完全二叉树中 若某个结点没有左孩子 则它一定没有右孩子 即该结点必是叶结点 55 127 性质4具有n个结点的完全二叉树的高度为 证明 设所求完全二叉树的高度为k 由完全二叉树定义可得 高度为k的完全二叉树的前k 1层是高度为k 1的满二叉树 一共有2k 1 1个结点 由于完全二叉树深度为k 故第k层上还有若干个结点 因此该完全二叉树的结点个数 n 2k 1 1 另一方面 由性质2可得 n 2k 1 即 2k 1 1 n 2k 1由此可推出 2k 1 n 2k 取对数后有 k 1 log2n k又因k 1和k是相邻的两个整数 故有k 1 由此即得 k 1 56 127 给二叉树结点编号 在一棵n个结点的完全二叉树中 从树根起 自上层到下层 每层从左至右 给所有结点编号 能得到一个反映整个二叉树结构的线性序列 完全二叉树 57 127 性质5如果对一棵有n个结点的完全二叉树 其深度为 log2n 1 的结点按层序编号 从第1层到第 log2n 1层 每层从左到右 则对任一结点i 1 i n 有 1 如果i 1 则结点i是二叉树的根 无双亲 如果i 1 则其双亲PARENT i 是结点 i 2 2 如果2i n 则结点i无左孩子 结点i为叶子结点 否则其左孩子LCHILD i 是结点2i 3 如果2i 1 n 则结点i无右孩子 否则其右孩子RCHILD i 是结点2i 1 a 结点i和i 1在同一层上 b 结点i和i 1不在同一层上完全二义树中结点i和i 1的左 右孩子 58 127 只要先证明 2 和 3 便可以从 2 和 3 导出 1 对于i 1 由完全二叉树的定义 其左孩子是结点2 若2 n 即不存在结点2 此时结点i无左孩子 结点i的右孩子也只能是结点3 若结点3不存在 即3 n 此时结点i无右孩子 对于i 1可分两种情况讨论 1 设第j 1 j log2n 层的第一个结点的编号为i 由二叉树的定义和性质2可知i 2j 1 则其左孩子必为第j 1层的第一个结点 其编号为2j 2 2j 1 2i 若2i n 则无左孩子 其右孩子必为第j 1层的第二个结点 其编号为2i 1 若2i 1 n 则无右孩子 2 假设第j 1 j log2n 层上某个结点的编号为i 2j 1 i 2j 1 且2i 1 n 则其左孩子为2i 右孩子为2i 1 则编号为i 1的结点是编号为i的结点的右兄弟或者堂兄弟 若它有左孩子 则编号必为2i 2 2 i 1 若它有右孩子 则其编号必为2i 3 2 i 1 1 证明 59 127 一 顺序存储结构二叉树的顺序存储 是采用一组连续的存储单元来存放二叉树中的结点 但是 由于二叉树是非线性结构 所以结点之间的逻辑关系难以从存储的先后确定 不过 由二叉树的性质5可知 对于完全二叉树 如果按照从上 根结点 到下 叶结点 和从左到右的顺序 对二叉树中的所有结点从0到n 1编号 这样存放到一维数组中 只要通过数组元素的下标关系 就可以确定二叉树中结点之间的逻辑关系 二叉树的存储结构 60 127 一 顺序存储结构 defineMAX TREE SIZE100 二叉树的最大结点数typedefDataTypeSqBiTree MAX TREE SIZE 0号单元存储根结点SqBiTreebt 二叉树的存储结构 61 127 A B C D E F G 完全二叉树 62 127 对于一般的二叉树 如果仍采用顺序表示 首先要对它进行扩充 增加一些并不存在的空结点 使之成为一棵完全二叉树 然后再用一维数组顺序存储 63 127 完全二叉树的顺序存储可利用数组下标确定结点之间的逻辑关系 一般二叉树则不能 可增加空结点来实现 D A B C E F 缺点 浪费存储空间 G 64 127 二 链式存储结构二叉树的链表中的结点包含三个域 数据域和左 右指针域 二叉链表为了便于找到结点的双亲 则增加一个指向双亲结点的指针域 三叉链表 二叉树的结点 含有两个指针域的结点 含有三个指针域的结点 二叉树的存储结构 65 127 66 127 思考 在含有n个结点的二叉链表中有多少个空链域 N 1 67 127 二叉链表 typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree lchilddatarchild 结点结构 68 127 三叉链表 typedefstructTriTNode 结点结构TElemTypedata structTriTNode lchild rchild 左右孩子指针structTriTNode parent 双亲指针 TriTNode TriTree 69 127 第六章树和二叉树 内容 6 1树的定义和基本术语6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 6赫夫曼树及其应用 70 127 遍历二叉树 71 127 什么是遍历二叉树 二叉树的遍历指的是沿某条搜索路径访问二叉树 对二叉树中的每个结点访问一次且仅一次 访问 的含义可以很广 如 输出结点的信息等 72 127 什么是遍历二叉树 二叉树是非线性结构 每个结点有两个后继 则存在如何遍历 即按什么样的搜索路径遍历的问题 73 127 先左后右的遍历算法 先 根 序的遍历算法 中 根 序的遍历算法 后 根 序的遍历算法 74 127 先 根 序的遍历算法 若二叉树为空树 则空操作 否则 1 访问根结点 2 先序遍历左子树 3 先序遍历右子树 75 127 中 根 序的遍历算法 若二叉树为空树 则空操作 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 76 127 后 根 序的遍历算法 若二叉树为空树 则空操作 否则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 77 127 DLR 先序遍历序列 ABDC 先序遍历 78 127 LDR 中序遍历序列 BDAC 中序遍历 79 127 LRD 后序遍历序列 DBCA 后序遍历 80 127 练习 81 127 思考 1 三种遍历的第一个结点和最后一个结点的特征 82 127 算法的递归描述 中序 voidInorder BiTreeT void visit TElemType 遍历右子树 83 127 算法的非递归描述 中序 BiTNode GoFarLeft BiTreeT Stack S if T returnNULL while T lchild Push S T T T lchild returnT 84 127 算法的非递归描述 中序 voidInorder I BiTreeT void visit TelemType 栈空表明遍历结束 while Inorder I 85 127 线索二叉树 86 127 遍历二叉树是以一定规则将二叉树中的结点排成一个线性序列 将一个非线性结构线性化 问题单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继 这种信息只有在动态遍历中才能得到 所以某次遍历得到的信息 下次再用时 仍要重新遍历 87 127 一 如何保存在遍历过程中得到的信息 1 方法A 在每个结点上增加指针域fwd和bkwd 分别指示结点在任一次序遍历时 得到的前趋和后继 缺点 将大大降低存储空间的利用率 2 方法B 利用已有的指针域存放 n个结点的二叉链表中含有n 1个空指针域 可以充分利用这些空指针域 存放指向结点在某种遍历次序下的前趋和后继结点的指针 以提高遍历或查找结点在指定次序下的前趋和后继运算的效率 88 127 二 如何对二叉树进行线索化 线索化的实质 是将二叉树的空指针改为指向前趋或后继的线索 而前趋或后继的信息只有在遍历时才能得到 因此线索化的过程即为在遍历的过程中修改指针的过程 89 127 线索二叉树是利用空链存储结点在某种遍历次序下的前驱和后继关系 即原有非空的链保持不变 仍然指向该结点的左 右孩子结点 使空的left链指向前驱结点 空的right链指向后继结点 指向前驱或后继结点的链称为线索 对二叉树以某种次序进行遍历并加上线索的过程称为线索化 按先 中 后 根次序进行线索化的二叉树称为先 中 后 序线索二叉树 线索二叉树 90 127 线索二叉树的结点结构如下 91 127 一棵中序线索二叉树的二叉链表结构如下图所示 DBGEAFHCK 92 127 用线索树的最大优点是 由于有了线索的存在 在某些情况下可以很方便地找到指定结点在某种遍历序列中的前驱和后继 而不必再对二叉树重新遍历 另外 在线索树上进行某种次序遍历要比在一般二叉树上进行这种遍历容易得多 93 127 Review 思考 编写递归算法 计算二叉树中叶子结点的数目 94 127 思路 输出叶子结点比较简单 用任何一种遍历递归算法 凡是左右指针均空者 则为叶子intLeafCount BiTree BitreeT 求二叉树中叶子结点的数目 if T return0 空树没有叶子elseif T lchild 左子树的叶子数加上右子树的叶子数 LeafCount BiTree 95 127 第六章树和二叉树 内容 6 1树的定义和基本术语6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 6赫夫曼树及其应用 96 127 树或森林与二叉树之间存在一一对应的关系 任何一棵树或一个森林可唯一地对应到一棵二叉树 反之 任何一棵二叉树也能唯一地对应到一个森林或一棵树 97 127 在讨论转换之前 先温习一下它们的基本概念 树 是n n 0 个结点的有限集合 且满足两个条件 有且仅有一个特定的称为根的结点 其余结点又可分为m m 0 个互不相交的有限集合T1 T2 Tm 其中每个集合又都是一棵树 并称其为根的子树 森林 是m m 0 棵互不相交的树的集合 二叉树 是n n 0 个结点的有限集合 它或是空或者是由一个根结点及两棵互不相交的分别称做根的左右子树的二叉树组成 98 127 树和森林间的转换关系 删去树的根就得到一个森林 将森林中所有的树加上一个共同的根就得到一棵树 99 127 为了讨论树 森林 和二叉树间的转换关系 首先介绍树 森林 的存储结构 100 127 树的存储结构 101 127 1 双亲表示法双亲表示法是以一组连续的空间 数组 存储树的结点 数组的元素有两个域 数据域data和双亲位置域parent 存储表示 defineMAX TREE SIZE100typedefstructPTNode Telemtypedata Intparent PTNode typedefstruct PTNodenodes MAX TREE SIZE Intn PTree 102 127 103 127 练习 104 127 显然 无双亲的结点就是根结点每个结点的双亲位置域存的就是该结点双亲的数组下标 所以很方便查找结点的双亲位置如果要查找结点的孩子 则需要遍历 105 127 思考 如何查找叶子结点 数组下标没有出现过的结点就是叶子结点 106 127 2 孩子表示法 多重链表结构 孩子表示法中每个结点有多个指针域 每个指针指向一棵子树的根结点 形式一 107 127 形式一 108 127 形式一中结点的结构是同构的 浪费空间 109 127 形式二 110 127 形式三 将每个结点的孩子结点排列起来 以单链表作存储结构构成一个线性表 n个结点有n个孩子链表 每个孩子链表设一个头指针 而n个头指针又组成一个线性表 采用顺序存储 这就是孩子链表存储 111 127 112 127 3 孩子兄弟表示法 左儿子 右兄弟 孩子兄弟表示法是为每个结点设计三个域 一个数据元素域 一个该结点的第一个 最左边 孩子结点指针域 一个该结点的下一个兄弟结点指针域 又称二叉树表示法或二叉链表表示法 113 127 3 孩子兄弟表示法 左儿子 右兄弟 存储表示 typedefstructCSNode Elemtypedata StructCSNode firstchild nextbrother CSNode CSTree 这种存储结构便于实现各种树的操作 更易于实现找结点的孩子 114 127 孩子兄弟表示法 115 127 练习 116 127 树与二叉树转换 117 127 将树转换成二叉树加线 在兄弟之间加一连线抹线 对每个结点 除了其左孩子外 去除其与其余孩子之间的关系旋转 以树的根结点为轴心 将整树顺时针转45 树转换成的二叉树其右子树一定为空 118 127 练习 A B C D E F G 119 127 将二叉树转换成树