树的基本概念
树
1.节点的度：一个节点含有的子树的个数称为该节点的度。
2. 树的度：一棵树中，最大的节点的度为树的度。
3. 叶子节点/终端节点：度为0的节点称为叶子节点。
4. 双亲节点/父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
5. 孩子节点/子节点：一个节点含有的子树的根节点称为该节点的子节点。
6. 根节点：没有双亲节点的节点。
7. 节点的层次：从根开始定义起，根为第一层，跟的子节点为二层，以此类推。
8. 树的高度或深度：树中节点的最大层次。
9. 非终端节点/分支节点：度不为0的节点。
10. 兄弟节点：具有相同父节点的节点互称兄弟节点。
11. 堂兄弟节点：双亲在同一层的节点。
12. 节点的祖先：从根到该节点所经分支上的所有节点。
13. 子孙：以某节点为根的子树中任一节点都成为该节点的子孙。
14. 森林：由m（m>=0）颗互不相交的树的集合称为森林。
二叉树
一、两种特殊的二叉树
1.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个 结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
2.满二叉树：如果一个二叉树的层数为k，且节点总数是（2^k）-1，则它就是满二叉树。
二、二叉树的遍历
- 先序遍历（前序）：先访问根节点，在递归遍历左子树在递归遍历右子树，访问根节点的操作发生在遍历其左右子树之前。
- 中序遍历：先递归遍历左子树，在访问根节点，在递归遍历右子树。访问根节点的操作发生在遍历其左右子树之间。
- 后序遍历：先递归遍历左子树在递归遍历右子树最后访问根节点，访问根节点的操作发生在遍历其左右子树之后。
- 层序遍历：按照每一层元素从左到右遍历即可。
二叉树的基本形态