树与二叉树

树的定义：
树是n（n>=0）个结点的有限集合T。
              （1）n=0时，T为空树。
                （2）n=1时，T只有一个根结点。
                （3）n>1时，此时T剩下的结点都互不相交，且结点构成的Ti为T的子树。
图片说明
如图A为此树的根，剔除A后B所在的树和C所在的树即为A的子树。(图中的6个结点)
度的定义：
（1）结点的度：即结点的子树的数量。上图A的度为2（有B,C两个结点）C的度为1（只有F一个结点）。
（2）树的度：上述结点的度中取最大值。上图树的度为2，若B再增加一个子结点G，则B的度为3，树的结点也变成3。(如下图)

（3）n度树：度为n的树。上图即为度为3的树。
（4）叶子结点：没有子树的结点（度为0）。上述叶子结点为：D E G F
（5）分支结点：度不为0的结点。上述分支结点为：B C
（6）双亲结点：上图中A是B,C的双亲，B,C是A的孩子。
（7）结点的层：规定根节点的层数为1，其他结点的层数为其双亲结点的层数加1。上图中结点A的层数为1。结点B的层数为1+1=2，结点G的层数为2+1=3。
（8）树的深度：树中各结点的层数的最大值，如上图中树的深度即为3，如果F还拥有一个子结点H（如图）则此树的深度即为H的层数3+1=4.
图片说明
（9）兄弟结点，堂兄弟结点，祖先结点：
1、兄弟结点：有相同双亲的结点如：D E G有相同的双亲B，所以他们三个互为兄弟结点。
2。堂兄弟结点：有不同的双亲，但其各自双亲是兄弟结点。如：D E G F有不同的双亲但B C为兄弟结点所以D E G 与F为堂兄弟结点。
3、祖先结点：从根节点到某一结点所经历的所有结点皆为此结点的祖先结点。如：从A到H其间所经历了A C F三个结点所以A C F 都为H的祖先结点。
（10）有序树，无序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树，否则称为无序树。
图片说明
如图，当规定T1与T2为有序树时，T1与T2分别是两棵不同的树。当T1与T2为无序树时，T1与T2两棵树表示的一个相同的树。
（11）森林：m（m>=0）棵树的集合（这些树不互相交集）

T1与T2组成一个森林，F={T1,T2}.

树结构的特点：
与线性结构相比：
线性结构——第一个数据（无前驱）——最后一个数据（无后继）——其他数据（分别有一个前驱和一个后继）
树结构———根节点（无前驱）————各个叶子结点（无后继）——分支结点（有一个前驱，有一个或者多个后继）

二叉树
定义：是由n（n>=0）个结点的有限集，此集可能是空树即（n=0）或者是由根节点和互不相交的左右子树构成的二叉树。
特点：
（1）二叉树的每个结点都至多有两个子树（有可能左右子树缺一个或者都缺）。
（2）每个结点的左右子树是按照顺序排列的（有左右之分）不可调换位置。
以下是二叉树的五种基本形态：
图片说明
二叉树与2度树的比较：

图中T1是度数为1的二叉树，T2是1度树，T3是度数为2的二叉树。
提问：三个结点，不同形态的二叉树有几种结构？树呢？
答：
不同形态的二叉树有五种如下图

不同形态的树有两种如下图
图片说明
二叉树的性质：
性质1:
在二叉树的第i层上至多有 $图片说明$ 个结点。

推理过程：由其是二叉树且有第i层可知第i-1层以及其以上的层数都是满层，由规律不难看出每层是以2为等比的等比数列的每一项，则第i层是此等比数列的第i项，至多的情况就是第i层排满即 $图片说明$ 个。
性质2：
深度为k的二叉树最多有 $图片说明$ 个结点。

推理过程：至多就是第k层排满，此时二叉树结点数是以2为等比的等比数列排列，那么就是求前k项的结点数之和，即 $图片说明$ 个。
性质3：
叶结点n0与分支结点n2的关系为：n0=n2+1。
推理过程：设树有n个结点，其中叶子结点为n0，度为1的结点为n1,度为2的结点为n2。则n=n0+n1+n2。抛去根节点，此时剩余的结点（皆为根节点的孩子结点）数为n-1。n2有2个孩子结点，n1有1个孩子结点，则孩子结点个数为2n2+n1。所以n-1=2n2+n1其中n=n0+n1+n2可得：2n2+n1+1=n0+n1+n2即n0=n2+1。

满二叉树
定义：深度为k且有 $图片说明$ 个结点的二叉树。
特点：
（1）每一层上的结点都铺满了且叶子结点都在第k层。
（2）n1=0;
（3）n个结点的满二叉树深度为： $图片说明$
推理过程：令 $图片说明$ 则 $图片说明$ ， $图片说明$

设满二叉树结点分别为：1 2 3 ......n则有：
（1）每个左结点都为偶数，每个右结点都为奇数。
（2）结点i的左结点序号为2i，右结点序号为2i+1（2i<=n,2i+1<=n）,结点i的双亲为|i/2|（向下取整，i>=2&&i<=n）
（3）结点x的层号为：
$图片说明$ 。（1<=x<=n）

完全二叉树：
定义：而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。 (如图为一个完全二叉树)

满二叉树一定是完全二叉树，反之不然
下图为一个非完全二叉树
图片说明
F的位置如果在C的左子树位置则此树变为完全二叉树。
深度为k的完全二叉树的特性：
（1）叶结点只能出现在层次最大或者次大的两层。
（2）完全二叉树的n个数满足： $图片说明$ 得： $图片说明$ （log2向下取整）。
（3）设完全二叉树结点分别为：1 2 3 ......n则有：
1.i=1,其为根节点否则i/2向下取整为i的双亲。
2.若2i>n,则其无左孩子结点，否则左孩子结点为2i
3.若2i+1>n,则其无右孩子结点，否则右孩子结点为2i+1
（4）左子树高度-右子树高度小于等于1且大于等于0.
（5）度为1的结点仅有1个或0个（叶子节点尽可能往左排）。
（6）叶子结点个数= n/2或（n+1）/2（n为奇数）

下面提几个问题：若对含n个结点的完全二叉树从上至下且从左至右进行1到n的编号：
（1）n号结点的双亲结点编号是多少？
（2）最后一个非终端结点编号是多少？
（3）度为1的结点有什么特征？
答：
（1）若n=1则无双亲结点；若n>1则双亲结点为|n/2|（向下取整）
（2）若n=1则无非终端结点；若n>1，因为是最后一个非终端结点，所以此结点的孩子中必有一个是最后一个叶子结点，若只有左孩子那么此非终端结点为n/2；若有左右孩子那么为（n-1）/2。
（3）度为1的结点仅有一个或零个。

二叉树的存储方式：
（1）顺序存储结构：
完全二叉树（如下图）
图片说明
其按顺序存储结构就为如下所示：

这是对于完全二叉树来说的，但是对于一般的二叉树可能会造成资源空间上的浪费如下

（2）链式存储结构：由前面得知，除叶节点外，每个分支结点都有孩子jie'd，所以在数据域前后分别加上两个指针域来表示左孩子和右孩子来进行链式存储。
图片说明

如下

可表示为：

二叉树的遍历：
常用的遍历方法有四种分别是：先序遍历，中序遍历，后序遍历，层次遍历。下面给出一个二叉树来分别说明这四种方法。

图片说明

（1）先序遍历——根——>左子树——>右子树。
由开始是根得第一个应该是A. 接着遍历左子树，将左子树看成一个新的二叉树对其进行遍历，则是B为其根子树，然后遍历左子树是D,接着是遍历右子树，同样的因为右子树不是叶子结点所以将其看成一个新的树进行遍历，根结点为F,左子树为E，这样A的左子树就全部遍历完了，由递归思想可知左子树顺序应该为：B D F E。左子树结束就是遍历右子树，将其看成一个新子树（I）先遍历根C，再接着是左子树，继续将左子树看成一个新树（II），继续对其进行遍历，根为G，无左子树，接着是其右子树H，至此这个新树（II）已经遍历结束，即新树（I）的左子树遍历结束，下面遍历新树（I）的右子树，为I。根为A的右子树顺序为：C G H I.
所以整个二叉树的先序遍历顺序为：A B D F E C G H I

（2）中序遍历——左子树——>根——>右子树。
由先从左子树遍历知应该先遍历以B为根的二叉树（树I），对其按照顺序进行中序遍历，其左子树为D，根为B。右子树为一个以F为根的新树（树II）对其按顺序遍历左子树为E，根为F，无右子树。至此树（I）的遍历已经全部结束即整个二叉树的左子树已经遍历结束。接着是遍历整个二叉树的根A. 最后对整个二叉树的右子树进行遍历，右子树是一个以C为根的树（III），对其进行中序遍历，先遍历其左子树，其左子树是一个以G为根的新树（IV），对其中序遍历则有左子树为空，根为G，右子树为H，所以树（IV）的遍历结束顺序，即树（III）的左子树遍历结束，接着遍历其根C和右子树，右子树为I，至此树(III)的遍历结束，即整个二叉树的右子树遍历结束。
所以整个二叉树的中序遍历顺序为：D B E F A G H C I

（3）后序遍历——左子树——>右子树——>根。
按照后序遍历的顺序来，先遍历整个二叉树的左子树树（I），左子树为D，右子树是一个以F为根的新子树（II），对其进行后序遍历，左子树为E，右子树为空，根为F，至此树(II)已经遍历结束，即树（I）的右子树遍历结束，接着遍历树(I)的根，为B，树（I）遍历结束。下面遍历整个二叉树的右子树树（III），其是一个以G为根的新树（IV），对其进行遍历，左子树为空，右子树为H，根为G，至此树（IV）遍历结束，即树(III)的左子树遍历结束，接着遍历树(III)的右子树，为I，最后遍历树（III）的根，为C，至此树（III）遍历结束即整个二叉树的右子树遍历结束。最后遍历其根，为A。
所以整个二叉树的后序遍历顺序为：D E F B H G I C A

（4）层次遍历——>从上到下——>从左到右。
对这棵树进行层次遍历的顺序为：A B C D F G I E H。其核心思想为出列的同时将该元素的孩子结点入列。用图来表示便是如下。
图片说明

知道了这先序，中序，后序遍历便可以根据其中的两种遍历顺序来确定一棵二叉树。（其中中序遍历是必须要的）
下面举一个例子：
已知树为二叉树：
先序遍历结果为：ABDHKECFIGJ
中序遍历结果为：HKDBEAIFCGJ
那么这棵树如何表示？
这里以左子树为例：
由先序遍历顺序根左右可知，A必定为根结点，则在中序遍历里A的左边都为A的左子树的结点，右边都为A的右子树结点。可画图如下：
图片说明
因为在中序遍历里A的左边都为A的左子树的结点，所以在先序遍历顺序中A后面的这五个元素即为左子树结点。将这五个左子树看成新的树，从先序遍历中可以看出B是这个新树的根，再在中序遍历中寻找B结点，可以知道B结点左边的即为这个新树的左子树，右边的即为新树的右子树。可以画图如下。
图片说明
重复上述操作从先序遍历中可以看出左边HKD的D为新树的根，再在中序遍历中寻找D左边的结点即为左子树右边的结点即为右子树。

重复上述操作在先序遍历中寻找出HK中的H为新根，在中序遍历中得知K为右子树。即可得：
图片说明
右子树也同理，最终此二叉树表示为：

同样的若是给出一棵二叉树的先序遍历+后序遍历或者中序遍历+后序遍历同样也可以推理出二叉树的图例即根据遍历结果创建二叉树。

下面以先序遍历为例写出其部分代码的递归描述并解释

void PreOrderTRAVERSE(BiTree T,void(*Visit)(TElem Type& e))
{//先遍历二叉树
    if(T)//如果为非空树进行以下操作
        {
        visit(T->data);//遍历根节点（1）
        PreOrderTRAVERSE(T->Lchild,Visit);//遍历左孩子结点（2）
        PreOrderTRAVERSE(T->Rchild,Visit);//遍历右孩子结点（3）
        }
}

图片说明

以上图为例，先序遍历的顺序为根-左-右，在树为非空树的情况下先进行的是

Visit(T->data);//即先遍历结点A

接着便是

PreOrderTRAVERSE(T->Lchild,Visit);//T->Lchild为T的左孩子结点
这一步具体写下来就是
if(T->Lchild)//如果为非空树进行以下操作
        {
        visit(T->Lchild->data);
        PreOrderTRAVERSE(T->Lchild->Lchild,Visit);//遍历左孩子结点*
        PreOrderTRAVERSE(T->Lchild->Rchild,Visit);//遍历右孩子结点
        }

图中A的左孩子为B，因为B无左孩子结点，所以上述代码中带*号的其实是T->Lchild->Lchild=NULL从而跳过而直接进行下一行的运算，由图可知T->Lchild为B，而B有右孩子为D,则开始遍历D，代码如下：

if(T->Lchild->Rchild)
        {
        visit(T->Lchild->Rchild->data);
        PreOrderTRAVERSE(T->Lchild->Rchild->Lchild,Visit);//遍历左孩子结点*
        PreOrderTRAVERSE(T->Lchild->Rchild->Rchild,Visit);//遍历右孩子结点
        }

由此递归可以得知D后无子函数，即A的左子树遍历完毕，即上述代码中的PreOrderTRAVERSE(T->Lchild,Visit);完成。接下来就是继续执行PreOrderTRAVERSE(T->Rchild,Visit);其运行原理与左子树相同。将代码中遍历的结点按照顺序记录即为此二叉树的先序遍历顺序（ABDCE）.

在遍历二叉树中还可以统计出叶子结点的个数
原理：叶子结点无左右孩子结点，所以依此特征可以用一个计数器，每当遍历到无左右孩子结点的结点时此计数器加一，初始值设为0即可。下面是部分实现代码：

void CountLeaf(BiTree T,int& count)//count初始为0.
{
    if(T)
    {
        if((T->Lchild==NULL) && (T->Rchild==NULL))
        count++;
        else
        {
            CountLeaf(T->Lchild,count);
            CountLeaf(T->Rchild,count);
        }
    }
    else count=0;
}

else后表示若此结点不是叶子结点则继续遍历其左孩子结点与右孩子结点（顺序应该是先遍历完根结点的左子树上的所有叶子结点再遍历右子树上的所有叶子结点，最后count为整个二叉树的叶子个数）。

求二叉树的深度
原理：若二叉树为空树则深度为0，若二叉树不为空树则深度为左右子树其中深度的最大值加一。即为：
f深度=
（1）0（二叉树为空树时）
（2）MAX{左子树深度，右子树深度}+1（不为空树时）
以下是部分基础代码

int Depth(BiTree T)//返回二叉树的深度
    {
        if(T==NULL)//为空树时
           {depthval=0;}
        else
        depthLeft=Depth(T->Lchild);//求T的左子树深度（1）
        depthReft=Depth(T->Rchild);//求T的右子树深度（2）
        depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
    }
return depthval;

以（1）求T的左子树深度为例剖析一下递进关系
当T！=NULL时,depthLeft=Depth(T->Lchild)是以总二叉树的左子树为新的树来求其深度，对其进行以上递归操作后，此新树的左子树和右子树深度已经得知，再通过最后一行代码来求左右子树中较大的子树的深度并加一，这样depthLeft=Depth(T->Lchild);这行代码就结束了，继续向下求其右子树深度，最后判断较大者并加一就是总的二叉树的深度。记得要返回值。

查询二叉树中的某个结点
原理：若是二叉树为空，则无结点返回false。当二叉树不为空，先将结点与根节点相比较，若相等则返回return true，若不等则在此二叉树的左子树中查询，成功返回true，失败则再在右子树中查询找到返回true，失败返回false。部分伪代码如下

bool Search(BiTree T,TElemType x,BiTree &p)//T是查询结点所在的二叉树，x是要查的数，P用来指向所找到的结点
{
    if(T){
         if(T->data==x){p=T;return true;}
         else
         {
            if(Search(T->Lchild,x,p))
            {return true;}
            else
            return Search(T->Rchild,x,p);
         }
         }
    else {p=NULL;return false;}
}

建立二叉树存储结构
（1）以字符串的形式“根-左-右”定义一棵二叉树
例如：
空树就以一个空白字符来表示如（）
只有一个根结点的二叉树A表示为A()();
下图的二叉树可以表示为：
AB()DCE()
alt
则创建一棵二叉树的部分思路如下：

  scanf(&ch)
  if(ch==" ")
  T=NULL;
  else
  {
  	T=new BiTNode;
  	T->data=ch;
  	CreateBiTree(T->lchild)
  	CreateBiTree(T->rchild)
  }

遍历二叉树
以中序遍历为例，中序遍历为左-根-右。
其可以根据递归算法和非递归算法两种来求。
下面先说递归算法
跟上文中的先序遍历相似这里不多说，其部分伪代码如下：

  void PreOrderTRAVERSE(BiTree T,void(*Visit)(TElem Type& e))
{//先遍历二叉树
    if(T)//如果为非空树进行以下操作
        {
        PreOrderTRAVERSE(T->Lchild,Visit);//遍历左孩子结点（1）
  		visit(T->data);//遍历根节点（2）
        PreOrderTRAVERSE(T->Rchild,Visit);//遍历右孩子结点（3）
        }
}

递归如上，非递归思路如下：

  p=b;
  while(栈不为空或者p！=NULL)
  {
  	while(p！=NULL)
  	{
  	将P入栈；
  	p=p->child；
  	}
  }
  if(栈不为空)
  {
  	将P出栈并且访问；
  	p=p->rchild;//对p的右子树也进行同样操作。
  }

栈中结点均没有访问，p指向刚刚出栈结点的右子树=>栈空且p=NULL结束。

  InitStack(S)；p=T；
  while(p||!StackEmpty(S))
  {
  	if(p)//扫描结点p的左孩子并进栈
  	{
  	Push(S,p);//扫描结点p进栈
  	p=p->lchild;//移动到左孩子
  	}
  else{
  	Pop(st,p);//出栈结点，访问结点p
  	if(!Visit(p->data)) return ERROR；
  	p=p->rchild;//转向处理其右子树
  	}
  return OK；
  }

线索二叉树