目录

开场白     

树的定义

结点的分类

结点间的关系

树的其他相关概念

树的存储结构

孩子兄弟表示法

二叉树的定义

 二叉树的特点

特殊二叉树

满二叉树

完全二叉树

二叉树的性质

二叉树的存储结构

---

开场白     

  这一篇文章是关于树的知识，这是一个比较特殊的结构。下面就让我们拿出百分之一百二的精神来学习吧。

        首先，让我们来看一看下面这幅图。

        我们可以看到，左边这颗就是树，只不过它是倒着的，根再上面，叶子在下面。再看看右边，就是我们抽象出来的树型结构，最上面的也是根，最下面的就是我们的叶子。

        无论多高多大的树，那也是从小到大，由根到叶，一点点成长起来的。俗话说“十年树木，百年树人”，可一颗大树又何止是十年这样容易的——哈哈，说到哪里去了，我们现在不是在上生物课，而是要讲一种新的数据结构——树。

树的定义

        之前我们讲的顺序表，链表，这些都是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要学习并研究一种一对多的数据结构——“树”，考虑它的特点以及特性，来解决我们生活中的一些问题。

        树（Tree）是n（n>=0）个结点的有限集。n=0的时候是空树。在任意一颗非空树中：1:有且仅有一个特定的称为根的结点；2：当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3~~~Tm,其中每一个集合本身又是一颗树，并且称为根的子树。

        树的定义其实就是我们再讲栈时提到的递归方法。

结点的分类

        树的结点包含一个数据和它的分支，就是它不仅储存了数据，还储存了和它有关系的结点的地址。结点拥有的子树称为结点的度。度为零的节点称为叶子结点或者终端结点；度不为零的节点称为非终端结点。树的度是树内各个结点的最大的度。

我们来看一看上图，首先A是根节点，它有3个子树分别为B1,B2,B3所以说它的度就是3，然后B1的分支有两条所以它的度为2，同理B2的度为1，D3的度为0，这里我们就不在全部都说了。所以说这里面的最大的度为3，这整颗树的度就为3。

结点间的关系

        结点的子树的根称为结点的孩子，相应的，该节点称为孩子的双亲。  我们还是从上图来举例说明，A就是B1，B2,B3 的双亲，所以B1,B2,B3就是A的孩子，同理B2是C3的父亲，C3是B2的孩子。

        同一个双亲的孩子称为兄弟。结点的祖先就是从根到该节点路径上的所有节点。  可以看到B1,B2,B3的父亲都是A，所以说他们都是兄弟，这也和我们人类的亲缘关系一样。D2的祖先就是从A到它自己的上的所有节点，所以C1,B1,A都是它的祖先。其它的我就不一一举例了，大家其实也很好理解。

        以某节点为根的子树的仍和一个结点都称为该结点的子孙。这个很好理解，因为有了根才有叶子。    

树的其他相关概念

        结点的层次从根开始定义起，根为第一层，根的孩子为第二层。比如某个结点在地N层，则它的孩子就在N+1层。其双亲在同一层的节点互为堂兄弟，就和我们人类的辈分关系一样，辈分相同但又不是亲兄妹的称为堂兄弟。树中结点的最大层次称为树的深度或高度。

树的存储结构

        说到存储结构，在我们学习树型结构之前，我们就已经学习了顺序存储和链式存储两种结构了。

        先来看看顺序存储结构，用一段地址连续的存储单元一次存储线性表的数据元素。这对于线性表来说是很自然的，对于树这样的结构呢？

        树中的某个节点的孩子可能有多个，而且每个节点的孩子的数量也不相同，如果说我们以最大的度的节点来开辟内存空间的话，这样对内存的消耗就很大很大了，如果是后面我们要学习的二叉树还好，如果遇到一些度很大的树的节点，这些方法就不太好，我们尽量还是要做到有多少我们用多少的存储空间。

        不过充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。我们要了解的有三种方法：双亲表示法，孩子表示法，孩子兄弟表示法。

        下面我们重要讲述孩子兄弟表示法，这个比较好理解。

孩子兄弟表示法

        我们观察一颗树可以发现，任意一棵树，只要它的结点的第一个孩子存在的话就是唯一的，它的兄弟存在的话也是唯一的。所以我们可以定义一个孩子指针指向它的第一个孩子，定义一个兄弟指针指向它右边的第一个兄弟。就像下面这样。

struct TreeNode
{
    datatype val;
    struct TreeNode* child
    struct TreeNode* brother;
}

      

        对于上图的左边这颗树来说，它的表示方法就是右边这种。首先我们可以看到A它只有孩子，没有兄弟则它的孩子节点就指向了左边第一个孩子B，它没有兄弟，兄弟节点就指向空；再来看B，它的孩子节点指向了第一个孩子D，它的兄弟节点指向了C，接下来就是重复的内容了，C的第一个孩子又是E，兄弟指针指向了空~~~ 这样直到J 就完全把整颗树表示出来了。

        其实这个表示方法其实还是有缺陷的，它只能通过双亲结点找到孩子和兄弟，但是无法找到它自己的双亲。其实解决这个方法也很简单，我们只需要再增加一个双亲指针就行了。这个方法就把一颗比较复杂的树表示成了一颗二叉树的形式，这时肯定你不知道二叉树是什么，没关系，下面就让我们来学习一下树的重点内容——二叉树。

二叉树的定义

        二叉树是我们学习数据结构中很重要的一个知识点。它的结构比较特殊，我们先来看一看图片。

       我们可以看到上面这幅图，它的度为2，我们仔细观察，它的每一个节点的度都小于或等于2。我们把这种树就叫做二叉树。

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

 二叉树的特点

 二叉树的特点有：

1.每个节点最多有两颗子树，所以二叉树中不存在度大于2的节点。注意不是只有两个子树，而是最多只有两颗子树。没有子树或者一颗子树也是可以的。

2.左子树和右子树，也要区分它是左子树还是右子树。就像人的双手和双脚，但显然左手和右手，左脚和右脚是不一样的，左手带左手套，右手带右手套，对你的生活影响是完全不同的。

可以看到上面这两颗树是完全不同的。因为二叉树是要区分左右的，对于图一来说3是2的右子树，而图二却相反，3是2的左子树。

特殊二叉树

满二叉树

在一颗二叉树中，如果所有分支节点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的树就叫做满二叉树。

像这样只有最后一层存在叶子结点，其它的节点都存在左右节点的特殊树形结构就是满二叉树，从样子上看就感觉它很完美。

单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这样做到了整棵树的平衡。因此，二叉树的特点有：

1.叶子节点只能出现在最下层，出现在其他层就不可能达到平衡。

2.非叶子节点的度一定是2。

3.在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

 对一颗具有n个结点的二叉树按层序编号，如果编号i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。

这样听起来好像不太好理解，这样我们先来看一看它长什么样子。

观察一下，上面这个完全二叉树有4层，它的前三层就是一颗满二叉树，然后最后一层的叶子节点必须是连续的，中间不能有空的部分。

 像上面这棵树，它的前三层是满二叉树，但是在第四层，5节点的左子树就不存在，导致9和B中介空了出来，所以说上面这颗树就不是满二叉树。

首先从字面上要区分，“完全”和“满”的差异，满二叉树一定是一颗完全二叉树，但完全二叉树不一定是满二叉树。我们一定要理解清楚这句话。

我们再这里也可以总结一下二叉树的特点：

1.叶子结点只能出现在最下两层。

2.最下层的叶子一定集中在左部连续位置。

3.倒数第二层，若有叶子结点，一定都在右部位置。

4.如果节点度为1，则该结点只有左孩子，即不存在右子树的情况。

5.同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

性质1：二叉树的第i层至多有2^(i-1)个结点。

比如：第一层为 2^0=1个；第二层2^1=2个；第三层2^3=3个~~~；通过数学归纳法的论证，可以得出二叉树的第i层有至多有2^(i-1)个结点。

性质2：深度为K的二叉树最多有2^k-1个结点（k>=1）。

记住这里是2^k-1，不是2^(k-1)。这里容易混淆，因为这里是算的总结点的个数，就需要用到等比数列的求和公式，简单推导一下就出来了，这里我们就不去推导了。

性质3：对于任何一颗二叉树T，如果终端结点数n0(叶子节点），度为2的节点数为n2，则n0=n2+1;

这个性质是非常重要的，希望大家都能够记住，如果记不住其实我们就画一颗简单的满二叉树或者完全二叉树就可以找到它们的关系了。

这里讲的3个性质都是比较常用的，希望同学们能够记下来。

二叉树的存储结构

二叉树我们一般都选择链式存储结构，二叉树每个结点最多有两个孩子，所以为他设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表。

struct TreeNode
{
    datatype val;
    struct TreeNode* child
    struct TreeNode* brother;
}

我们前面也说了，如果有需要，我们还可以增加一个指向双亲的指针。

遍历二叉树

二叉树的遍历主要要用到递归，所以这里的内容需要对递归有一定的理解能力。

遍历二叉树的方法有3中，分别是前序，中序，后序遍历。

我们这里指讲讲前序遍历，中序和后序其实也和前序遍历差不多，只要弄懂前序遍历，其它两个就不是问题。

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，在前序遍历右子树。具体代码如下。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{	

    //如果该节点是空，打印# 再返回
	if (root == NULL)
	{
		printf("# ");
		return;
	}
    //不是空，打印数据域
	printf("%c ", root->data);
    //然后遍历左子树
	BinaryTreePrevOrder(root->left);
    //遍历右子树
	BinaryTreePrevOrder(root->right);
}

中序遍历

规则是若二叉树为空，则空操作返回，从根节点开始，先访问根节点的左子树，再访问根节点，最后访问右子树。

后序遍历

规则是若二叉树为空，则空操作返回，从根节点开始，先访问根节点的左子树，再访问根节点的右子树，最后再访问根节点。

下面的代码就留给同学们自己去写了。后面还有稍难的层序遍历还需要用到队列的知识，我们后面再讲。

总结

        终于到了总结的时间，树这一块的内容，相对于前面的队列和栈就比较复杂了。我们这里也只学习了一些树和二叉树的基本性质和概念。需要学懂树型结构还需要很长的一段路要走。开头我们提到了树的定义，降到了递归子啊树中的应用。提到了子树，结点，度，叶子，分支节点，双亲，孩子，兄弟，深度，层次等等。这些都是需要我们去理解记忆的。

        遍历是二叉树最重要的部分，前序，中序，后序以及层序遍历（这里没有讲）都是需要熟练掌握的知识。要让自己学会用递归去实现它们的代码。这样可以加深我们对递归的理解。

        好了，关于树和二叉树的一些基本知识我们就讲到这里，如果有哪里不正确的地方还请大家指出。