目录

1.树的概念及其结构

1.1树的概念

 1.2树相关的概念

1.3树的表示

2.二叉树概念及其结构

2.1概念

2.2现实中的二叉树 

2.3特殊的二叉树

  2.4二叉树的性质

2.5二叉树存储结构

2.5.1链式存储

2.5.2顺序存储

3.搜索二叉树

---

1.树的概念及其结构

1.1树的概念

树是一种非线性的结构，它是由N个数据的层次结构的集合，把它叫做树就是因为它的逻辑结构就像是一颗倒过来的树，它的根向上，叶子向下。

1.有一个特殊的节点称为根节点，根结点没有前驱结点。

2.除根结点以外，其余M个结点被分为（M>0）个互不相交的集合T1,T2,T3......Tm，其中每个集合又是与结构相似的子树，每颗子树的根结点只有一个前驱，可以有0个或者多个后继。

3.树是递归定义

 

注意：树形结构中子树之间不能有交集，否则就不是树形结构。

 1.2树相关的概念

  

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

2.叶结点或终端结点：度为0的结点称为叶子结点；如上图：B，C，H，I...等节点为叶子结点

3.非终端结点或分支结点：度不为0的结点；如上图D,   E,   F,   G ...等结点为分支结点

4.双亲结点或父结点：若一个结点有子结点，这个结点就成为这个节点的双亲结点或者父结点，如上图：A是B的父亲结点。

5.孩子结点或子结点：一个结点含有子树的结点称为该结点的子结点，如上图：B是A的孩子结点

6.兄弟结点：具有相同父结点的结点互称为兄弟结点，如上图：C是B的兄弟结点 

7.树的度：一颗树种最大结点的度称为树的度，如上图：树的度为6

8.结点的层次：从根开始，根为第一层，根的子结点为第二层，一次类推

9.树的高度或深度：树的结点的最大层次，如上图：树的高度为4

10.堂兄弟结点：双亲在同一层的结点互为堂兄弟结点，如上图：H,  I互为兄弟结点

11.结点的祖先：从根到该结点的所经分支上的所有结点；如上图所示：所有结点都是A的子孙

12.森林：有m（m>0）颗互不相交的树的集合称为森林

1.3树的表示

树的结构相比与线性结构就比较复杂了，要储存起来就比较麻烦了，既然保存值域，也要保存结点与结点之间的关系，实际树的很多种表示方式如：双亲表示法，孩子表示法，孩子双亲表示法以及孩子兄弟表示法，我们这里就了解最简单的孩子兄弟表示法。

typedef int DataType;
struct Node
{
   struct Node* firstchild;    //第一个孩子结点
   struct Node* pnextbrother;  //下一个兄弟结点
   DataType _Data;             //该结点储存数据

}

 

2.二叉树概念及其结构

2.1概念

一棵二叉树是节点的一个有限集合，该集合：

1.或者为空

2.由一个根结点加上两个别称为左子树和右子树的二叉树组成

从上图可以看出：

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

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

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

2.2现实中的二叉树 

2.3特殊的二叉树

1.满二叉树：一个二叉树，如果每一层节点数都达到了最大值，则这个二叉树就是满二叉树。也就是说一个二叉树的层数为K，总结点的个数是，则它是满二叉树。

2.完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树引出来的，对于深度为K的，有n个结点的二叉树，当且仅当每一个结点都与深度为K的满二叉树中编号从1至n的结点----对应时称为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

  2.4二叉树的性质

1.若规定根节点的层数是1，则一棵非空二叉树的第i层上最多有个结点。

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

3.对任何一个二叉树，如果度为0其叶结点个数为,度为二的结点分支个数为，则有。

3.若对规定根节点的层数是1，具有n个结点的满二叉树的深度。

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

       1.若i>0，i位置结点的双亲序号：，i=0，i为根节点编号，无双亲结点

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

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

2.5二叉树存储结构

想要实现二叉树的存储的话可以用到前面所学到两种存储方法链式存储和顺序存储 。

2.5.1链式存储

我们对每个结点设立两个指针一个左孩子一个右孩子同时存储数据。

typedife int DataNode

struct Node
{ 
     struct Node *lifechild;
     struct Node *rightchild; 
     DataNode val;
}

我们还有三叉链的结构会出现多一个指针指向双亲结点 。

typedife int DataNode

struct Node
{ 
     struct Node *lifechild;
     struct Node *rightchild; 
     struct Node*parent;
     DataNode val;
}

结合下面图片来看可以跟好的理解逻辑结构。  

2.5.2顺序存储

我们可以运用到前面的2.4中的第四点的结论，我们可以利用他们在顺序表中的编号来确定它们相互之间的关系，结构上是一个数组实际逻辑上是一个二叉树。

3.搜索二叉树

搜索二叉树是一种特殊的二叉树，它的特点在于每一个结点的左结点总是小于右结点且右子树大于它的双亲结点。这里只是简单说一下不做多余的讲解。

它的结构如下图所示：