《C++程序设计第四章树形结构.ppt》由会员分享，可在线阅读，更多相关《C++程序设计第四章树形结构.ppt（126页珍藏版）》请在金锄头文库上搜索。
1、数据结构第4章树型结构 学习要点 熟练掌握二叉树的结构特性 了解相应的证明方法 建立存储结构是进行操作的前提 故须熟悉二叉树的各种存储结构 并把握各种存储结构的特点及适用范围 遍历二叉树是二叉树各种操作的基础 实现二叉树遍历的具体算法与所采用的存储结构有关 掌握各种遍历策略的递归算法 灵活运用遍历算法实现二叉树的其他操作 理解包括层次遍历在内的各种非递归遍历的算法 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系 熟练掌握二叉树的线索化过程以及在中序线索化二叉树上找到给定结点的前驱和后继的方法 二叉树的线索化过程是基于对二叉树进行遍历 而线索二叉树上的线索又为相应的遍
2、历提供了方便 熟悉树的各种存储结构及其特点 掌握树和森林与二叉树的转换方法 学会编写实现树的各种操作的算法 理解等价关系和等价类问题 了解最优树的特性 掌握建立最优树和赫夫曼编码的方法 第4章树型结构 树型结构是一种典型的分支结构 并且具有明显的层次特征 树型结构在客观世界中是广泛存在的 如家族谱 组织机构 博弈等都可用树型结构形象地表示 树型结构在计算机领域中也有着广泛的应用 编译程序 数据库系统 分析算法 4 1树 森林的定义及基本术语 树 tree 是n 个结点的有限集T 当n 0时称为空树 否则满足以下两个条件 有且仅有一个特定的结点 称为树的根 root 其余结点可分为m 个互不相交
3、的子集T1 T2 Tm 其中每一个子集本身又是一棵树 并称其为根结点的子树 subtree 4 1树 森林的定义及基本术语 森林是m m 0 棵互不相交的树的集合 用森林的定义也可定义树 一棵非空的树由根结点及其子树森林所构成 树和森林均为典型的树型结构 从形态上看 树结构类似于自然界倒长的一棵树 4 1树 森林的定义及基本术语 基本术语结点 包含了数据元素及若干个指向其子树的分支 结点的度 结点的子树数目或分支个数 树的度 在树中取各结点的度的最大值 分支结点 又称非终端结点 度大于零的结点 树叶结点 又称终端结点 度为零的结点 结点的路径 根结点到该结点所经分支和结点构成结点的路径 结点的
4、路径长度 根结点到该结点路径上所经分支的数目 4 1树 森林的定义及基本术语 基本术语结点的层次 设根结点的层次为1 则其子树的根结点层次为2 第L层结点的子树的根结点层次为L 1 树的深度 树中结点 该结点必为树叶结点 的最大层次 孩子结点及双亲结点 结点的子树的根结点称为该结点的孩子结点 该结点又称为孩子结点的双亲结点 兄弟结点 拥有同一个双亲结点的若干个结点互称为兄弟结点 堂兄弟结点 在同一层次上 但双亲结点不同的若干个结点称为堂兄弟结点 4 1树 森林的定义及基本术语 基本术语祖先结点 根结点到该结点路径上的所有结点均为该结点的祖先结点 子孙结点 某结点的子树中所包含的所有结点均为该结
5、点的子孙结点 无序树 子树之间不存在次序关系 即子树能够调换 则称该树为无序树 有序树 子树之间映射客观存在的次序关系 子树不能调换 则称该树为有序树 线性结构和树型结构的比较 4 2二叉树 4 2 1二叉树的结构定义二叉树定义二叉树是n n 0 个结点的有限集 当n 0时 二叉树为空 当n 0时 二叉树由一个根结点及至多两棵互不相交的左右子树组成 且左右子树都是二叉树 二叉树特点每个结点至多有二棵子树 即不存在度大于2的结点 二叉树的子树有左 右之分 且其次序不能任意颠倒 4 2 1二叉树的结构定义 二叉树的基本形态 空二叉树 只有根结点的二叉树 右子树为空 左子树为空 左右子树均非空 4
6、2 2几种特殊形态的二叉树 满二叉树 一棵深度为k的二叉树若每一层上的结点数都达到最大则称其为满二叉树 完全二叉树 一棵具有n个结点且深度为k的二叉树若前k 1层的结点数都达到最大 剩余的结点在第k层中从左至右连续分布则称其为完全二叉树 拟满二叉树 一棵具有n个结点且深度为k的二叉树若前k 1层的结点数都达到最大 剩余的结点在第k层中随机分布则称其为拟满二叉树 正则二叉树 在一棵二叉树中 如果只存在度为0和度为2的结点则称其为正则二叉树 平衡二叉树 在一棵二叉树中 若其任一子树型均满足 左子树的深度 右子树的深度 1 则称其为平衡二叉树 4 2 2几种特殊形态的二叉树 4 2 3二叉树的性质
7、二叉树性质1在二叉树的第i层上至多有2i 1个结点 i 1 证明 用归纳法证明之i 1时 只有一个根结点 2i 1 20 1 是对的假设对所有j 1 j i 命题成立 即第j层上至多有2j 1个结点 那么 第i 1层至多有2i 2个结点又二叉树每个结点的度至多为2 第i层上最大结点数是第i 1层的2倍 即2i 2 2 2i 1故命题得证 4 2 3二叉树的性质 二叉树性质2深度为k的二叉树上至多含2k 1个结点 k 1 证明基于上一条性质 深度为k的二叉树上的结点数至多为20 21 2k 1 2k 1 4 2 3二叉树的性质 二叉树性质3对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的
8、结点 则必存在关系式 n0 n2 1 证明 设n1为二叉树中度为1的结点数 二叉树上结点总数n n0 n1 n2 又二叉树上分支总数b n1 2n2 而b n 1 n0 n1 n2 1 由此 n0 n2 1 一棵完全二叉树的例子 4 2 3二叉树的性质 二叉树性质4具有n个结点的完全二叉树的深度为 1证明设完全二叉树的深度为k则根据第二条性质得2k 1 n 2k即k 1 log2n k因为k只能是整数 因此 k 1 4 2 3二叉树的性质 二叉树性质5若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号 则对完全二叉树中任意一个编号为i的结点 若i 1 则该结点是二叉树的根 无双亲 否
9、则 编号为 i 2 的结点为其双亲结点 若2i n 则该结点无左孩子 否则 编号为2i的结点为其左孩子结点 若2i 1 n 则该结点无右孩子结点 否则 编号为2i 1的结点为其右孩子结点 4 2 3二叉树的性质 用归纳法证明如下 当i 1时 由完全二叉树的定义及编号规则可知 i结点是二叉树的根 其左孩子若存在编号是2即2i 右孩子若存在编号是3即2i 1 性质成立 设编号为i 1的结点其左孩子若存在编号是2 i 1 右孩子若存在编号是2 i 1 1性质成立 由完全二叉树的定义及编号规则可知 对于第i个结点 其左孩子若存在 编号必为编号为i 1的那个结点的左孩子位序加2 即2 i 1 2 2i
10、右孩子若存在 编号必为编号为i 1的那个结点的右孩子位序加2 即2 i 1 1 2 2i 1 故 和 成立 性质得证 4 2 4二叉树的存储结构 顺序存储结构特点结点间关系蕴含在其存储位置中浪费空间 适于存满二叉树和完全二叉树实现 按满二叉树的结点层次编号 依次存放二叉树中的数据元素 constMAXSIZE 100 暂定二叉树中结点数的最大值为100structSqBiTree ElemType base 存储空间基址intnodeNum 二叉树中结点数 二叉树的存储结构 顺序存储 4 2 4二叉树的存储结构 二叉树的链式存储结构 二叉链表 BTnode h 二叉链表结点结构template
11、structBTnode ElemTypeData BTnode Lchild Rchild lchild data rchild 二叉链表例 A B C D E F G 在n个结点的二叉链表中 有n 1个空指针域 Root 4 2 4二叉树的存储结构 二叉树的链式存储结构 三叉链表 templatestructBTnode ElemTypeData BTnode Lchild Rchild BTnode parent lchild data rchild parent 三叉链表例 root 4 2 5二叉链表类的定义 二叉链表类模板 BinaryTree h ifndef BINARYTRE
12、E H define BINARYTREE H include include include BTnode h usingnamespacestd template 二叉链表类classBinaryTree public BinaryTree m root NULL 构造函数BinaryTree constBinaryTree 4 2 5二叉链表类的定义 二叉链表类模板 BinaryTree 4 2 5二叉链表类的定义 二叉链表类模板 先序递归遍历二叉树的接口函数voidPreorderTraverse void visit constElemType 4 2 6二叉树的递归遍历 问题的提出
13、顺着某一条搜索路径巡访二叉树中的结点 使得每个结点均被访问一次 而且仅被访问一次 访问 的含义可以很广 如 输出结点的信息等 遍历 是任何类型均有的操作 对线性结构而言 只有一条搜索路径 因为每个结点均只有一个后继 故不需要另加讨论 而二叉树是非线性结构 每个结点有两个后继 则存在如何遍历即按什么样的搜索路径遍历的问题 4 2 6二叉树的递归遍历 从下图中可以看到 二叉树是由根结点 D 左子树 L 及右子树 R 三部分组成 由这三部分的组合可得到以下的搜索路径 DLR LDR LRD DRL RDL RLD 其中 先左后右的搜索方式是最常用的遍历二叉树的方法 4 2 6二叉树的递归遍历 先序遍
14、历二叉树 DLR 若二叉树为空树 则空操作 否则 访问根结点先序遍历左子树先序遍历右子树 先序遍历右图得到 abdeghcf 4 2 6二叉树的递归遍历 先序递归遍历二叉树templatevoidBinaryTree PreorderTraverse BTNode T void visit constElemType 4 2 6二叉树的递归遍历 中序遍历二叉树 LDR 若二叉树为空树 则空操作 否则 中序遍历左子树访问根结点中序遍历右子树 中序遍历右图得到 dbgheafc 4 2 6二叉树的递归遍历 后序遍历二叉树 LRD 若二叉树为空树 则空操作 否则 后序遍历左子树后序遍历右子树访问根结
15、点后序遍历右图得到 dhgebfca 4 2 7几个二叉树基本操作的例子 建立二叉树对前页所示的二叉树进行先序遍历 得到一个变通的遍历结果 abd eg h cf 建立二叉链表的存储结构 利用先序遍历思想 以变通的遍历结果作为输入数据 执行以下操作 若当前输入数据为特殊字符 则当前二叉树根结点为空 否则 1 生成根结点 当前数据写入根结点数据域2 建立左子树3 建立右子树 4 2 7几个二叉树基本操作的例子 建立二叉树 按先序次序输入结点值的方式建立二叉树TtemplatevoidBinaryTree Create1 BTNode 4 2 7几个二叉树基本操作的例子 销毁二叉树如果二叉树为空则
16、结束 否则 1 销毁左子树 2 销毁右子树 3 释放根结点 显然 这是一个递归的过程 借助了后序遍历的思想 4 2 7几个二叉树基本操作的例子 销毁二叉树 销毁二叉链表形式的二叉树TtemplatevoidBinaryTree Destroy BTNode 4 2 7几个二叉树基本操作的例子 求二叉树深度的算法如果二叉树为空则深度为0 否则 1 求二叉树左子树的深度 2 求二叉树右子树的深度 3 二叉树的深度是左 右深度大的那棵子树的深度加1 这也是一个递归的过程 可借助后序遍历思想实现 4 2 7几个二叉树基本操作的例子 求二叉树深度的算法 求二叉树的深度templateintBinaryTree Depth BTNode T if T return0 inth1 h2 h1 Depth T lchild h2 Depth T rchild returnh1 h2 h1 1 h2 1 4 2 8二叉树的非递归遍历 中序遍历二叉树的非递归算法 利用栈 templatevoidBinaryTree InorderTraverseNonRecursive void visit constE
