《计算机软件基础》第三章 非线性数据结构（3-2）树

3.2树 树的定义 树是由n(n>0)个结点构成的有限集合 当n=0时称为空树;否则,任意一棵非空树必符 合以下两个条件: 1)树中有且仅有一个特定的称为根的结点; 2)除根结点外,其余结点可分为m个互不相交 的有限集合T1,T2,T3,…,Tm,其中每一个 集合本身又是一棵树,称之为根的子树

计 算 机 软 件 基 础 3．2 树 一．树的定义 树是由n（n≥0）个结点构成的有限集合。 当n=0时称为空树；否则，任意一棵非空树必符 合以下两个条件： 1）树中有且仅有一个特定的称为根的结点； 2）除根结点外，其余结点可分为m个互不相交 的有限集合T1，T2，T3，，Tm，其中每一个 集合本身又是一棵树，称之为根的子树。    

令树的主要特点(形态与自然界中的树十分相似) 1.只有一个根结点 2.结点分布呈明显的层次关系 3.递归定义 ①树的示意图

计 算 机 软 件 基 础 ❖ 树的主要特点（形态与自然界中的树十分相似） 1.只有一个根结点 2. 结点分布呈明显的层次关系 3. 递归定义 B C D E F H A G I 树的示意图    

树的逻辑结构 分析:对于树中的任意结点来说,若其为根 结点,则其无双亲结点;若其为叶子,则其 无孩子结点;否则,此结点有且仅有一个双 亲结点,并且有若干个孩子结点。 树中结点的逻辑关系是一种一对多 的关系,体现在一个结点只能有一个双亲, 但可以有多个孩子

计 算 机 软 件 基 础 ❖ 树的逻辑结构 分析：对于树中的任意结点来说，若其为根 结点，则其无双亲结点；若其为叶子，则其 无孩子结点；否则，此结点有且仅有一个双 亲结点，并且有若干个孩子结点。 结论：树中结点的逻辑关系是一种一对多 的关系，体现在一个结点只能有一个双亲， 但可以有多个孩子。    

二、树的有关术语 结点的度:每个结点的子树个数。 树的度:树中所有结点的度的最大值 叶子:又称终端结点,是指度为0的结点。 分支结点:又称非终端结点,度不为0的结点。 双亲和孩子:一个结点的子树的根结点称为此 结点的孩子;若结点1是结点2的孩子,则结点2 就被称为是结点1的双亲。 结点的层次:规定根为第一层,其下面的一层 为第二层,依次类推

计 算 机 软 件 基 础     二、树的有关术语 •结点的度：每个结点的子树个数。 •树的度：树中所有结点的度的最大值。 •叶子：又称终端结点，是指度为0的结点。 •分支结点：又称非终端结点，度不为0的结点。 •双亲和孩子：一个结点的子树的根结点称为此 结点的孩子；若结点1是结点2的孩子，则结点2 就被称为是结点1的双亲。 •结点的层次：规定根为第一层，其下面的一层 为第二层，依次类推

树的深度:树中结点的最大层次数。 兄弟和堂兄弟:同一双亲的孩子之间互称兄弟; 其双亲在同一层的结点互为堂兄弟 有序树和无序树:如果树中任一结点的各个子 树规定从左到右是有次序的,即不能互换位置, 则称该树为有序树,否则称为无序树。 森林:由m(m>0)棵互不相交的树构成的集

计 算 机 软 件 基 础 •树的深度：树中结点的最大层次数。 •兄弟和堂兄弟：同一双亲的孩子之间互称兄弟； 其双亲在同一层的结点互为堂兄弟。 •有序树和无序树：如果树中任一结点的各个子 树规定从左到右是有次序的，即不能互换位置， 则称该树为有序树，否则称为无序树。 •森林：由m（m≥0）棵互不相交的树构成的集 合。    

二叉树 计1.二叉树的定义 二叉树是一个由n(n>0)个结点构成的 有限集合,它或者为空树,或者是由一个根 结点和两个分别被称为左子树和右子树的互 不相交的子集构成的,其左、右子树也是二 叉树

计 算 机 软 件 基 础 三. 二叉树 1. 二叉树的定义 二叉树是一个由n（n≥0）个结点构成的 有限集合，它或者为空树，或者是由一个根 结点和两个分别被称为左子树和右子树的互 不相交的子集构成的，其左、右子树也是二 叉树。    

二叉树的特点 A 1)度小于等于2,即 树中不存在度大于2的 B 结点; (2)有序树,即每个 结点的子树有左右之分, G H 不能交换 二叉树示意图

计 算 机 软 件 基 础 B C D E G F H A 二叉树示意图 ❖ 二叉树的特点 （1）度小于等于2，即 树中不存在度大于2的 结点； （2）有序树，即每个 结点的子树有左右之分， 不能交换。    

2.二叉树的性质 (1)二叉树的第层上至多有21个结点。 (2)深度为k的二叉树的结点总数至多为2k-1 个。 (3)若一棵二叉树上度为0(叶子)和度为2的 结点数分别为nn和n2, 则:n=n2+1

计 算 机 软 件 基 础 2. 二叉树的性质     （1）二叉树的第i层上至多有2 i-1个结点。 （2）深度为k的二叉树的结点总数至多为2 k -1 个。 （3）若一棵二叉树上度为0（叶子）和度为2的 结点数分别为n0和n2， 则：n0=n2+1

3.特殊的二叉树 (1)满二叉树 若一棵二叉树的深度为k,其结点总数为2k-1 个,则称此二叉树为满二叉树。 B 满二叉树示例 E F G

计 算 机 软 件 基 础 3. 特殊的二叉树 （1）满二叉树 若一棵二叉树的深度为k，其结点总数为2 k -1 个，则称此二叉树为满二叉树。 B C D E G A F 满二叉树示例    

(2)完全二叉树 若一棵深度为k、具有n个结点的二叉树,能 够与一棵同深度的满二叉树中编号从1到n的结 点(从上到下,从左到右编号)相对应,则称 此二叉树为完全二叉树。 思考 A 深度为3的完全 二叉树有几种 B 形态? E 完全二叉树示例

计 算 机 软 件 基 础 （2）完全二叉树 若一棵深度为k、具有n个结点的二叉树，能 够与一棵同深度的满二叉树中编号从1 到n的结 点（从上到下，从左到右编号）相对应，则称 此二叉树为完全二叉树。 B C D E A 完全二叉树示例 思考： 深度为3的完全 二叉树有几种 形态？    