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）棵互不相交的树构成的集 合。