一、树的概念：
树其实是区别于线性表，线性结构的另一种数据结构，本质是结点的有限集。树的定义有两点：1)有且仅有一个特定的称为根（root）的结点；2）当结点数量>1时，其余结点可分为若干个互不相交的有限集，其中每个集合也可以看作一颗树，称之为根的子树。
1.度（结点的分类）：
结点拥有的子树的数量是为树的度。
如上图所示，B结点的度为1，因为他只拥有根为D的一颗子树，而D的度为3，因为他拥有G、H、I 三颗只有根的子树，这就是结点的度，大家可以思考一下A结点的度是多少？
一颗树的度则是这棵树中度多的结点的度的值，上面这颗树的度则是D结点的度，为3。
2.结点之间的关系：
结点的子树的根称之为该结点的孩子（child结点）
该结点衍生出来的结点称之为该结点的父母（parent结点）
由同一个结点衍生出的同一层结点互相称之为兄弟（sibling）
由同一个结点之下的所有结点称之为子孙，例如B的子孙有D、G、H、I 结点。
3.树的层&深度：
如图所示，结点的层次从根算起，根为层，根的孩子为第二层以此类推。
一棵树的深度是树中结点层次大的值称为树的深度，或高度。
二、树的存储结构：
双亲孩子表示法：
把树种的所有结点的值依次组成一个单链表，一个结点种定义三个域，分别是数据域、父母指针域、长子（个孩子）指针域，如果这个长子有兄弟的话，则指针域指向下一个存储兄弟位置的指针域，否则就为空。
二、二叉树：
1.二叉树的定义：和树的定义类似，但是有一个特点：由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。（二叉树是递归定义）
2.二叉树的特点：1）每个结点多有两颗子树；2）左子树与右子树有顺序，即使一颗树中只有一个子树，也需要去判断是左子树还是右子树。
3.一些特殊的二叉树：1）斜树：所有结点都只有左子树或所有结点都只有右子树的二叉树称为斜树（斜树其实就是单链表！）；2）满二叉树：如果一棵二叉树的所有分支结点都存在左右子树，并且所有的叶子结点都在同一层，则称之为满二叉树；
3）完全二叉树：如果每个结点按层序编号与相同层数的满二叉树编号一致的话，则这棵树称为满二叉树。
2.二叉树的性质：
1）在二叉树的第n层上多有2^(n - 1)个结点。比如层：1个结点，第二层：2个 以此类推。
2）深度为k的二叉树至多有2^k - 1 个结点，例如图6-5-5的满二叉树有四层，结点有15个。数学归纳法可以证明。
3）一颗二叉树的叶子结点树为n，度为2的结点数量为m，则 n = m + 1；
证明过程：设一颗二叉树的所有结点为n，度为1的结点为n1，度为2的结点是n2，叶子节点为n0，则：n = n1 + n2 + n0;因为二叉树只有度为1或2的结点和叶子节点。而一颗二叉树的所有连线可以根据二叉树图像直观推出：n1 + n2 * 2 ；度为1的结点只有一条连线，度为2的结点有两条连线，而一颗二叉树的连线等于结点的数量减1，所以课可以列出式子： n1 + n2 + n0 - 1 = n1 + 2n2 可以得出性质3
4)具有n个结点的完全二叉树深度为：log2n + 1可以根据性质2推出来。
5）对于一颗结点数量为n的完全二叉树，n为树的深度，i为按树的层为结点编号，则：1.i = 1则此结点为根结点；2.若i > 2n 要么此结点的左孩子是2i，否则不存在左孩子；3.与2类似，若i结点存在右孩子，则右孩子序号为 2i + 1;
3.二叉树的存储结构（重要）：
1）顺序存储结构：将二叉树中的每一个结点按照满二叉树的层次序号进行编号，将空着的编号进行留空，将结点中的数据存入数组对应编号中，这样可以做成二叉树的顺序存储结构。
但是缺点是浪费存储空间，举个例子：斜二叉树的顺序存储结构会是怎么样的呢？
如图所示，浪费了非常多的存储空间，所以顺序存储结构只适用于完全二叉树。
2）二叉链表：
首先树结点定义与结点定义类似，但是指针域有两个，分别是lchild（左孩子）和rchild（右孩子）。如图所示：
树的定义与单链表定义有相似之处，就是必须要有根节点。
树的创造方法：（while方法，非递归）
用类似于栈的思想进行树的创建，其实和递归类似，递归也是用到栈。
4.二叉树的遍历：
众所周知二叉树的三种遍历方法：前序遍历、中序遍历、后序遍历；其实还有一种层序遍历，就是按照一层一层从左到右的顺序依次遍历树。、
1）前序遍历：
2）中序遍历：
3）后序遍历：
其实递归遍历的核心思想是理解递归，关于这一点大家可以去看一下我写的递归和栈的那篇文章，有详细的解释。
