树的定义 树（tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中必须满足以下两个特点：（1）有且仅有一个特定的称为根（ROOT）的结点；（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并称之为根的子树。
树的相关概念
结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点或者终端结点；度不为0的结点称为非终端结点或者分支结点。除了根节点外，分支结点也称为内部结点。树的度就是结点度的最大值。 结点子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲，同一双亲的孩子互称为兄弟，结点的祖先是从根到该结点所经分支上的所有结点。以某一结点为根的子树中任一结点都称为该结点的子孙。 结点的层次是从根结点开始为第一层，根的孩子为第二层。双亲在同一层的结点互称为堂兄弟。树的结点的最大层次称为树的深度。
树的存储结构 双亲表示法，孩子表示法，孩子兄弟表示法 着重介绍一下孩子兄弟表示法：对于任意一棵树，他的结点的第一个孩子如果存在就是唯一的，他的兄弟如果存在就是唯一的。因此我们设置两个指针，分别该结点的第一个孩子和右兄弟。 对于上图的树，我们可以表示为： 这个就叫大名鼎鼎的二叉树。
二叉树 定义：是n(n>=0)个结点的有限集合，该集合可以为空集合，称为空二叉树，或者又一个根结点和两个互不相交的，分别称为根结点的左子树和右右子树的二叉树组成。 特点：（1）每个结点最多两个子树；（2）左子树和右子树都是有次序的。（3）即使只有一棵子树，也要区分它是左子树还是右子树。 分类： （1）斜树：所有结点都偏向一侧
（2）满二叉树：在一棵二叉树里，所有分支结点都存在左子树和右子树，且叶子结点都在同一层上 （3）完全二叉树：对一棵具有n个结点的二叉树按层数编号，如果所有结点的编号都和满二叉树的编号相等，那么称为完全二叉树 完全二叉树的几个特点：a：叶子结点只可能出现在最后两层b：最后一层的叶子结点一定集中在左部连续的位置，而倒数第二层如果有叶子结点那么一定都在右部连续的位置。c：如果结点的度为1，则该结点只有左孩子，即不存在只有右子树的情况，d:同样结点树的二叉树，完全二叉树的深度最小。
二叉树的性质 **性质一：**二叉树的第i层最多有 2 i − 1 2^{i-1} 2i−1 **性质二：**深度为k的二叉树最多有 2 k − 1 2^{k}-1 2k−1个结点 **性质三：**对于任意一棵二叉树，叶子结点（度为0）个数为n0，度为1的结点个数为n1，度为2的结点个数为n2.则有n0 = n2+1。 **性质四：**具有n个结点的完全二叉树的深度为log2n+1向下取整
二叉树的存储结构 顺序存储结构： **二叉链表：**二叉树每个结点最多有两个孩子，设计一个数据域和两个指针域。
遍历二叉树 **定义：**指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使每个结点被访问一次且仅被访问一次。 二叉树遍历方法: a.前序遍历 结果：abdghceif 规则：若二叉树为空，则空操作返回，否则先访问根结点，在前序遍历左子树的左孩子，没有左孩子则打印右孩子，继续找右孩子的左孩子，依次类推 b.中序遍历（左根右）
结果：cdhbaecf 规则：若二叉树为空，则空操作返回，否则从左子树开始，一层一层没有左孩子就打印输出该双亲结点，然后判断右孩子。右子树的情况一样。 c.后序遍历(左右根)：
结果：ghdbiefca 规则：若二叉树为空，则空操作返回，否则先寻找左孩子，找到没有左孩子的那个结点，在看他有没有兄弟，接着返回他的双亲，根结点最后输出。 练习题 a.假如前序abcdef，中序cbaedf 那么该树的后序结果是多少？ 解答：前序的第一个为根节点a，可知后序的最后一个为a。 然后根据中序可知cd为左子树，edf为右子树。 首先看左子树前序为bc中序为cb，则说明b是c的双亲，且c为b的左孩子，所有后序为cb。 再看右子树，前序为def，中序为edf，可以从前序看出d是双亲结点，至于ef由中序edf可以看出为兄弟结点，且e为左兄弟，f为右兄弟。 综上所示，后序遍历为cdefda。 b.假如某树的中序为abcdefg，后序为bdcafge，那么它的前序结果为多少？ 解答：首先找根结点，后序的末尾e，那么根结点为e，根据中序可知abcd为左数，fg为右子树。 我们先来看左子树，中序abcd，后序bdca，可知a为根结点的左孩子，根据后序可知c为a的右孩子，d为c的右孩子，那么根据中序可知b为c的左孩子，所以前序目前为eacbd。 再看右子树，中序为fg，后序为fg，根据后序g为e的右孩子，那么可知f为g左孩子。那么前序为eacbdgf。 **注意：**已知条件必须要有中序，不然结果不唯一。
线索二叉树 树，森林和二叉树 树到二叉树： 加线（把所有兄弟之间连起来）——>去线（除了与第一个孩子的线，其他孩子的都去掉）——>层次调整（顺时针旋转一下） 二叉树到树： 加线（把所有的右孩子和亲人连起来）——>去线（去掉所有二叉树与其右孩子的连线）——>层次调整 二叉树到森林 从根开始，把右结点的线去掉，直到变为若干二叉树