(超详细)C++实现链式二叉树的系列操作（数据结构）

//导入头文件
#include
#include
using namespace std;
int count=0;//记录叶子结点个数 

//二叉树链式存储结构
typedef struct BTNode{
	char data;//数据域
	struct BTNode *lchild,*rchild;//左右孩子指针 
}BTNode,*BiTree; 


//创建二叉链表树
BiTree CreateBiTree(){
	BiTree T; //定义二叉树结点结构体变量 
	char ch;  
	cin>>ch; //输入数据元素 
	if(ch == '#'){
		T=NULL; //输入字符#，则将对应结点孩子指针域置为空 
	}else{
		T=(BTNode *)malloc(sizeof(BiTree)); //分配结点存储空间 
		T->data=ch;
		T->lchild=CreateBiTree();
		T->rchild=CreateBiTree();
	}
	return T; //返回创建的二叉树T 
} 

//显示二叉树结点
 
//1.按先序次序(递归)访问二叉树
void PreOrder(BiTree T){
	if(T==NULL){
		return;//结束 
	}else{
		cout<data;
		PreOrder(T->lchild);//遍历左孩子
		PreOrder(T->rchild);//遍历右孩子 
	}
}


//2.按中序次序(递归)访问二叉树
void InOrder(BiTree T){
	if(T==NULL){
		return;//结束 
	}else{
		InOrder(T->lchild);//遍历左孩子
		cout<data;
		InOrder(T->rchild);//遍历右孩子 
	}
}

//3.按后序次序(递归)访问二叉树
void PostOrder(BiTree T){
	if(T==NULL){
		return;//结束 
	}else{
		PostOrder(T->lchild);//遍历左孩子
		PostOrder(T->rchild);//遍历右孩子 
		cout<data;
	}
}

//4.按先序次序(递归)输出叶子结点
void PrePrintLeaf(BiTree T){
	if(T!=NULL){
		if(T->lchild==0&&T->rchild==0){ //叶子结点左、右孩子均为0 
			cout<data;	
		}
		PrePrintLeaf(T->lchild);//遍历左孩子
		PrePrintLeaf(T->rchild);//遍历右孩子
	}
}

//5.统计叶子结点的个数
void CountLeafNum(BiTree T){
	if(T!=NULL){
		if(T->lchild==0&&T->rchild==0){ //叶子结点左、右孩子均为0 
			count++;
		}
		CountLeafNum(T->lchild);//统计左孩子叶子结点的个数
		CountLeafNum(T->rchild);//统计右孩子叶子结点的个数
	}
}

//6.按后序次序(递归)输出度为2的结点
void PostPrintNode(BiTree T){
	if(T!=NULL){
		PostPrintNode(T->lchild);//遍历左孩子
		PostPrintNode(T->rchild);//遍历右孩子
		if(T->lchild!=NULL&&T->rchild!=NULL){
			cout<data;	
		}
	}
}

//7.获取二叉树的深度
int PostTreeDepth(BiTree T){
	int ldepth,rdepth;//记录左右孩子深度
	if(T==NULL){
		return 0;
	}else{
		ldepth=PostTreeDepth(T->lchild);//左孩子深度
		rdepth=PostTreeDepth(T->rchild);//右孩子深度
		if(ldepth>rdepth){
			return ldepth+1;
		}else{
			return rdepth+1;
		}
	}
}


//显示菜单 
void load(){
	cout<>choose;
	while(choose!=8){
		switch(choose){
			case 1:{
				PreOrder(T);
				break;
			}
			case 2:{
				InOrder(T);
				break;
			}
			case 3:{
				PostOrder(T);
				break;
			}
			case 4:{
				PrePrintLeaf(T);
				break;
			}
			case 5:{
				CountLeafNum(T);
				cout<>choose;
	}
	return 0;
}

        注意：输入初始数据时是以“先序”的顺序输入的（即“根-左-右”），需要提前换算好再输入。