树是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：

（1）有且仅有一个特定的称为根的结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、......、Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

一、树的定义

树是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：
（1）有且仅有一个特定的称为根的结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、......、Tm，其中每一个集合本身又是一棵树，并且称为根的子树。
如图所示：

关于树：

（1）n>0时根结点是唯一的，不可能存在多个根结点。
（2）m>0时，子树的个数没有限制，但是它们一定是互不相交的，下图所示的就不符合数的定义，因为它们都有相交的子树。

二、树的存储结构

1.双亲表示法

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲结点在数组中的位置。

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。

这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所以用的时间复杂度为O(1)，知道parent为-1时，表示找到了树结点的根。可是如果要知道结点的孩子是什么，得遍历整个结构才行。

改进：

增加一个结点最左边孩子的域，叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如图所示：

对于有0个或1个孩子结点来说，这样就解决了找结点孩子的问题了。甚至是两个孩子，知道了长子是谁，另一个当然就是次子了。

再改进：

可以增加一个右兄弟域来体现兄弟关系，也就是说，每个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1，如下图所示：

总结：

存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结构。

2.孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如下图所示：

3.孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

三、二叉树的定义

二叉树是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点：

（1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
（2）左子树和右子树是有顺序的，次序不能任意颠倒。
（3）即使树中某结点只有一棵子树，也要区别它是左子树还是右子树。

二叉树具有五种基本形态：

（1）空二叉树。
（2）只有一个根结点。
（3）根结点只有右子树。
（4）根结点既有左子树又有右子树。

特殊二叉树：

1.斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。

2.满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点：
（1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
（2）非叶子结点的度一定是2。
（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3.完全二叉树

对一个具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
完全二叉树的特点：
（1）叶子结点只能出现在最下两层。
（2）最下层的叶子一定集中在左部连续位置。
（3）倒数两层，若有叶子结点，一定都在右部连续位置。
（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
（5）同样结点数的二叉树，完全二叉树的深度最小。

满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

四、二叉树的存储结构

二叉树的顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，不如双亲与孩子的关系，左右兄弟的关系等。
满二叉树的顺序存储：

将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如图所示：

二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域。称这样的链表叫做二叉链表。

其中，data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表。

五、遍历二叉树

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

1.前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。遍历的顺序为：ABDGHCEIF。

2.中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。遍历的顺序为：GDHBAEICF。

3.后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。遍历的顺序为：GHDBIEFCA。

4.层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。遍历的顺序为：ABCDEFGHIJ。

学习是一个慢慢积累的过程，也是一件很快乐的事，这种快乐来自于你的思考。完成一项学习任务固然重要，但更重要的是在完成的过程中学到了什么，掌握了什么，遇到一些什么问题，为什么会出现这种问题，根源是什么，都有哪些解决方案，什么样的情况适合这个方案。只有在不断的思考，你的能力才会有所提升！