实验任务

从终端输入二叉树元素序列，建立对应的二叉树；采用递归的方式先序遍历、中序遍历和后序遍历二叉树并输出遍历序列；*采用递归或非递归的方式层次遍历二叉树；*采用递归的方式统计二叉树中度为0、度为1、度为2的结点个数；采用递归方式销毁二叉树。
例如：建立如下图1所示的二叉树，则在终端输入“AB##DE##C##”序列，其中“#”表示空树。

在这里插入图片描述

代码

// 采用递归算法实现二叉树的三种深度遍历：先序遍历、中序遍历、后序遍历，并统计二叉树中各种结点的个数。

// 二叉树的存储结构采用的二叉链表
// 例如输入AB##DE##C##，则确定要建立的二叉树
// 采用递归方式先序、中序、后序遍历二叉树
// 采用后序方式销毁二叉树
// 统计二叉树中各种结点的个数

#include "iostream"
using namespace std;
#include<stdlib.h>

#define OVERFLOW -1
#define OK 1
#define ERROR 0


typedef int status;
typedef char TElemType;

//二叉树的二叉链表存储结构
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//创建二叉树status CreatBiTree(BiTree &t) 
status CreatBiTree(BiTree &T){
	char c;
	cin>>c;
	if(c == '#') T = NULL;
	 else{
	 	T = new BiTNode;
	 	if(T==NULL)return ERROR;
	 	T->data = c;
	 	CreatBiTree(T->lchild);
	 	CreatBiTree(T->rchild);
	 }
	 return OK;
}
//先序遍历二叉树void PreOrderTraverse(BiTree t)			
status PreOrderTraverse(BiTree T){
	if(T){
		cout<< T ->data;
		PreOrderTraverse(T -> lchild);
		PreOrderTraverse(T -> rchild);
	}
	return OK;
}

//中序遍历二叉树void InOrderTraverse(BiTree t)			
status InOrderTraverse(BiTree T){
	if(T){
		InOrderTraverse(T -> lchild);
		cout<< T ->data;
		InOrderTraverse(T -> rchild);
	}
	return OK;
}

//后序遍历二叉树void PostOrderTraverse(BiTree t)			
status PostOrderTraverse(BiTree T){
	if(T){
		PostOrderTraverse(T -> lchild);
		PostOrderTraverse(T -> rchild);
		cout<< T ->data;
	}
	return OK;
}


//后序销毁二叉树void DestroyBiTree(BiTree &t)	
status DestroyBiTree(BiTree &T){
	if(T){
		DestroyBiTree(T ->lchild);
		DestroyBiTree(T ->rchild);
		free(T);
		T = NULL;
	}
	return OK;
}

//统计二叉树中度为0的结点的个数int Node0Count( BiTree t) 

int Node0Count(BiTree T)
{
	if(T)
	{
		if(T->lchild == NULL && T->rchild == NULL)
			return 1;
		else
			return Node0Count(T->lchild)+Node0Count(T->rchild);
	}
	return ERROR;
}


//统计二叉树中度为1的结点的个数int Node1Count( BiTree t) 
int Node1Count(BiTree T)
{
	if(T)
	{
		if((T->lchild && T->rchild==NULL) || (T->rchild && T->lchild==NULL))
			return Node1Count(T->lchild) + Node1Count(T->rchild) +1;
		else
			return Node1Count(T->lchild) + Node1Count(T->rchild);
	}
	return ERROR;
}

//统计二叉树中度为2的结点的个数int Node2Count( BiTree t) 
int Node2Count(BiTree T)
{
	if(T)
	{
		if(T->lchild && T->rchild)
			return Node2Count(T->lchild) + Node2Count(T->rchild) +1;
		else
			return Node2Count(T->lchild) + Node2Count(T->rchild);
	}
	return ERROR;
}


int main(){
	int ch;
	BiTree t=NULL;
	cout<<"命令菜单：\n\t1.建立二叉树\n\t2.先序遍历\n\t3.中序遍历\n\t4.后序遍历\n\t5.销毁二叉树\n\t6.退出"<<endl;
	cout<<"\n请输入命令：";

	cin>>ch;	

	while(ch!=7){
		switch(ch){
			case 1:	cout<<"\n请输入要建立的二叉树中的元素，#代表空树\n";
					CreatBiTree(t);
					cout<<"二叉树建立成功\n";
					cout<<"\n请继续输入命令：";
					break;

			case 2:	cout<<"先序遍历的结果为：";
					PreOrderTraverse(t);
					cout<<"\n\n请继续输入命令：";
					break;

			case 3:	cout<<"中序遍历的结果为：";
					InOrderTraverse(t);
					cout<<"\n\n请继续输入命令：";
					break;

			case 4:	cout<<"后序遍历的结果为：";
					PostOrderTraverse(t);
					cout<<"\n\n请继续输入命令：";
					break;

			case 5: cout<<"二叉树中度为0的结点个数为："<<Node0Count(t)<<endl;
					cout<<"二叉树中度为1的结点个数为："<<Node1Count(t)<<endl;
					cout<<"二叉树中度为2的结点个数为："<<Node2Count(t)<<endl;
					cout<<"\n\n请继续输入命令：";
					break;

			case 6:	DestroyBiTree(t);
					cout<<"二叉树已销毁.";
					cout<<"\n\n请继续输入命令：";
					break;
		
			default: cout<<"\n输入命令出错，请重新输入命令：";
		}

		cin>>ch;
	}
}//main