5.节点的层次和树的高度：树中的每个节点都处在一定的层次上节点的层次从树根开始定义，根节点为第1层，它的孩子节点为第2层以此类推，一个节点所在的层次为其品B双亲节点所在的层次加1。树中节HE（或树点的最大层次称为树的高度的深度）。16.有序树和无序树：若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。11
11 5 . 节点的层次和树的高度： 树 中的每个节点都处在一定的层次上 。 节点的层次从树根开始定义 ，根节 点为第 1 层 ，它的孩子节点为第 2 层 , 以此类推 ,一个节点所在的层次为其 双亲节点所在的层次加 1 。树中节 点的最大层次称为树的高度 （或树 的深度 ） 。 6 . 有序树和无序树：若树中各 节点的子树是按照一定的次序从左 向右安排的 ，且相对次序是不能随 意变换的 ，则称为有序树 ，否则称 为无序树 。 A B C D E F GJ H I K L M 1 2 3 4
7.森林：n（n>0）个互不相交的树的集合称为森林森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给n棵独立的树加上一个节点，并把这n棵树作为该节点的子树，则森林就变成了树。12
12 7. 森林：n（n＞0）个互不相交的树的集合称为森林。 森林的概念与树的概念十分相近，因为只要把树的根节 点删去就成了森林。反之，只要给n棵独立的树加上一 个节点，并把这n棵树作为该节点的子树，则森林就变 成了树
7.1.4 树的性质性质1树中的节点数等于所有节点B的度数加1。IRHH证明：根据树的定义，在一棵树中，M除树根节点外，每个节点有具仅有一个前驱节点。也就是说，每个节点与度之和=分支数指向它的一个分支一一对应，所以除分支数=n-1树根之外的节点数等于所有节点的分所以，n=度之和+1支数（度数），从而可得树中的节点数等于所有节点的度数加1。13
13 7.1.4 树的性质 性质1 树中的节点数等于所有节点 的度数加1。 证明：根据树的定义，在一棵树中， 除树根节点外，每个节点有且仅有一 个前驱节点。也就是说，每个节点与 指向它的一个分支一一对应，所以除 树根之外的节点数等于所有节点的分 支数（度数），从而可得树中的节点 数等于所有节点的度数加1。 度之和＝分支数 分支数=n-1 所以，n=度之和+1 A B C D E F G J H I K L M
求解大法归纳求解树的节点个数问题：对于度为m的树，在n、no、nl、n2、…、nm中只有两个参数未知时，一般可求出这两个值。例如求n和n.的求解过程如下：n=no+ni+..+nm度之和=n-1度之和=n,+2n,+...+mnm所以有:n=n,+2n,+...+mnm+1=no+ni+...+nm这样:no-nz+...+(m-1)nm+114
14 求解树的节点个数问题：对于度为m的树，在n、n0、n1、 n2、.、nm中只有两个参数未知时，一般可求出这两个值。 例如求n和n0的求解过程如下： n=n0+n1+.+nm 度之和=n－1 度之和=n1+2n2+.+mnm 所以有：n＝n1+2n2+.+mnm+1=n0+n1+.+nm 这样：n0=n2+.+(m－1)nm+1 求解方法归纳
例：一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶子节点个数是A.41B.82C.113D.122注：本题为2010年全国考研题15
15 例：一棵度为4的树T中，若有20个度为4的节点，10个 度为3的节点，1个度为2的节点，10个度为1的节点，则树T 的叶子节点个数是 。 A.41 B.82 C.113 D.122 注：本题为2010年全国考研题