1.树的概念
学二叉树之前得先学树，后面也有能用到树的知识，比如并查集就是树当中的森林
1-1树的概念
树是一种非线性的数据结构，它是由N（N>=0）个有限结点组成的层次关系的集合，说它是树主要是因为他很像一棵倒挂的树，也就是根在是上，枝叶在下。
A为根结点，根节点没有前驱结点
树是递归定义的，树中最基本的关系就是父子关系，A是B和C的父节点，同时B也是D的父节点。（任何一棵树都可以分为根和子树）
上面两个图都不是树，因为树内部不能出现环，出现环就是我们后面要讲的图
1-2.树中的亲缘关系名词
结点的度：一个结点所含子树的个数，比如结点A的度为2
叶子结点或终端结点：度为0的结点，比如结点D，G和E
分支结点或非终端结点：度不为0的结点，比如结点A,B和C
父节点或双亲结点：若一个结点有子节点，那么这个结点就被称为父节点，比如A是B和C的父节点
子节点或孩子结点：同理，比如B和C是A的子节点
兄弟节点：具有相同父节点的结点，比如B和C是兄弟结点（亲兄弟）
堂兄弟结点：父节点都在同一层的结点，比如D和G,E
树的度：一棵树中，最大的结点的度被称为树的度，比如该树的结点是2
结点的层次：从根开始定义，如果规定根为第一层，以此类推（推荐）
备注：如果规定根为第0层，以此类推也行，但数组从0开始时因为偏移量，这里没必要
而且如果一个如果要表示空树，显然规定根为第一层，更能合乎情理表示空树
结点的祖先：从根到该节点的经过分支的所有结点，比如G的祖先是A和C
结点的子孙：以某一个结点为根的子树中的任意一个结点，比如C的子孙是G和E
森林：由m(m>0)棵互不相交的树的集合
2.树的存储方式
2-1兄弟孩子表示法
不那么合适的写法：
由于我们不知道树的结点的度为多少，所以在树的结点定义的时候直接定义有点麻烦
//一：结点的度不知道，我怎么设计呐？ struct TreeNode { int data; struct TreeNode* childNode1; struct TreeNode* childNode2; struct TreeNode* childNode3; //... }; //二：如果明确树的度 //静态顺序表： #define N 5 struct TreeNode { int data; struct TreeNode* childArr[N]; int childSize; }; //缺点：但是这是树的度，不是每一个结点的度，会造成数组空间浪费 //三：动态顺序表： struct TreeNode { int data; struct TreeNode** childArr; int childSize; };
最合适的写法：
兄弟孩子表示法
typedef int DataType; struct TreeNode { struct TreeNode* firstchild1;//第一个孩子结点 struct TreeNode* pNextBrother;//指向第一个兄弟结点 DataType _data; };
Linux目录系统结构：（树）
2-2双亲表示法
任意一个结点找祖先
3.满二叉树和完全二叉树
二叉树：度为2的树；二叉树的结点的度只能为0或者2
任何二叉树都是由以下结构复合而成的
特殊的二叉树：
- 满二叉树：每一层都是满的，
如果有K层，第K层结点个数：2^(K-1) ; 总结点个数：2^k-1 - 完全二叉树：如果有K层，则前K-1层必须是 满的，最后一层满或不满都可以
K层，结点数量范围是【2^(K-1),2^K-1】
4.二叉树的性质
性质1：在二叉树的第i层上至多有2^(i-1)个结点（数学归纳法或者错位相减法证明）
性质2：深度为i的二叉树至多有2^i-1个结点 （数学归纳法或者错位相减法证明）
性质3：对于任意一棵二叉树，若叶子数为n0,度为2的结点有n2,则n0=n2+1（数学归纳法）
性质4：具有n个结点的完全二叉树必为LogN+1（数学推导证明如下）
