???本文將通過(guò)完成以下內(nèi)容來(lái)展示二叉樹(shù)的基本操作，代碼解釋標(biāo)注全面而且清晰，代碼書(shū)寫(xiě)也十分規(guī)范，適合初學(xué)者進(jìn)行學(xué)習(xí)，本篇文章算是本人的一些學(xué)習(xí)記錄分享，希望對(duì)有需要的小伙伴提供一些幫助~

本文的內(nèi)容為：

用遞歸的方法實(shí)現(xiàn)以下算法：

1．以二叉鏈表表示二叉樹(shù)，建立一棵二叉樹(shù)（算法5.3）；

2．輸出二叉樹(shù)的中序遍歷結(jié)果（算法5.1）；

3．輸出二叉樹(shù)的前序遍歷結(jié)果（見(jiàn)講稿）；

4．輸出二叉樹(shù)的后序遍歷結(jié)果（見(jiàn)講稿）；

5．計(jì)算二叉樹(shù)的深度（算法5.5）；

6．統(tǒng)計(jì)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)（算法5.6）；

7．統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)；

8．統(tǒng)計(jì)二叉樹(shù)的度為1的結(jié)點(diǎn)個(gè)數(shù)；

1、源程序及主要算法說(shuō)明
#includeusing namespace std;

//二叉樹(shù)的二叉鏈表存儲(chǔ)表示
typedef struct BiNode
{				
	char data;						//結(jié)點(diǎn)數(shù)據(jù)域
	struct BiNode *lchild,*rchild;	//左右孩子指針
}BiTNode,*BiTree;

//1. 以二叉鏈表表示二叉樹(shù)，建立一棵二叉樹(shù)（算法5.3）；
void CreateBiTree(BiTree &T)
{	
//按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），創(chuàng)建二叉鏈表表示的二叉樹(shù)T
	char ch;
	cin>>ch;
	if(ch=='#')   T=NULL;  	//遞歸結(jié)束，建空樹(shù)
	else{
   	 	T=new BiTNode;    T->data=ch; 	//生成根結(jié)點(diǎn)
		cout<<"請(qǐng)輸入"<data<<"的左孩子(沒(méi)有左孩子輸入#)";
    	CreateBiTree(T->lchild);  //遞歸創(chuàng)建左子樹(shù)
   		cout<<"請(qǐng)輸入"<data<<"的右孩子(沒(méi)有左孩子輸入#)";
    	CreateBiTree(T->rchild); //遞歸創(chuàng)建右子樹(shù)
  }																	
}									//CreateBiTree
//2．輸出二叉樹(shù)的中序遍歷結(jié)果（算法5.1）；					
void InOrderTraverse(BiTree T)
{  
 	if(T){   
     InOrderTraverse(T->lchild); 
     cout<data;
     InOrderTraverse(T->rchild);}
}

//3．輸出二叉樹(shù)的前序遍歷結(jié)果（見(jiàn)講稿）；
void PreOrderTraverse(BiTree T)
{
	if(T){     
     cout<data; 
     PreOrderTraverse(T->lchild); 
     PreOrderTraverse(T->rchild);
} 
}
// 4．輸出二叉樹(shù)的后序遍歷結(jié)果（見(jiàn)講稿）；
void PostOrderTraverse(BiTree T)
{
	if(T){
     PostOrderTraverse(T->lchild); 
     PostOrderTraverse(T->rchild); 
     cout<data; 
} 
}

//5．計(jì)算二叉樹(shù)的深度（算法5.5）；
int Depth(BiTree T) {
{    int m,n;
	if(T == NULL ) return 0;        //如果是空樹(shù)，深度為0，遞歸結(jié)束
	else 
	{	m=Depth(T->lchild);			//遞歸計(jì)算左子樹(shù)的深度記為m
		n=Depth(T->rchild);			//遞歸計(jì)算右子樹(shù)的深度記為n
		if(m>n) return(m+1);		//二叉樹(shù)的深度為m 與n的較大者加1
		else return (n+1);
	}
}
}

//6．統(tǒng)計(jì)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)（算法5.6）；
int NodeCount(BiTree T){
 	if(T==NULL) return 0;  			// 如果是空樹(shù)，則結(jié)點(diǎn)個(gè)數(shù)為0，遞歸結(jié)束
     	else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
    	 //否則結(jié)點(diǎn)個(gè)數(shù)為左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)+1
} 

//7．統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)；
int LeafCount(BiTree T){
 	if(T==NULL) 	//如果是空樹(shù)返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是葉子結(jié)點(diǎn)返回1
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

//8．統(tǒng)計(jì)二叉樹(shù)的度為1的結(jié)點(diǎn)個(gè)數(shù)；
//	n=n0+n1+n2; n2=n0-1; n1=n-n0-n2=n-n0-(n0-1)=n-2n0+1
int n1Count(BiTree T,int n,int n0){
	if(T==NULL) 	//如果是空樹(shù)返回0
		return 0;
	
	int n1=0; 
	n1=n-2*n0+1;
	
	if (n1<0) 
		return 0;
		
	return n1;
}

int main()
{
	BiTree tree;
	cout<<"請(qǐng)輸入建立二叉鏈表的序列：\n";
	cout<<"請(qǐng)輸入根節(jié)點(diǎn)：";
	CreateBiTree(tree);
	
	cout<<"所建立的二叉鏈表先序序列：\n";
	PreOrderTraverse(tree);
	cout<<"\n";
	cout<<"所建立的二叉鏈表中序序列：\n";
	InOrderTraverse(tree);
	cout<<"\n";
	cout<<"所建立的二叉鏈表后序序列：\n";
	PostOrderTraverse(tree);
	cout<<"\n";
	
	int depth = Depth(tree);
	cout<<"所建立的二叉鏈表深度是：\n";
	cout<< "depth = "<< depth;
	cout<<"\n";
	
	cout<<"所建立的二叉鏈表結(jié)點(diǎn)個(gè)數(shù)是：\n";
	int nodeCount = NodeCount(tree);
	cout<< "nodeCount(n) = "<< nodeCount;
	cout<<"\n";
	
	cout<<"所建立的二叉鏈表葉結(jié)點(diǎn)個(gè)數(shù)是：\n";
	int leafCount = LeafCount(tree);
	cout<< "leafCount(n0) = "<< leafCount;
	cout<<"\n";
	
	cout<<"所建立的二叉鏈表度為1的結(jié)點(diǎn)個(gè)數(shù)是：\n";
	int n1 = n1Count(tree,nodeCount,leafCount);
	cout<< "n1 = "<

運(yùn)行結(jié)果如下：