一.概念
1.结点的度：⼀个结点含有⼦树的个数称为该结点的度；
2.树的度：⼀棵树中，所有结点度的最⼤值称为树的度；
3.叶⼦结点或终端结点：度为0的结点称为叶结点；
4.双亲结点或⽗结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；
5.孩⼦结点或⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点
6.根结点：⼀棵树中，没有双亲结点的结点；
7.结点的层次：从根开始定义起，根为第1层，根的⼦结点为第2层，以此类推
8.树的⾼度或深度：树中结点的最⼤层次；
二.二叉树
1.概念
树的度为2的，⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树
2.两种特殊的二叉树
满二叉树：一颗二叉树如果每层的结点数都达到最⼤值，则这棵⼆叉树就是满⼆叉树。
也就是说，如果⼀棵⼆叉树的层数为K，且结点总数是 ，则它就是满⼆叉树。
完全二叉树：完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点⼀ 对应时称之为完全⼆叉树。 要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
3.二叉树的性质
1.若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i - 1)(i>0)个结点
2. 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点总数是((2 ^ k) - 1)(k>=0)
3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0＝n2＋1 (度为0的结点比度为2的结点多一个)
4. 具有n个结点的完全⼆叉树的深度k为log(n + 1)上取整
5. 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点
若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦
若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦
4. 二叉树的遍历
1.前序遍历：根结点 --> 左子树 --> 右子树
2.中序遍历：左子树 --> 根结点 --> 右子树
3.后序遍历：左子树 --> 右子树 --> 根结点
4.层序遍历：从上到下从左到右依次遍历