〈新〉计算机软件技术基础课件-5(树与二叉树).ppt

* * 物料管理 File * * * Algorithms and DataStructures:files 1、树的定义及基本术语 2、树的存储结构 3、二叉树的定义、性质及其存储结构  4、二叉树的遍历 5、二叉树的应用 §3 树 1、树的定义及基本术语 张源 张明 张亮 张丽 张林 张维 张平 张华 张群 张晶 张磊 老祖宗 儿子（辈） 孙子（辈） 曾孙（辈） 定义： 树是由n(n≥0)个结点组成的有限集合T。其中有且仅有一个结点称为根结点，其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，… … Ti … Tm，每个Ti本身又是一棵树，称为根结点的子树。 树的定义是递归的！ 基本术语 结点（node）： 树中元素。 结点的度(degree)： 结点拥有的子树数。 树形数据结构是结点之间有分支，有层次的非线性数据结构。 一棵树中最大的结点度数为树的度。 1、树的定义及基本术语 双亲（parents）： 孩子结点的上层结点称为这些结点的双亲。 兄弟（sibling）： 同一双亲的孩子。 结点的层次（level）： 从根结点开始算起，根为第一层，根的直接后继结点为第二层，依次类推。 深度（depth）： 树中结点的最大层次数。 有序树： 树中结点在同一层中按从左到右有序排列，不能互换的称为有序树。 森林： m(m≥0)棵互不相交的树的集合。 孩子(child)： 除根结点外，每个结点都是其前趋结点的孩子。 叶子(leaf)： 度为0的结点。 2、树的存储结构 树的存储一般采用多重链表结构。 含义：每个结点设有多个指针域，其中每个指针指向一棵子树的根结点。 结点的结构类型： 结点异构型:即根据每个结点的子树数设置该结点的指针域个数。 结点同构型:即每个结点的指针域个数均为树的度数。 异构型虽节省存储空间但对运算不利；同构型运算方便但存在空链域。 A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 结点同构 2、树的存储结构 eg：一棵具有n个结点，度为k的树。 指针域总个数为nk 有用指针域个数为（n-1）。 空链域个数为：nk-(n-1)=n(k-1)+1。 k取不同值时，空链域所占比例： 结点数目相同但度数不同的树，采用同构型时，空链域所占比例分析 k=2： k=3： k→∞： K越大则空链域占用比例就越高。 当k=2时，空链域占用比例最低。 3、二叉树的定义、性质及存储结构 定义 二叉树是n(n≥0)个结点的有限集合，它或为空树或是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 二叉树也是递归定义的！ 二叉树的特点： 每个结点最多有两棵子树，并且有左右之分。 A B E F A B E F 两棵不同的二叉树 二叉树的性质 性质一： 二叉树的第i层上至多有2i-1(i≥1)个结点。 性质二： 深度为h的二叉树上至多含有2h-1个结点。 性质三： 在任意的二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有: n0=n2+1。 性质三证明： 设n1表示度数为1的结点，则总结点数n为：n=n0+n1+n2； 综合这二者关系可得性质三 另一方面，度为1的结点有1个孩子，度为2的结点有2个孩子。故二叉树中孩子结点总数为：n1+2n2，又二叉树中只有根结点不是任何结点的孩子，故总结点数为n=n1+2n2+1 ； 此处：指针数不包括空指针 几种特殊形式的二叉树 满二叉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3、二叉树的定义、性质及存储结构 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 完全二叉树 非完全二叉树 完全二叉树 满二叉树 一棵深度为h，且有2h-1个结点的二叉树称为满二叉树。 几种特殊形式的二叉树 3、二叉树的定义、性质及存储结构 平衡二叉树 非平衡二叉树 平衡二叉树 1 2 3 4 5 6 7 1 6 2 3 7 4 5 满二叉树 完全二叉树 二叉树的存储结构 二叉树的顺序存储结构 为实现顺序存储，必须把二叉树中所有结点按照一定的次序组成一个线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。 对于完全二叉树，从树根起，自上层到下层，每层从左到右的给结点进行编号，就能得到一个反映整棵二叉树结构的线性序列。 对于一棵含有n个结点的二叉树，假设编号为i的结点是Ki（1≤i ≤n ），则可得到以下几点规律： 特点：左子树与右子树