二叉树的基本操作

发表于 | 更新于 | 分类于 | 评论数：
本文字数： 27k | 阅读时长 ≈ 24 分钟

二叉树简介

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。

二叉树的操作

1
2
3
4
5
6
//二叉树节点的数据成员
typedef struct BinTreeNode{
	char data;                   //字符型节点数据域
	struct BinTreeNode *Lchild;  //指向左孩子的指针
	struct BinTreeNode *Rchild;	 //指向右孩子的指针
}BinNode,*BinTree;

二叉树的初始化操作

所谓初始化就是将一颗二叉树由用户输入的数据构造出来。初始化的的方法由很多中，其中将会介绍的是利用先序&中序 或者 中序&后序 以及“扩展的先序遍历序列”共三种方法来构造二叉树。

1.扩展的先序遍历序列构造二叉树。

对于扩展的先序序列的二叉树是这样一颗二叉树的:所有的节点都有两个孩子(度<2的用“^”补充完整)。如上图的二叉树扩展后为:

先序遍历后结果为:ABD^^E^^CF^^^。

只需要输入整个先序遍历结果就可以构造一颗图中的二叉树。代码如下

1
2
3
4
5
6
7
8
9
10
11
BinTree Create_Kz(string Stemp){     //利用字符串作为暂时存放序列的介质 
	BinNode *root;
	if(Stemp[intemp++]=='^')root=NULL;
	else{
		root=new BinNode;
		root->data=Stemp[intemp-1];
		root->Lchild=Create_Kz(Stemp);
		root->Rchild=Create_Kz(Stemp);
	}
	return root;
}



2.根据先序遍历与中序遍历的结果来构造二叉树

对于每一颗二叉树来说，先序遍历的第一个节点一定是根节点，中序遍历中，根节点的左边一点时左子树的所有节点，根节点的右边一定时右子树的所有节点，依照这个思路就可以通过先序和中序遍历得到一个完整的二叉树。

先序序列时用来作为找根节点的依据，而找到根节点后就可以利用中序序列来分割出左右子树(如下图)，按相同的方法分别找到左右子树的根节点和其左右子树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int find(string s,char ch,int start,int end){
	int i=start;
	while(i<=end && s[i]!=ch)i++;
	if(i>end)return -1;
	else return i;
}
BinTree Create_PI(string Pre,int Pstart,int Pend,string In,int Istart,int Iend){   
	BinTree Tree;//参数说明-依次为: 先序序列,起点,终点,中序序列,起点,终点 
	if(Pstart>Pend || Istart>Iend) 
		Tree=NULL;
	else{
		int i=find(In,Pre[Pstart],Istart,Iend);//查找该节点元素值在中序中的位置 
		if(i!=-1){ 
			Tree=new BinNode;
			Tree->data=Pre[Pstart];
			if(i!=Istart)Tree->Lchild=Create_PI(Pre,Pstart+1,Pstart+(i-Istart),In,Istart,i-1);
			else Tree->Lchild=NULL;  
			if(i!=Iend)Tree->Rchild=Create_PI(Pre,Pstart+(i-Istart)+1,Pend,In,i+1,Iend);
			else Tree->Rchild=NULL;
		}
		else{
			cout<<"输入数据有误"<<endl;
			exit(1);//运行异常，结束程序 
		}
	}
	return Tree;
}

3.根据中序遍历与后序遍历的结果来构造二叉树

和第二中基本原理相同，不过有所改变的是二叉树的根节点在后序遍历中位于最后一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BinTree Create_AI(string Aft,int Astart,int Aend,string In,int Istart,int Iend){
	BinTree Tree;//依次为:后序序列，后序起点，后序终点，中序序列，中序起点，中序终点 
	if(Astart>Aend || Istart>Iend)
		Tree=NULL;  
	else{
		Tree=new BinNode;
		int i=find(In,Aft[Aend],Istart,Iend);
		if(i!=-1){
			Tree->data=Aft[Aend];//或者可以赋值为In[i]; 
			if(i!=Istart) Tree->Lchild=Create_AI(Aft,Astart,Astart+(i-Istart)-1,In,Istart,i-1);
			else Tree->Lchild=NULL;
			if(i!=Iend) Tree->Rchild=Create_AI(Aft,Astart+i-Istart,Aend-1,In,i+1,Iend);
			else Tree->Rchild=NULL;
		}
		else{
			cout<<"输入的数据有误"<<endl;
			exit(1);
		}
	}
	return Tree;
}

二叉树的遍历

基础的二叉树遍历方法有一下三种：

  1. 先序遍历:访问次序为根节点-左子树-右子树。
  2. 中序遍历:访问次序为左子树-根节点-右子树。
  3. 后序遍历:访问次序为左子树-右子树-根节点。

先序遍历

如图中二叉树，其先序遍历的过程如下：

  1. 首先访问根节点A，然后访问A的左子树。
  2. A的左子树的根节点是B，访问完毕。接下来访问B的左子树，B的左子树的根节点很显然是D
  3. D无孩子，所以B的左子树已访问完毕。按照定义，我们访问B的右子树，其右子树的根节点为E
  4. E无孩子，所以B的右子树也已访问完毕。此时我们已经遍历完根节点A的左子树了，我们只需要按照相同的方法访问A的右子树即可遍历完整颗二叉树。

最后的遍历结果为：ABDECF

中序遍历

说完先序，其实中序的访问过程也大同小异，只不过调换了左子树和根节点的访问顺序。其遍历的过程如下:

  1. 第一步是访问根节点A的左子树,对其左子树进行中序排序。
    1. 其左子树是以B为根节点的子树，先访问B的左子树，其左子树无孩子所以直接访问其根节点D。
    2. 以B为根节点的子树的左子树已访问完毕，访问根节点B
    3. 接下来中序访问以B为根节点的子树的右子树。其右子树无孩子所以直接访问其根节点E
  2. 根节点A的左子树中序访问完毕，访问根节点A
  3. 按照相同方法，中序访问根节点A的右子树。

最后的遍历结果为: DBEAFC

后序遍历

最后是后序遍历，其与先序的差别就是先访问左子树和右子树，最后访问根节点，其过程如下:

  1. 后序遍历根节点A的左子树
    1. 后序遍历根节点B的左子树，因D无孩子，所以访问D后，B的左子树访问完毕。
    2. 后序遍历根节点B的右子树，因E无孩子，所以访问E后，B的右子树访问完毕。
    3. 最后访问根节点B。
  2. 后序遍历根节点A的右子树
    1. 后序遍历根节点C的左子树，因F无孩子，所以访问F后，C的左子树访问完毕。
    2. C无右子树,所以直接跳到最后一步–访问C。
  3. 最后访问根节点A

后序遍历结果为: DEBFCA

C++递归实现：（先序，中序，后序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Pre(BinTree root){  //先序遍历 
	if(root){
		cout<<root->data;
		Pre(root->Lchild);
		Pre(root->Rchild);
	}
}

void In(BinTree root){ //中序遍历 
	if(root){
		In(root->Lchild);
		cout<<root->data;
		In(root->Rchild);
	}
}
void Aft(BinTree root){ //后序遍历 
	if(root){
		Aft(root->Lchild);
		Aft(root->Rchild);
		cout<<root->data;
	}
}

二叉树的其他相关操作

求二叉树的高度

所谓二叉树的高度是指所有叶子节点到根节点的最短路径的最大值+1。如下图中的二叉树的高度为5

用眼睛我们可以直接判断出数的高度，那么，如何用代码实现求二叉树的高度呢？

对于一棵二叉树来说，我们要做的是判断左右子树的高度，取最大值，然后再加上+1（根节点也是一层）。依次递归，对于节点不存在时我们返回其高度为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
int DepthTree(BinTree root){ //如果一颗树存在，返回这棵树的高度
	int hl,hr;//分别记录左子树高度和右子树高度 
	if(!root)return 0; 
	if(root->Lchild)
		hl=DepthTree(root->Lchild);
	else 
		hl=0;
	if(root->Rchild)
		hr=DepthTree(root->Rchild);
	else 
		hr=0;
	return  hl>hr?hl+1:hr+1;	
}

求某个节点的高度

节点的高度是指当前节点到根节点的路径值+1，如上图中节点D的高度为2+1=3

和求树的高度思路大致相同，因为一棵树只有一个所求节点，所以需要先在左子树中寻找，如果未找到，则在右子树中寻找，返回0代表该二叉树中无此节点。

1
2
3
4
5
6
7
8
9
int DepthNode(BinTree root,BinTree ch){
	if(!root || !ch)return NULL;
	int len=0;
	if(root==ch)return 0;
	len=DepthNode(root->Lchild,ch);
	if(len>0)return len+1;
	else len=DepthNode(root->Rchild,ch);
	return len+1;
}

求某个节点的双亲节点

因为链二叉树的节点内没有直接前驱域，所以需要该项操作，并且判断时是由以某节点的左右孩子是否为给出的节点来判断该节点是否为给出的节点的双亲节点。

设给出节点为ch.

  1. 判断根节点是否为ch的双亲节点
  2. 判断根节点的左孩子是否为ch的双亲节点
  3. 判断根节点的右孩子是否为ch的双亲节点
1
2
3
4
5
6
7
8
BinTree Parents(BinTree root,BinTree Object){//寻找Object的双亲节点
	if(!root)return NULL;
	if(root->Lchild==Object || root->Rchild==Object)return root;
	BinTree p;
	p=Parents(root->Lchild,Object);
	if(p)return p;
	else return Parents(root->Rchild,Object);
}

求二叉树的节点个数

求节点个数与求树的高度思路大同小异，我们要求的就是左子树的节点个数加上右子树的节点个数再加1（根节点）。依次递归，如果节点不存在，就返回其节点个数为0。

1
2
3
4
5
6
7
8
9
int BinCount(BinTree root){
	if(!root)return 0;
	int cl,cr; //分别记录左子树节点个数和右子树节点个数 
	if(root->Lchild)cl=BinCount(root->Lchild);
	else cl=0;
	if(root->Rchild)cr=BinCount(root->Rchild);
	else cr=0;
	return cl+cr+1; 
}

一个更优的编码方式：

1
2
3
4
5
int Size(BinTree T)
{
if (T==NULL) return 0;
else return Size(T->Lchild)+Size(T->Rchild)+1;
}

求树的叶子节点个数

遍历时加以对于叶子节点的判断即可(无孩子),左子树叶子节点个数加上右子树的个数

1
2
3
4
5
int BinLeaf_1(BinTree root){
	if(!root)return 0;
	if(root->Lchild==NULL && root->Rchild==NULL) return 1;
	return BinLeaf_1(root->Lchild)+BinLeaf_1(root->Rchild);
}

输出叶子节点值

先序或者后序遍历时判断是否为叶子节点再输出即可

1
2
3
4
5
6
7
void BinLeaf_2(BinTree root){
	if(!root)return ;
	if(root->Lchild==NULL && root->Rchild==NULL)
		cout<<root->data<<" ";
	BinLeaf_2(root->Lchild);
	BinLeaf_2(root->Rchild);
}

总结

对于二叉树作为一种基础的层次性逻辑结构，在算法中的应用范围很广，例如哈夫曼树、排序二叉树等等……这部分内容还是需要自己牢牢掌握的。

0%