1.二叉树基本概念

• 树是N个结点的有限集合,N=0时称为空树,任意一颗非空树满足以下条件:

  1. 有且只有一个特定的称为根的结点
  2. 当N>1时,其他结点可分为m个互不相交的悠闲集合,其中每个集合本身又是一个棵树,并称为根节点的子树

• 树的定义是递归的,是一种递归的数据结构,树作为一种逻辑结构,同时也是一种分层结构,具有以下两特点:

  1. 树的根节点没有前驱结点,除根之外的所有结点有且只有一个前驱结点
  2. 树中所有结点可有零个或多个后继结点

• 树的基本术语

  1. 一个结点的子结点个数称为结点的度,树中结点的最大度数称为树的度
  2. 度大于0的称分支结点或非终端结点,度为0的称为叶子结点或终端结点
  3. 结点的层次: 从树根开始数,根节点为第一层,它的子结点为第二层,...
  4. 树的高度:树中最大层数
  5. 路径:两结点之间经过的结点序列
  6. 路径长度:路径上经过的边的个数

• 树的性质:

  1. 树中的结点数等于所有结点的度数加1
  2. 度为m的树中第i层至多有m^(i-1)个结点
  3. 高度为h的m叉树至多有(m^h-1)/(m-1)个结点
  4. 具有n个结点的m叉树的最小高度为logm(n(m-1)+1)向上取整

• 二叉树:结点度最大为2的有序树,称为二叉树

• 二叉树性质:

  1. 二叉树的第i层最多有2^(i-1)个结点
  2. 非空二叉树的叶子结点树=度为2的结点数+1
  3. 高度为H的二叉树至多有2^H-1个结点
  4. 具有n个结点的完全二叉树的高度为log2N+1(log2N向下取整)

• 特殊二叉树:

  • 满二叉树:除叶子结点外,度全为2的二叉树
  • 完全二叉树:结点编号全部连续的二叉树

• 二叉树的创建:可以用顺序表也可用链表,我这用的是后者,在创建二叉树之前,先要将普通二叉树转换为扩展二叉树,然后按照扩展二叉树的前序遍历序列把结点输入控制台

  • 怎么转换成扩展二叉树:就是将普通二叉树中的所有结点(包括叶结点)的度都变为2,即为了凑满,在结点原本左右孩子为空的地方输入一个特殊符号当做其孩子,我这为空的地方输入的是#
  • 转换成扩展二叉树时,得到它的前序遍历序列,按照这个序列输入控制台即可创建二叉树了

• 二叉树的四种遍历方式:

  1. 前序遍历(DLR):对于每颗子树的遍历顺序均为先访问根结点,再访问左孩子,最后访问右孩子
  2. 中序遍历(LDR):先左孩子,再根结点,最后右孩子
  3. 后序遍历(LRD):先左孩子,再右孩子,最后根结点
  4. 层次遍历:按树的层次遍历,一层访问完再访问下一层,每一层从左至右

• 这里给出前中后序都是基于递归实现的,而层次遍历是通过队列实现的这里给出我对递归的认识

• 递归像剥洋葱,假设我们剥了一层皮后还要洗干净这层皮,这一步才算完成,那么我们在剥完一次皮后,本来按步骤要去洗的,但剥完发现还有一层皮要剥,于是我们就先不洗了,而是立马把新出现的皮给剥了,之后同样看到皮就一路剥下去,每层皮洗的动作都先延后,直到剥完最后一层皮,发现没皮可剥了,那我们就把最后一层皮拿去洗,这样我们对最后一层皮的处理就彻底完成了,完成后这层皮后出现再你手里的就是倒数第二层皮,然后你那它去洗,则第二层皮的处理就完成了,紧接着去洗倒数第三层…依次类推,直到洗好第一层皮那么整个动作就完成了.

二叉树的链式创建及前中后序层次遍历代码实现

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#define maxSize 100
typedef struct BTnode { //二叉链表结点
	char data;
	struct BTnode *lchild;
	struct BTnode *rchild;
} BTnode;

void createBTnode(BTnode *&T) {//按前序遍历创建结点 
	char ch;
	scanf("%c",&ch);//这里要先把二叉树转换为扩展二叉树 ,然后把结点按前序遍历输入 
	if(ch=='#') {
		T=NULL;
	} else {
		T=(BTnode *)malloc(sizeof(BTnode)); 
		T->data=ch;
		createBTnode(*&T->lchild);
		createBTnode(*&T->rchild);
	}
}


void preOrderTraversal(BTnode *T) {//前序遍历输出结点 
	if(T!=NULL) {
		printf("%c ",T->data);
		preOrderTraversal(T->lchild);
		preOrderTraversal(T->rchild);
	}

}

void inOrderTraversal(BTnode *T){//中序遍历输出结点 
	if(T!=NULL){
		inOrderTraversal(T->lchild);
		printf("%c ",T->data);
		inOrderTraversal(T->rchild);
	}
	
} 

void postOrderTraversal(BTnode *T){//后序遍历输出结点 
	if(T!=NULL){
		postOrderTraversal(T->lchild);
		postOrderTraversal(T->rchild);
		printf("%c ",T->data);
	}
	
}

void level(BTnode *p){//二叉树的层次遍历 
	BTnode *bt[maxSize];
	BTnode *q;
	int front,rear;//建立循环队列 
	front=rear=0;//初始化队列 
	if(p!=NULL){
		rear=(rear+1)%maxSize;
		bt[rear]=p;//根结点入队 
		while(front!=rear){//队不为空时循环 
			front=(front+1)%maxSize;
			q=bt[front];//头结点出队 
			printf("%c ",q->data);//出队就打印 
			if(q->lchild!=NULL){//若出队结点有左孩子则左孩子入队 
				rear=(rear+1)%maxSize;
				bt[rear]=q->lchild;
			}
			if(q->rchild!=NULL){//若出队结点有右孩子则右孩子入队 
				rear=(rear+1)%maxSize;
				bt[rear]=q->rchild;
			}
		}
	}
}
int main() {
	BTnode *T;
	createBTnode(T);
	
	printf("前序遍历序列为: ");
	preOrderTraversal(T);
	printf("\n");
	
	printf("中序遍历序列为: ");
	inOrderTraversal(T);
	printf("\n");
	
	printf("后序遍历序列为: ");
	postOrderTraversal(T);
	printf("\n");

	printf("层次遍历序列为: ");
	level(T);
	printf("\n");
	return 0;
}
/*
	示例输入(注:输入的是扩展二叉树序列):ab#d##c##
*/

2.二叉树的查找与插入

#include <iostream>
#include<stdlib.h> 

typedef struct BTNode{
	int data;
	BTNode *lchild;
	BTNode *rchild;
}BTNode;

int SearchBTS(BTNode *T,int key,BTNode *f,BTNode *&p){//二叉排序树的查找 
	BTNode *r,*s;
	if(!T){
		p=f;//p指向他爹
		return 0; 
	}else{
		if(key==T->data){
			p=T;
			return 1;
		}else if(key<T->data){
			return SearchBTS(T->lchild,key,T,p);
		}else{
			return SearchBTS(T->rchild,key,T,p);
		}
	}
}

int InsertBST(BTNode *&T,int key){//二叉树的插入 
	BTNode *p,*s;

	if(!SearchBTS(T,key,NULL,p)){
		s=(BTNode *)malloc(sizeof(BTNode));
		s->data=key;
		s->lchild=s->rchild=NULL;
		if(!p){
			T=s;
		}else if(key<p->data){
			p->lchild=s;
		}else{
			p->rchild=s;
		}
		return 1;
	}
	return 0;
}

void createBTS(BTNode *&T,int arr[],int n){
	for(int i=0;i<n;i++){
		InsertBST(T,arr[i]);
	}
}
void LDR(BTNode *T){
	if(T!=NULL){
		LDR(T->lchild);
		printf("%d ",T->data);
		LDR(T->rchild);
	}
}
int main(int argc, char** argv) {
	BTNode *T;
	int arr[]={5,9,35,8,7,21,6,4};
	for(int i=0;i<8;i++){
		InsertBST(T,arr[i]);
	}
	//createBTS(T,arr,8); 
	LDR(T);
	return 0;
}

3.二叉树前中后序层次遍历实现

• 我的上篇博客给出了二叉树的创建和前中后序遍历算法,但它们都是基于递归实现的,虽然代码简洁,但理解起来有点费劲,想当初第一次看到这么简洁的遍历算法后,心里连连跳出三个卧槽,实在是简洁的不像话,这里先给出我自己对递归的理解.

• 递归像剥洋葱,假设我们剥了一层皮后还要洗干净这层皮,这一步才算完成,那么我们在剥完一次皮后,本来按步骤要去洗的,但剥完发现还有一层皮要剥,于是我们就先不洗了,而是立马把新出现的皮给剥了,之后同样看到皮就一路剥下去,每层皮洗的动作都先延后,直到剥完最后一层皮,发现没皮可剥了,那我们就把最后一层皮拿去洗,这样我们对最后一层皮的处理就彻底完成了,完成后这层皮后出现再你手里的就是倒数第二层皮,然后你那它去洗,则第二层皮的处理就完成了,紧接着去洗倒数第三层...依次类推,直到洗好第一层皮那么整个动作就完成了.

• 前中后序的非递归遍历算法都是依靠辅助栈来实现的,而层次遍历是通过循环队列实现的,下面依次给出操作原理

• 前序遍历(DLR)的非递归思想:

  1. 先定义一个栈,把二叉树的根结点入栈
  2. 然后栈顶出栈,一出栈便输出出栈结点,出栈的同时判断它是否有左右孩子,要有则入栈.注:要是左右孩子都存在则先右孩子入栈,因为先进后出嘛
  3. 最后在栈不为空的条件下一直循环执行步骤2

• 中序遍历(LDR)的非递归思想

  1. 先定义一个栈,把二叉树的根结点入栈
  2. 把从根结点出发的左孩子一路入栈
  3. 碰到第一个没有左孩子的结点则访问输出该结点(即栈顶出栈结点),并让它指向自己的右孩子
  4. 若上一步中该结点有右孩子,则以他的右孩子出发,它有左孩子则左孩子统统入栈,即重复步骤2,步骤3
  5. 若步骤3中的结点没有右孩子,只要栈不为空便栈顶出栈,接着继续做步骤3的判断

• 后序遍历(LRD)的非递归遍历思想

• 和前序遍历的过程一样就四点不同的地方,其他都一样

  1. 需要两个辅助栈实现
  2. 当栈1出栈顶点左右孩子都存在时,先左孩子入栈
  3. 栈1出栈结点立马压入栈2,并不像前序那样立马访问输出
  4. 最后统一让栈2一次性出栈,每个结点一出栈就访问输出

• 后序遍历能这么干的依据是:逆后序遍历就是把先序遍历中对左右子树的遍历顺序交换的结果

• 二叉树的层次遍历实现思想(和图的广度优先遍历思想一致)

  1. 先创建一个二叉树结点类型队列,根结点若不为空则入队
  2. 紧接着对头出队,马上访问输出出队结点的数据域,出队的同时判断该结点是否有左右孩子,有的话则统统入队,注:左右孩子都有时先左孩子入队,先进先出嘛
  3. 在队不为空的情况下循环执行以上两步

  好了,上代码才是王道

#include <iostream>
#include <stdlib.h> 
#define maxSize 100
typedef struct BTNode{
	char data;
	struct BTNode *lchild;
	struct BTNode *rchild;
}BTNode;

void createBTree(BTNode *&p){//前序遍历创建二叉树,所以创建完成后p肯定就是二叉树的根结点 
	char ch;
	scanf("%c",&ch);
	if(ch=='#'){
		p=NULL;
	}else{
		p=(BTNode *)malloc(sizeof(BTNode));
		p->data=ch;
		createBTree(p->lchild);
		createBTree(p->rchild);
	}
}


void preOrderSt(BTNode *p){//前序遍历的非递归实现 
	BTNode *stack[maxSize];
	int top;
	top=-1;
	BTNode *q;
	if(p!=NULL){
		stack[++top]=p;//根结点入栈 
		while(top!=-1){
			q=stack[top--];//根结点出栈 
			printf("%c ",q->data);//访问 
			if(q->rchild!=NULL){//若结点有右孩子则右孩子入栈(先进后出嘛)
				stack[++top]=q->rchild;
			}
			if(q->lchild!=NULL){//有左孩子则左孩子入栈 
				stack[++top]=q->lchild;
			}
		}
	}
}

void inOrderSt(BTNode *p){//中遍历的非递归实现 
	BTNode *stack[maxSize];
	BTNode *q;
	int top;
	top=-1;
	while(p!=NULL||top!=-1){
		while(p!=NULL){//左孩子存在的话一直进栈 
			stack[++top]=p;
			p=p->lchild;
		}
		if(top!=-1){//左孩子不存在则一路出栈,出栈的同时得判读它有没右孩子 
			p=stack[top--];//没有左孩子了,则栈顶出栈 
			printf("%c ",p->data);//一出栈便立马访问 
			p=p->rchild;//若右孩子存在,会进入上面的while循环,再度判读其右孩子有没有左孩子 
		}
	}
} 

void postOrderSt(BTNode *p){//后序遍历的非递归实现 
	BTNode *stack1[maxSize];int top1=-1;
	BTNode *stack2[maxSize];int top2=-1;
	BTNode *q,*s;
	stack1[++top1]=p;//入栈 
	while(top1!=-1){//若栈不为空 
		q=stack1[top1--];//根结点出栈的同时看看有没有左右孩子,有就进栈(先左后右) 
		stack2[++top2]=q;//栈1出栈的元素栈2马上入栈 
		if(q->lchild!=NULL){
			stack1[++top1]=q->lchild;
		}
		if(q->rchild!=NULL){
			stack1[++top1]=q->rchild;
		}
	}
	while(top2!=-1){//栈2中出栈输出 
		s=stack2[top2--];
		printf("%c ",s->data);
	} 
} 

void level(BTNode *p){//二叉树的层次遍历 
	BTNode *bt[maxSize];
	BTNode *q;
	int front,rear;//建立循环队列 
	front=rear=0;//初始化队列 
	if(p!=NULL){
		rear=(rear+1)%maxSize;
		bt[rear]=p;//根结点入队 
		printf("层序遍历序列为: ");
		while(front!=rear){//队不为空时循环 
			front=(front+1)%maxSize;
			q=bt[front];//头结点出队 
			printf("%c ",q->data);//出队就打印 
			if(q->lchild!=NULL){//若出队结点有左孩子则左孩子入队 
				rear=(rear+1)%maxSize;
				bt[rear]=q->lchild;
			}
			if(q->rchild!=NULL){//若出队结点有右孩子则右孩子入队 
				rear=(rear+1)%maxSize;
				bt[rear]=q->rchild;
			}
		}
	}
}

int main(int argc, char** argv) {
	BTNode *p;
	createBTree(p);
	
	printf("前序非递归遍历序列: ");
	preOrderSt(p);
	printf("\n");
	
	printf("中序非递归遍历序列: ");
	inOrderSt(p);
	printf("\n");
	
	printf("后序非递归遍历序列: ");
	postOrderSt(p);
	printf("\n"); 

	printf("层次遍历序列: ");
	level(p);
	printf("\n");     
	return 0;
}

4. 根据遍历序列还原二叉树

• 已知先序序列存在pre[l1...r1]中 ,中序序列存在in[l2...r2]中,二叉树的结点数据域不等,构造二叉树并求其后序遍历序列
• 已知中序序列存在in[l2...r2]中,后序序列存在post[l1...r1],二叉树的结点数据域不等,构造二叉树并求其前序遍历序列

代码如下

#include <iostream>
#include <stdlib.h>

typedef struct BTNode{//二叉树结点 
	char data;
	struct BTNode *lchild,*rchild;
}BTNod;


BTNode *createBT(char pre[],int l1,int r1,char in[],int l2,int r2){//由先序+中序还原二叉树 
	BTNode *s;//为二叉树的根节点 
	int i;
	if(l1>r1){
		return NULL;
	}else{
		s=(BTNode *)malloc(sizeof(BTNode));//为其分配内存空间 
		s->lchild=NULL;//初始化左右孩子指针 
		s->rchild=NULL;
		for(i=l2;i<=r2;i++){
			if(in[i]==pre[l1]){//在中序序列中找到根结点 
				break;
			}
		}
		s->data=in[i];//数据域存放的是根结点的数据 
		s->lchild=createBT(pre,l1+1,l1-l2+i,in,l2,i-1);//找到根结点后,找出左子树的序列范围 
		s->rchild=createBT(pre,l1-l2+i+1,r1,in,i+1,r2);//找出右子树的序列范围 
	}
}

BTNode *createBT2(char post[],int l1,int r1,char in[],int l2,int r2){//由后序+中序还原二叉树 
	BTNode *s;//为二叉树的根节点 
	int i;
	if(l1>r1){
		return NULL;
	}else{
		s=(BTNode *)malloc(sizeof(BTNode));
		s->lchild=NULL;
		s->rchild=NULL;
		for(i=l2;i<=r2;i++){
			if(in[i]==post[r1]){//在中序序列中找到根结点 
				break;
			}
		}
		s->data=in[i];
		s->lchild=createBT2(post,l1,l1-l2+i-1,in,l2,i-1);//找到根结点后,找出左子树的序列范围 
		s->rchild=createBT2(post,l1-l2+i,r1-1,in,i+1,r2);//找出右子树的序列范围 
	}
}

void preOrder(BTNode *p){//前序遍历 
	if(p!=NULL){
		printf("%c ",p->data);
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
}

void postOrder(BTNode *p){//后序遍历 
	if(p!=NULL){
		postOrder(p->lchild);
		postOrder(p->rchild);
		printf("%c ",p->data);
	}
}
int main(int argc, char** argv) {
	BTNode *p;
	char pre[]={'a','b','d','c'};//前序遍历序列 
	char in[]={'b','d','a','c'};//中序遍历序列 
	char post[]={'d','b','c','a'};//后序遍历序列 
	int l1,r1,l2,r2;
	l1=l2=0;
	r1=r2=3;
	printf("由先序+中序确定的二叉树的后序序列为: ") ;
	p=createBT(pre,l1,r1,in,l2,r2);
	postOrder(p);
	printf("\n");
	 
	printf("由中序+后序确定的二叉树的前序序列为: ") ;
	p=createBT2(post,l1,r1,in,l2,r2);
	preOrder(p);
	return 0;
}

我在上述代码中也给出了类似的已知中序+后序求二叉树的实现,但已知前序+后序不能唯一确定一颗二叉树

5.二叉树最大宽度求法

求二叉树中结点最多的那层的结点数

#include <iostream>
#include <stdlib.h> 

#define maxSize 100
typedef struct BTNode{//二叉树结点 
	char data;
	struct BTNode* lchild;
	struct BTNode* rchild;
}BTNode;

typedef struct{//结点及所在层 
	BTNode *p;
	int lno;
}St;

void createBTreePre(BTNode *&p){//创建二叉树 
	char ch;
	scanf("%c",&ch);
	if(ch=='#'){
		p=NULL;
	}else{
		p=(BTNode *)malloc(sizeof(BTNode));
		p->data=ch;
		createBTreePre(p->lchild);
		createBTreePre(p->rchild);
	}
}
 

int maxNode(BTNode *p){//求二叉树的最大宽度 
	St que[maxSize]; //队列 
	int front,rear,lno,i,j,max,n;
	max=0;
	front=rear=0;
	BTNode *q;
	
	if(p!=NULL){
		rear++;
		que[rear].p=p;//根节点入队 
		que[rear].lno=1; //记录结点所在层数 
		while(front!=rear){//队不为空 
			++front;
			q=que[front].p;
			lno=que[front].lno;//队头出队 
			if(q->lchild!=NULL){//出队的同时看看左右孩子是否存在,在的话就入队 
				++rear;
				que[rear].p=q->lchild;
				que[rear].lno=lno+1;
			}
			if(q->rchild!=NULL){
				++rear;
				que[rear].p=q->rchild;
				que[rear].lno=lno+1;
			}
		}
		for(i=1;i<=lno;i++){//层数循环 
			n=0;
			for(j=1;j<=rear;j++){//队列循环 
				if(que[j].lno==i){//结点之间只要层数相同,n加1 
					n++;//计数的功能 
				}
			}
			max=(max>=n) ? max : n;
		}
		return max;
	}else{
		return 0;
	}
} 
int main(int argc, char** argv) {
	BTNode *p;
	int n;
	createBTreePre(p);
	n=maxNode(p);
	printf("%d\n",n);
	return 0;
}