递归算法遍历二叉树（先序、中序、后序遍历二叉树，求树的深度，结点个数等）

迈不过友情╰ 2022-05-03 11:58 178阅读 0赞

## 递归实现二叉树基本操作 ##

### 源代码实现： ###

#include<iostream>
    using namespace std;
    typedef struct node{
    	struct node * lchild;
    	struct node * rchild;
    	char data;
    }BiTreeNode,*BiTree;
    
    void CreateBiTree(BiTree &T){
    	char c;
    	cin>>c;
    	if('#'==c)
    		T = NULL; 
    	 else
    	 {
    	 	T = new BiTreeNode;
    	 	T->data = c;
    	 	CreateBiTree(T->lchild);
    	 	CreateBiTree(T->rchild);
    	  } 
    		
    }
    
    void PreOrderTraverse(BiTree T)
    {
    	if(T)
    	{
    		cout<<T->data;
    		PreOrderTraverse(T->lchild);
    		PreOrderTraverse(T->rchild);
    	}
    }
    
    void InOrderTravers(BiTree T){
    	if(T){
    	InOrderTravers(T->lchild);
    	cout<<T->data;
    	InOrderTravers(T->rchild);
    	}	
    }
    
    void PostOrderTravers(BiTree T){
    	if(T){
    	PostOrderTravers(T->lchild);
    	PostOrderTravers(T->rchild);
    	cout<<T->data;
    	}	
    }
    
    void Copy(BiTree T,BiTree &NewT)
    {
    	if(T==NULL)
    	{
    		NewT=NULL;
    		return;
    	}
    	else{
    	NewT=new BiTreeNode;
    	NewT-> data=T-> data;
    	Copy(T->lchild,NewT->lchild);
    	Copy(T->rchild,NewT->rchild);
    	}
    }
    
    int Depth(BiTree T)
    {
    	int m,n;
    	if(T==NULL)  return 0;
    	else {
    		m=Depth(T->lchild);
    		n=Depth(T->rchild);
    		if(m>n) return (m+1);
    		else return (n+1);
    	}
    }
    
    int NodeCount(BiTree T)
    {
    	if(T==NULL) return 0;
    	else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    }
    
    int main(){
    	BiTree T;
    	BiTree NewT;
    	cout<<"创建二叉树:\n";
    	CreateBiTree(T);
    	cout<<"***  ***  ***  ***  ***\n";
    	cout<<"请选择：\n";
    	cout<<"1.先序遍历二叉树 \n";
    	cout<<"2.中序遍历二叉树 \n";
    	cout<<"3.后序遍历二叉树 \n";
    	cout<<"4.复制二叉树 \n";
    	cout<<"5.计算二叉树的深度 \n";
    	cout<<"6.统计二叉树中结点的个数 \n";
    	cout<<"***  ***  ***  ***  ***\n";
    	int a;
    	cin>>a;
    	cout<<endl;
    	switch(a)
    	{
    		case 1:PreOrderTraverse(T);break;
    		case 2:InOrderTravers(T);break;
    		case 3:PostOrderTravers(T);break;
    		case 4:Copy(T,NewT);break;
    		case 5:cout<<Depth(T);break;
    		case 6:cout<<NodeCount(T);break;
    		default:cout<<"ERROR!"<<endl;
    	}
    	return 0;
    	
    }