基本术语
结点的度：结点拥有的子树的数目
叶子结点：度为0的结点
分支结点：度不为0的结点
树的度：树中结点的最大的度
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1
树的高度：树中结点的最大层次
森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。
相关公式
性质1：二叉树第i层上的结点数目最多为
性质2：深度为k的二叉树至多有个结点（k>=1）
性质3：包含n个结点的二叉树的高度至少为
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
证明：
假设度为1的结点数为n1，则二叉树结点总数n=n0+n1+n2,然后计算度的个数，0个儿子就有0度，1个儿子1度，2个儿子2度，度数总和，0n2+1n1+2n2，除了根节点，每个节点都有度，则n-1=0n2+1n1+2n2，得到n0=n2+1
例题
假设一棵完全二叉树共有699个结点，则在该树中叶子结点共有？
答：一棵二叉树，假设度为0的节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2，节点总数为s
从节点看，有n0+n1+n2=s
从树枝看，有0n0+1n1+2*n2=s-1
得到：n0=n2+1
完全二叉树有n1=0或1
所以完全二叉树的叶子节点个数n0=s/2向上取整或n0=(s+1)/2向下取整，得n0=350
有一个完全二叉树的叶子节点个数为1234个，那么它最多有()个节点
答：度为0的节点数：1234，度为2的节点数：1233
完全二叉树度为1的节点数不是0就是1，所以最多节点数：1234+1233+1=2468
二叉搜索树
二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
例题:
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
答：二叉搜索树中序遍历是递增的,所以我们可以中序遍历判断前一数是否小于后一个数.