二叉树递归的应用

时间：2021-05-27作者：klpeng分类：IT综合浏览：260评论：0

二叉树通过递归实现基本应用

定义一个二叉树结构体:

typedef struct bitNode{
	char data;
	struct bitNode *lchild;
	struct bitNode *rchild;
}bitNode,* biTree;

1.创建二叉树

void creatTree(bitNode *& root) //记得加&
{
	//认为输入的二叉树为前序遍历字符串 
	//以输入的字符串：AB#C##D#EF###为例
	//输入#则认为该节点为NULL
	char ch;
	if(ch=='#'){
		root = NULL;
	}else{
		//创建一个树结点
		root = (bitTree)malloc(sizeof(bitNode));
		root->data = ch;
		creatTree(root->lchild);
		creatTree(root->rchild);
		 
	}
}

2.遍历二叉树

递归遍历二叉树有三种

（1）前序遍历

void preorder(bitNode *root)
{
	
	
	if(root == NULL){
		return ;
	}else{
	
		cout<<root->data;
		preorder(root->lchild);
		preorder(root->rchild);
	}
}

（2）中序遍历

void inorder(bitNode *root)
{
	
	
	if(root == NULL){
		return ;
	}else{
	
		
		inorder(root->lchild);
		cout<<root->data;
		inorder(root->rchild);
	}
}

（3）后序遍历

void postorder(bitNode *root) //后序遍历 
{
	if(root == NULL){
		return ;
	}else{
		postorder(root->lchild);
		postorder(root->rchild);
		cout<<root->data;
	}
}

3.求二叉树中的结点数

int node(bitNode*root) //求结点数 
{
	if(root == NULL){
		return 0;
	}else{
		return node(root->rchild)+node(root->lchild)+1;
	}
}

4.求二叉树的高度

int height(bitNode *root)//求树的高度
{
	if(root==NULL){
		return 0;
	}else{
		int left = height(root->lchild);
		int right = height(root->rchild);
		return (left>right)?left+1:right+1;
	}	
}

5.求二叉树的树叶数

int leaf(bitNode *root)//求叶子结点数 
{
	if(root==NULL){
		return 0;
	}
	else if(root->lchild==NULL&&root->rchild==NULL){
		return 1;
	}else{
		return leaf(root->lchild)+leaf(root->rchild);
	}
}

测试代码:


int main()
{
	bitNode *root;
	creatTree(root); //创建一个二叉树
	cout<<"\n二叉树的前序遍历:"<<endl;
	preorder(root); 
	cout<<"\n二叉树的中序遍历:"<<endl;
	inorder(root);
	cout<<"\n二叉树的后序遍历:"<<endl;
	postorder(root);
	
	cout<<"\n二叉树的叶子:"<<endl;
	cout<<leaf(root); 
	cout<<"\n二叉树的高度:"<<endl;
	cout<<height(root);
	cout<<"\n二叉树的结点数:"<<endl;
	cout<<node(root); 
}

运行结果: