树是非线性的数据结构，是由n(n=0)个有限节点组成的具有层次关系的集合。 树中有一个特殊的节点，称为根节点，根节点没有前驱节点，除了根节点以外，其馀的节点分为m(m0 )个相互不相交的集合T1、T2、…、Tm，每个集合ti(1=I=m 每个子树的根节点只有一个前体，可以有0个以上的后继者。
因此，树是递归定义的。 也就是说，任何树都可以分解为根的部分树的形状，另外，部分树可以分解为对应的根和部分树，直到不能分割为止。
递归：通常求解分割统治问题。 也就是说，可以将当前问题分解为子问题，子问题可以继续分解
树概念：
节点的度：将一个节点中包含的子树的数量称为该节点的度； 上图： a的为6叶节点或终结节点，度为0的节点称为叶节点； 上图： b、c、h、I…等节点为叶节点的非终结节点或分支节点：度不为0的节点； 上图： d、e、f、G…等节点是分支节点的父节点或父节点。 如果一个节点包含子节点，则该节点称为该子节点的父节点。 上图： a是b父节点的子节点或子节点。 一个节点中包含的子树的根节点称为该节点的子节点。 上图： b为a的子节点兄弟节点：具有相同父节点的节点相互称为兄弟节点； 上图：乙、丙为兄弟节点树度。 一棵树中，最大的节点度叫做树度。 上图：树度为6个节点的层次：从根开始定义，根为第1层，根的子节点为第2层； 树的高度或深度：树中节点的最大级别； 上图(树高4表兄弟节点)父母在同一层节点上互为表兄弟； 上图： h、I互为兄弟节点祖先：分支上从根到该节点经过的所有节点； 上图： a是所有节点祖先的子孙：以某个节点为根的子树中的任意一个节点称为该节点的子孙。 上图：所有节点都是a的后代的森林： m(m0 )本互不相交的树的集合称为森林。 二叉树的一个二叉树是节点的有限集合。 该集合为空，或者由在一个根节点上添加了两个左子树和被称为右子树的二叉树的二叉树构成。
二叉树的特点：
每个节点最多有两个子树。 也就是说，它是二叉树的非丰度大于2的节点。 二叉树的子树有左右之分，不能颠倒子树的顺序。特殊的二叉树
满二叉树：一个二叉树，当每个层次的节点数达到最大值时，该二叉树满二叉树。 也就是说，如果一个二叉树的阶数为k，并且节点总数为(2^k )-1，则其将被二叉树填充。 完全二叉树：完全二叉树是一种高效的数据结构，完全二叉树由完全二叉树引导。 关于具有深度为k的n个节点的二叉树，只把各个节点与深度为k的满二叉树中编号为1到n的节点一一对应的情况称为完全二叉树。 需要注意的是，二叉树是一种特殊的完全二叉树。 http://www.Sina.com/http://www.Sina.com /
满二叉树
设根节点层数为1，则在一根非空二叉树的第I层上最多有完全二叉树个节点，设根节点的层数为1，则深度为h的二叉树的最大节点数为http://www.Sina.com/3358
底，n 1是对数)对于具有n个节点的完全二叉树，如果按照从上到下从左到右的排列顺序从0开始对所有节点编号
编号I的节点在i0的情况下包括I位置节点的二叉树的性质； i=0，I是根节点编号，没有父母的节点为2i 1n，2^(i-1)，如果不是2i 1=n，则没有左边的孩子，则为2i 2n，2^h- 1.，2i 2=n
对于任何二叉树，如果度为0、叶节点的数量为n0、度为2的分支节点的数量为n2，则n0=n2 1
证明：
练习有练习问题的二叉树有399个节点，如果其中有199个度为2的节点，则该二叉树中的叶节点数为() ) ) ) ) ) ) )。
a不存在这样的二叉树
B 200
C 198
从二叉树性质3可知，D 199选b为n0=n2 1，因此n0=199 1=200
在具有2n个节点的完全二叉树中，叶的节点数为() ) ) )。
A n
B n 1
C n-1
在D/2中选择a，首先完全二叉树度为1 (即n1 )的节点个数只有0或1，即n1{ 0，1 }，n0 n1 n2=2n，且n0=n2 1，因此2n0 n1=2n 1。 n1=0时，n0=n(n/2； n的时候
1 = 1时，n0 = n。 一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）A 11
B 10
C 8
D 12
选B，首先根据性质4可知，若为满二叉树，则其高度为 h = Log(n+1)(以2为底)，再联系满二叉树和完全二叉树的概念，可得知完全二叉树的前n-1层是满的，因此若为完全二叉树，则 2^h - 1^ + x = n ,其高度为h = log(n - x) + 1，且x∈[1,2h-1]，所以代入题中，h = log(531 - x) + 1，还是得不出答案，于是我们可以根据选项来排除，若h = 11，则2^11 - 1^= 1024，对应x∈[1,512]，则1024 + x = 531，不成立；若h = 10，则2^10 - 1^= 512，对应x∈[1,256]，则 512 + x = 531，成立；因此该树得高度为10。
一个具有767个节点的完全二叉树，其叶子节点个数为（）A 383
B 384
C 385
D 386
选B，过程思想同第二个习题