数据结构 【二叉树（上）】

        谈到二叉树，先来谈谈树的概念。

1、树的概念及结构

        树是一种非线性的数据结构，它的逻辑关系看起来像是一棵倒着的树，也就是说它是根在上，而叶子在下的，

        在树这种数据结构中，最顶端的结点称为根结点。在树的使用过程中，由于树的逻辑关系很像人的遗传关系图谱，所以，一般将上一级的结点称为下一级结点的父结点，某一层级结点往上的结点称为该层结点的祖先。这里要注意的一点是：树形结构中，子树之间不能有交集，否则就不是树形结构。

1.1、树的相关概念

结点的度： 一个结点含有的子树的个数就称为该结点的度；如上图：A的度为6；

叶结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等结点为叶结点；

分支结点：度不为0的结点称为分支结点； 如上图：D、E、F、G...等结点为分支结点；

父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点；

子结点：若有一个结点有父结点，则这个结点称为其父结点的子节点；如上图：B是A的子结点；

兄弟结点：处于同一层级的结点称为兄弟节点；

树的度：一棵树中，最大结点的度称为树的度；如上图：树的度为6；

结点的层次：从根开始定义，根为第1层，根的子结点为第2层，以此类推；

树的高度：树中结点的最大层次；如上图：树的高度为4；

堂兄弟结点：双亲结点在同一层级的结点称为堂兄弟结点；如上图：H、I互为堂兄弟结点；

结点的祖先： 从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先；

子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙；

森林：由m（m>0）棵互不相交的树的集合称为森林；

1.2、树的表示

        树的表示就比较复杂了，既要保存结点中要存储的数据，也要保存结点之间的相互关系。众多树的表示方法中，左孩子右兄弟表示法是最常用的方法。它的逻辑关系可以表示成下面的形式：

typedef int DataType;
struct Node
{struct Node* firstChild1;    // 第一个孩子结点struct Node* pNextBrother;   // 指向其下一个兄弟结点DataType data;               // 结点中的数据域
};

2、二叉树

2.1、概念

        一棵二叉树是结点的有限集合，该集合：1.或者为空，2.由一个根节点加上两颗别称为左子树和右子树的二叉树组成，

        从上图可以看出：

        1.二叉树不存在度大于2的结点

        2.二叉树的子树有左右之分，次序不能颠倒，因此，二叉树是有序树。

对于任意的二叉树都是由以下几种情况符合而成的：

2.2、特殊的二叉树 

        1、满二叉树：一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为h，且结点数总是2^(h-1)，那么它就是满二叉树。

        2、完全二叉树：完全二叉树是效率很高的数据结构，对于高度为h的二叉树，它的h-1层的结点全满，第h层的结点是连续的情况下称为完全二叉树。要注意：满二叉树也是一种特殊的完全二叉树。

2.3、二叉树的性质 

1、若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。

2、若规定根节点的层数为1，则深度为h的二叉树的最大结点树最大的结点数为2^h-1。

3、对于任何一颗二叉树，如果度为0其结点个数为n0，度为2的分支结点个数为n2,则有n0=n2+1。

4、若规定根结点的层数为1，具有n个节点的满二叉树的深度h=log(n+1),以2为底。

5、对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组对所有结点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子

3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

3、二叉树的顺序结构及实现

3.1、二叉树的顺序结构

        普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2、堆 

        在二叉树的概念上限制一些条件就是堆。堆有两条性质：1.堆中某个结点的值总是大于或者不小于其父结点的值。2.堆总是一棵完全二叉树。

         堆的实现我将单独写一篇博客来实现。