二叉树的基本操作(代码+注释)

前言：掌握二叉树的基本操作，如二叉树的建立、遍历、结点个数统计、树的层次遍历等。

ps：这里是个人整理的笔记，方便自己后期的复习，若有问题欢迎各位大佬前来指教！

#include
#include
#define MAXNODE 1000
typedef int ElemType;
typedef struct BiNode{
	ElemType data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTNode *creatNode(ElemType data){
	BiTNode *node=(BiTNode *)malloc(sizeof(BiTNode));
	node->data=data;
	node->lchild=node->rchild=NULL;
	return node;
} 
//初始化二叉树
void initBiTree(BiTree *bi){
//	如果此时形参仅为一级指针的话，函数内部会生成一个保存一级指针的临时变量 
//	要想改变这个一级指针的指向，就必须传递二级指针，
//	这样，就可以通过二级指针所指向的地址来修改一级指针的指向 
	*bi = NULL;
} 
//由值来创建二叉树
void creatBiTree(BiTree T){
	int ch;
	scanf("%d",&ch);
	if(ch== -1)
		T=NULL; //为-1时便不再调用自己，结束递归 
	else {
//		由根左右的顺序创建结点 
		T=creatNode(ch); //生成根节点
		//由递归创建子树 
		creatBiTree(T->lchild);
		creatBiTree(T->rchild); 
	}	
} 
//自动插入  ------用来创建完全二叉树
void insert(BiTree *bi,ElemType data){
//	先创建结点--->为结点分配一个存储空间
	BiTNode *node=creatNode(data);
	if(*bi==NULL){
		*bi=node;//为空树的话，直接将结点赋给根结点 
	}
//	定义一个存储树的队列 
//	这里使用的是广度优先的层次遍历思想---->从上到下，从左到右 
	BiTree Queue[MAXNODE];
	int front,rear;
//	从队列里存储的结点判断是否存在空的位置，有空的位置则放入创建好的结点
//	所以，我们需要从队列的第一个位置开始判断
	front=rear=0;
	//存入根结点的地址 
	Queue[rear++]==*bi;
	while(front!=rear){
//		从队列中取值判断是否有左右孩子 
//		没有则将node赋给空位置处 
		BiTree temp=Queue[front++];
		if(temp->lchild){ 
			Queue[rear++]=temp->lchild;
		} 
		else{
			temp->lchild=node;
			return;
		}
		if(temp->rchild){
			Queue[rear++]=temp->rchild;
		}
		else{
			temp->rchild = node;
			return;
		}
	} 
} 
//深度优先搜索------->采用递归的思想
//先序遍历
void preOrder(BiTree bi){
	if(bi==NULL){
		return;
	}
	printf("%4d",bi->data);
//	递归
	preOrder(bi->lchild);//先递归遍历左子树，左子树全部遍历完后，再遍历右子树
	preOrder(bi->rchild); 
} 
//中序
void midOrder(BiTree bi){
	if(bi==NULL){
		return;
	}
	midOrder(bi->lchild);
	printf("%4d",bi->data);
	midOrder(bi->rchild);
} 
//后序
void laterOrder(BiTree bi){
	if(bi==NULL){
		return;
	}
	laterOrder(bi->lchild);
	laterOrder(bi->rchild);
	printf("%4d",bi->data);
} 
//宽度优先搜索--->借用队列
void layerOrder(BiTree bi){
	BiTree temp;
	if(bi==NULL){
		return;	
	}
	BiTree Queue[MAXNODE];
	int front,rear;
	front=rear=0;
//	根结点先入队 
	Queue[rear++]=bi;
	while(rear!=front){
		temp=Queue[front++];
		
		if(temp->lchild){
			Queue[rear++]=temp->lchild;
		}
		if(temp->rchild){
			Queue[rear++]=temp->rchild;
		}
		//根节点出队 
		printf("%4d",temp->data);
	}
}
//统计叶子结点的个数-->递归
int countLeaf(BiTree bi){
	if(bi==NULL){
		return 0;
	}
	//判断出叶子结点 并返回1 
	if(bi->lchild==NULL&&bi->rchild==NULL)
	return 1;
	//递归 
	return countLeaf(bi->lchild)+countLeaf(bi->rchild);
} 
 
int main(){
	BiTree bi = NULL;
	int i;
	initBiTree(&bi);
	//生成二叉树
	
	ElemType data[]={1,2,3,4,5,6,7,8,9};
	 for(i=0;i<9;i++){
	 	insert(&bi,data[i]);
	 }
	
	 //先序遍历
	 preOrder(bi);
	 printf("n");
//	 中序
	midOrder(bi);
	printf("n");
//	后序
	 laterOrder(bi);
	 printf("n");
//	 层次遍历
	layerOrder(bi);
	printf("n"); 
}