大话数据结构---（五）二叉树

1.二叉树的基本概念

二叉树是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树特点
（1）每个结点最多有两棵子树。
（2）左子树和右子树是有顺序的，次序不能任意颠倒。
（3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
特殊二叉树
满二叉树：如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。（满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的）。

2.二叉树的性质

从上一篇博客可以得知，任意一棵树能通过孩子兄弟表示法转换为二叉树，那么二叉树的性质有哪些呢？

  • 在二叉树的第i层上至多有2(i-1)个结点（i>=1）
  • 深度为k的二叉树至多有2k-1个结点（k>=1）
  • 如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i,有：
    （1）如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]。
    （2）如果2i>n,则结点i无左孩子；否则其左孩子是结点2i。
    （3）如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。

3.二叉树的存储结构

二叉树顺序存储结构：二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。
先来看看完全二叉树的顺序存储，一棵完全二叉树如图1所示： 在这里插入图片描述将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如图2所示：
在这里插入图片描述
考虑一种极端情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2k-1个存储空间，这显然是对存储空间的浪费。所以，顺序存储结构一般只用于完全二叉树。
二叉链表：既然顺序存储结构不能满足大部分树的存储，那么这里考虑链式存储结构。二叉树的每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表，结点结构如图所示。
在这里插入图片描述
结点结构代码为：

typedef struct BiTNode//结点结构
{
TElemType data;//结点数据
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

结构示意图如图所示：
在这里插入图片描述就如同树的存储结构中讨论的一样，如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表。

4.二叉树的遍历

定义：是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问依次且仅被访问一次。
二叉树的遍历方法：二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了。

  • 前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。上图所示的前序遍历结果为：ABDGHCEIF。
    代码如下：
void PreOrderTraverse(BiTree T)
{
   if(T==NULL)
     return ;
  cout<<T->data;//显示结点数据，可以更改为其他对结点操作
  PreOrderTraverse(T->lchild);//再先序遍历左子树
  PreOrderTraverse(T->rchild);//最后先序遍历右子树
}
  • 中序遍历：规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。上图所示的中序遍历结果为：GDHBAEICF。
void InOrderTraverse(BiTree T)
{
  if(T==NULL)
     return ;
  InOrderTraverse( T->lchild);//中序遍历左子树
  cout<<T->data;//显示结点数据，可以更改为其他对结点操作
  InOrderTraverse(T->rchild);//最后中序遍历右子树 
}
  • 后序遍历：规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。上图所示的中序遍历结果为：GHDBIEFCA。
void PostOrderTraverse(BiTree T)
{
  if(T==NULL)
   return ;
  PostOrderTraverse(T->lchild);//先后序遍历左子树
  PostOrderTraverse(T->rchild);//再后序遍历右子树
  cout<<T->data;//显示结点数据，可以更改为其他对结点的操作
}
  • 层序遍历：规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。上图所示的中序遍历结果为：ABCDEFGHI。
    这里可能有人会问，研究这么多遍历方法干什么呢？
    我们用图形方式表示树的结构，而对计算机而言，他只有循环和判断等方式来处理，也就是说它只能处理线性序列。而我们刚才提到的遍历方式就是为了将图形结构转换为线性序列，这就给程序的实现带来的好处。

5.二叉树的建立

说了半天对二叉树的操作，那么二叉树是哪来的呢，当然是自己创建的。为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，将左图扩展为右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如“#”。右图的前序遍历序列就为AB#D##C##。
在这里插入图片描述
有了这样的准备，我们就可以得知如何创建一棵二叉树了，我们把刚才前序遍历序列AB#D##C##用键盘挨个输入。实现的算法如下：

void CreateBiTree(BiTree *T)
{
 TElemType ch;
 cin>>ch;
 if(ch=='#')
 *T=NULL;
 else{
 *T=(BiTree)malloc(sizeof(BiTNode));
 if(!*T)
 exit(OVERFLOW);
 (*T)->data=ch;//生成根结点
 CreateBiTree(&(*T)->lchild);//构造左子树
 CreateBiTree(&(*T)->rchild);//构造右子树
}
}

当然，你完全也可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交换一下。另外输入的字符也要做相应的更改。
二叉树的完整代码：

#include<iostream>
using namespace std;
typedef struct BTNode {//定义树结点
	char data;
	struct BTNode *lchild, *rchild;
}*BiTree;
void CreateTree(BiTree &T) {//前序创建二叉树
	char data;
	cout << "请输入结点的值：";
	cin >> data;
	if (data == '#') {
		T = NULL;
	}
	else {
		T = (BiTree)malloc(sizeof(BTNode));
		T->data = data;
		CreateTree(T->lchild);//构造左子树
		CreateTree(T->rchild);//构造右子树
	}
}
void PreOrderTraverse(BiTree T) {//前序遍历
	if (T!=NULL) {
		PreOrderTraverse(T->lchild);
		cout << T->data << " ";
		PreOrderTraverse(T->rchild);
	}
}
int main() {
	cout << "前序创建二叉树，空指针输入#"<<endl;
	BiTree T = (BiTree)malloc(sizeof(BTNode));
	CreateTree(T);
	cout << "前序遍历二叉树" << endl;
	PreOrderTraverse(T);
}

运行实例如下：
在这里插入图片描述

6.线索二叉树

仔细观察上面的黑色输入框，不难发现，为了创建一个只有四个元素的二叉树，新增了五个空间用于存储‘#’，也就是浪费了一半的空间。对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数，也就是说，存在2n-(n-1)=n+1个空指针域，白白浪费着内存资源，这显然是不提倡的。除此之外，对于上述的二叉链表，我们之恶能直到每个结点指向其左右孩子结点的地址，而不知道该结点的前驱是谁，后继是谁。要想直到必须先遍历一次，那么为什么不考虑在创建时就记住这些结点的前驱后继呢。
我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。下图实例即将图1线索化后转换成图2。
在这里插入图片描述在这里插入图片描述那么问题来了，怎样判断lchlid是指向它的前驱还是左孩子呢，因为只有这两种情况，这时第一想法是添加一个bool变量，当然也可以是其它变量。因此，我们在每个结点在增设两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于想lchild和rchild的指针变量，结点结构如表所示：
在这里插入图片描述
其中：
ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rtag为0时指向该结点的右孩子，为1时指向该结点的后继。
线索二叉树的实现
线索存储结构定义代码如下：

typedef enum{Link,Thread}PointerTag;//Link==0表示指向左右孩子指针，Thread==1表示指向前驱或后继的线索
typedef struct BiThrNode{//二叉线索存储结点结构
TElemType data;//结点数据
struct BiThrNode *lchild,*rchil;//左右孩子指针
PointerTag LTag;
PointerTag RTag;//左右标志
}BiThrNode,*BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。
中序遍历线索化的递归函数代码如下：

BiThrTree pre;//全局变量，始终指向刚刚访问过的结点
//中序遍历进行中序线索化
void InThreading(BiThrTree p)
{
  if(p)
  { 
    InThreading(p->lchild);//递归左子树线索化
    if(!p->lchild)//没有左孩子
    {
      p->LTag=Thread;//前驱线索
      p->lchild=pre;//左孩子指针指向前驱
    }
    if(!pre->rchild)//前驱没有右孩子
    {
      pre->RTag=Thread;//后继线索
      pre->rchild=p;//前驱右孩子指针指向后继（当前结点p）
    }
    pre=p;//保持pre指向p的前驱
    InThreading(p->rchild);//递归右子树线索化
  }
}

遍历线索二叉树的代码如下:

//T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
//中序遍历二叉线索链表表示的二叉树T
Status InOrderTraverse_Thr(BiThrTree T)
{
 BiThrTree p;
 p=T->lchlid;//p指向根结点
 while(p!=T){//空树或遍历结束时，p==T
 while(p->LTag==Link)//当LTag==0时循环到中序序列第一个结点
{
  p=p->lchild;
}
cout<<p->data<<endl;//显示结点数据，可以更改为其它对结点操作
while(p->RTag==Thread&&p->rchild!=T)
{
  p=p->rchild;
  cout<<p->data<<endl;
}
p=p->rchild;//p进至其右子树根
}
return OK;
}

如果所用的二叉树需经常遍历后查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构时非常不错的选择。