③树的最大层次称为树的深度。 ④在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树，叶子结点没有子树。
这棵树的深度为5。
以K和T结点为根所构成的子树分别为：
在计算机中可以用树结构来表示算术表达式。原则，略。树在计算机中通常用多重链表表示。略。
对比树型结构和线性结构的结构特点：
*考点16 二叉树及其性质 重点
1、什么是二叉树 重点
二叉树（binary tree）是一种重要的非线性结构。
二叉树具有以下两个特点：
①非空二叉树只有一个根结点。 ②每个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，但树结构中的每一个结点的度可以是任意的。
在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。
当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。
图1是一棵只有根结点的二叉树，图2是一棵深度为4的二
叉树。
2、二叉树的基本性质 重点
性质1 在二叉树的第k层上，最多有2k-1（k≥1）个结点。 根据二叉树的特点，这个性质是显然的。
性质2 深度为m的二叉树最多有2m-1个结点。
深度为m的二叉树是指二叉树共有m层。 根据性质1，只要将第1层到第m层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即：
21-1+22-1+23-2+…+2m-1=2m-1
性质3 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多1个。
解释：不讲了。
假设二叉树中有n0个叶子结点，n1个度为1的结点，n2个度为2的结点，则二叉树中总的结点数n为：
n= n0+n1+n2 (1)
由于在二叉树中除了根结点外，其余每一个结点都有惟一的一个分支进入。设二叉树中所有进入分支的总数为m，则二叉树中总的结点数为：
n= m+1 (2)
又由于二叉树中这m个进入分支是分别由非叶子结点射出的。其中度为1的每个结点射出1个分支，度为2的每个结点射
出2个分支。因此，二叉树中所有度为1与度为2的结点射出的分支总数为n1+2n2。而在二叉树中，总的射出分支数应与总的进入分支数相等，即：
m= n1+2n2 (3)
将（3）代入（2）式有：
n= n1+2n2 +1 (4)
最后比较（1）式和（4）式有：
n0+n1+n2= n1+2n2 +1
化简后得：n0 =n2 +1
例：图2所示的二叉树中，3个叶子结点，有2个度为2的结点，度为0的叶子结点比度为2的结点多一个。
性质4 具有n个结点的二叉树，其深度至少为?log2n? +1，其中?log2n?表示取log2n的整数部分。
这个性质可以由性质2直接得到。不讲了。 解释：2m-1=n，则m= log2(n+1)≥?log2n?+1
3、满二叉树与完全二叉树 重点
满二叉树与完全二叉树是两种特殊形态的二叉树. （1）满二叉树
除了最后一层外，每一层上的所有结点都有两个子结点的二叉树称为满二叉树。
也就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。
图3、图4和图5分别是深度为2、3、4的满二叉树。
结点数为3
结点数为7
结点数为15
（2）完全二叉树
除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。这样的二叉树称为完全二叉树。
更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。
满二叉树是完全二叉树，但完全二叉树一般不是满二叉树。 图6、图7分别是深度为3、4的完全二叉树。