合肥工业大学数据结构课件第七章 树和二叉树.ppt

第七章 树和二叉树 第七章 树和二叉树 7.1 树的相关概念和术语 7.2 二叉树的定义、性质和存储结构 7.3 二叉树的遍历及其应用 7.4 线索二叉树 7.5 树和森林 7.6 哈夫曼树（Huffman） 7.1 树的相关概念和术语 家族关系示意图/单位机构组成示意图 定义：树T是由n个结点组成的有限集合（n 0）。 其中有一个根结点， 其余结点可划分成m个（m=0）互不相交的子集 T1, T2, ... ,Tm， 且这些子集也分别构成树。 （注意：有无空树的概念） 7.1 树的相关概念和术语 术语 关系术语 孩子结点 —— 子树的根 父结点 兄弟结点 —— 同一个结点的孩子结点互为兄弟 祖先结点 后代结点 层次类术语 根的层次为1 其余结点的层次为其父结点层次加1 高度/深度 —— 整个树中结点的最大层次 度 —— 结点的孩子数目称为结点的度 叶子（终结点）—— 度为0 分支结点----度不为0的结点（非叶子结点） 树的度 —— 最大的结点度 森林 —— 多棵树 有序树/无序树 ——按照兄弟结点之间的排列是否有序 7.1 树的相关概念和术语 运算 （1）初始化 （2）查找 —— 结点的父、兄弟、祖先、后代、根 （3）插入 —— 叶子， 子树 （4）删除 —— 叶子，子树 树的存储？ 7.2 二叉树的定义、性质和存储结构 7.2.1定义 二叉树T：是n个结点组成的有限集合（n = 0）， n=0时为空二叉树， 否则：其中有一个根结点， 其余结点可以划分成两个互不相交的子集TL, TR， 且TL, TR也分别构成二叉树 —— 左、右子树。 7.2 二叉树的定义、性质和存储结构 二叉树与树的区别： 是两种不同性质的结构； 二叉树存在空树，树不存在空树； 二叉树恰有两个子树，树可有多个； 二叉树子树有序，树无序。 比较三个结点的树与二叉树的各有几种不同的形态。 三个结点的树 三个结点的二叉树 7.2 二叉树的定义、性质和存储结构 由定义可知，依据结点数的多少可将二叉树划分为五种不同的形态： （1）空树，即结点数为0 （2）单结点二叉树，即仅有一个结点 （3）左子树为空右子树不空 （4）右子树为空左子树不空 （5）左右子树均不空 7.2 二叉树的定义、性质和存储结构 7.2.2二叉树的性质 性质1：第i层的结点数≤2i-1； 性质2：高度为k（k≥1）的二叉树的结点总数≤2k-1； 性质3：设二叉树的叶子结点数为n0，度为2的结点数为n2，则 n0=n1+1。 证明：设总结点数为n，度为1的结点数为n1，则 n=n0+n1+n2 ——结点数 （1） n-1=n1+2n2 ——分支数 （2） 式（1）－（2）得 n0=n2+1 课堂练习：已知一棵二叉树中，有20个叶子结点，10个结点只有左孩子，15个结点只有右孩子，求该二叉树的总结点数。 7.2 二叉树的定义、性质和存储结构 定义1：称高度为k且有2k-1个结点的二叉树为满二叉树。 例如，高度为1~4的满二叉树如下。 7.2 二叉树的定义、性质和存储结构 定义2：在满二叉树最下一层从右到左依次连续去掉若干个结点的二叉树称为完全二叉树。 下面分别给出完全二叉树和非完全二叉树的示例。 7.2 二叉树的定义、性质和存储结构 对完全二叉树编号 编号的方式：从上到下，每一层中从左到右，根节点编号为1。 例：下面完全二叉树的编号 7.2 二叉树的定义、性质和存储结构 性质4：有n个（n≥1）结