树的概念
- 有一个特殊的节点，称为根节点
- 子树之间不能有联系
- 每个节点有且仅有一个父节点
- 一棵 n 个节点的树由 n - 1 条边
节点的度： 一个节点含有的子树的个数为该节点的度
如图： A 的度为 3
叶节点或终端节点： 度为 0 的节点
如图： J、K、L、H、I都是叶节点
非终端节点或分支节点： 度不为 0 的节点
如图： E、G、D 等都是分支节点
双亲节点或父节点： 若一个节点有子节点，则这个节点称为其子节点的父节点
如图： E 是 J 的父节点
孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点
如图： J 是 E 的子节点
兄弟节点： 具有相同父节点的节点互称为兄弟节点
如图： E 和 F 是兄弟节点
树的度： 一颗树中最大的节点的度称为树的度
如图： 树的度为 3
树的层次： 从根开始，根节点为第一层，根的子节点为第二层，依次类推
树的高度或深度： 树中节点的最大高度
如图： 树的高度为 4
堂兄弟节点： 双亲在同一层的节点为堂兄弟节点
如图： F 和 G 为堂兄弟节点
祖先节点： 从根到该节点所经分支的所有节点
如图： G 的祖先节点为 C、A
子孙： 以某节点为根的子树中任意节点都称为该节点的子孙
如图： B 的子孙为 E、F、J
森林： 由 m 颗互补相交的树的集合叫森林 （并查集）
树是递归定义的，任何一颗树都包含根和 n 棵子树
例如 A 由B、C、D三棵子树构成，B由E、F两棵子树构成，E由J一棵子树构成，此时J已经是叶节点，不可再拆
树的定义
1. 明确了树的度为 N
#define N 4
struct TreeNode{int val;struct TreeNode* subs[N];
}2. 没有明确树的度（顺序表）
struct TreeNode{int val;SeqList subs; //顺序表中存入 struct TreeNode*
}3. 左孩子右兄弟(高手设计的结构）
struct TreeNode{int val;struct TreeNode* leftchild;struct TreeNode* rightbrother;
}无论一个父亲节点由几个孩子，child 指向左边开始的第一个孩子,brother 则为 child 的亲兄弟
我们可以认为，windows 下面的文件系统就是个森林，C盘就是一棵树，D盘也是一棵树……
二叉树的概念
- 或者为空
- 有一个根节点加上两棵别成为左子树和右子树的二叉树
满二叉树： 一个二叉树，每一层节点数都达到了最大，若层数为 h ，则一共有 2^h - 1 个节点。
完全二叉树： 一个二叉树，前 h - 1 层是满的，最后一层不满，但从左到右是连续的
二叉树的存储方式
1. 顺序存储
我们可以用数组来存储满二叉树或完全二叉树中的数据，二叉树的逻辑结构是想象出来的，物理结构则是内存中实实在在存储的
用数组来存储的好处是可以用下标来寻找父子关系
假设一个父节点的下标是 i ，那左孩子节点的下标是 2 * i + 1，右孩子节点的下标是 2 * i + 2
假设一个子节点的下标是 j ，那父节点的下标是 (j - 1) / 2 。不用担心是左孩子还是右孩子，除法有取整的机制
但是使用数组只适用于满二叉树或完全二叉树，其他一般二叉树就必须把相应没有的位置空出来，但是不太方便，存在很多的空间浪费
未完待续……（接下来将介绍一种二叉树，堆）
