1.基本概念
树是n个结点的有限集合，是一组由边相连的结点的元素组织结构。
树结构示意图：
结点的度：一个结点的子树的个数记为该结点的度；如A结点的度为3,B结点的度为2
树的度：结点树的度数最大的值为树的度，如上图的树的度为2，因为B结点的度为2，是这颗树最大的结点度
叶子结点：没有下一级相关联的结点为叶子结点，如E,F,C,G
分支结点：非叶子结点为分支结点，包括根结点
内部结点：除根结点外，分支结点为内部结点
2.二叉树
二叉树每个结点最多只能有两个子树，称为左子树和右子树
示意：
满二叉树：非叶子结点恰好有两个子结点
完全二叉树：除最后一层恰好有两个子结点，最后一层结点从左到右填充
结点数n与高度h关系如下：
n=2^h-1
2^h = n + 1
叶子节点数n0,度数为2的结点数n2之间的关系：
n0 = n2 + 1
3.树的遍历
注：遍历一个结点但是在那个时刻并不访问它。
遍历二叉树：
二叉树的遍历方法：
* 访问根
* 访问根的左子树中的所有结点
* 访问根的右子树中的所有结点
前序遍历：访问根的子树之前访问根，然后访问根的左子树中的所有结点，再访问根的右子树中的所有结点
* 访问根的左子树中的所有结点
* 访问根
* 访问根的右子树中的所有结点
中序遍历：递归访问左子树中的结点，首先访问最左叶子结点，接下来访问该叶子结点的根结点，然后访问其右子结点
* 访问根的左子树中的所有结点
* 访问根的右子树中的所有结点
* 访问根
后序遍历：递归访问左子树的结点，首先访问最左叶子结点，然后访问该叶子结点的兄弟结点，再然后访问其父结点
层序遍历：从根结点开始，每次访问一层中的结点，同一层中，从左到右访问结点
前序遍历结果：A，B，C，E，F，D，G，H，I，J，K
中序遍历结果：E，C，F，B，D，A，H,G,J,I,K
后序遍历结果：E，F，C，D，B，H，J，K，I，G，A
层序遍历结果：A，B，G，C，D，H，I，E，F，J，K