? ? ? ???本文將通過完成以下內(nèi)容來展示二叉樹的基本操作，代碼解釋標(biāo)注全面而且清晰，代碼書寫也十分規(guī)范，適合初學(xué)者進(jìn)行學(xué)習(xí)，本篇文章算是本人的一些學(xué)習(xí)記錄分享，希望對有需要的小伙伴提供一些幫助~
本文的內(nèi)容為：
用遞歸的方法實(shí)現(xiàn)以下算法：
1．以二叉鏈表表示二叉樹，建立一棵二叉樹（算法5.3）；
2．輸出二叉樹的中序遍歷結(jié)果（算法5.1）；
3．輸出二叉樹的前序遍歷結(jié)果（見講稿）；
4．輸出二叉樹的后序遍歷結(jié)果（見講稿）；
5．計(jì)算二叉樹的深度（算法5.5）；
6．統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個(gè)數(shù)（算法5.6）；
7．統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)；
8．統(tǒng)計(jì)二叉樹的度為1的結(jié)點(diǎn)個(gè)數(shù)；
代碼如下所示：
1、源程序及主要算法說明
#include<iostream>
using namespace std;
//二叉樹的二叉鏈表存儲(chǔ)表示
typedef struct BiNode
{
char data; //結(jié)點(diǎn)數(shù)據(jù)域
struct BiNode *lchild,*rchild; //左右孩子指針
}BiTNode,*BiTree;
//1. 以二叉鏈表表示二叉樹，建立一棵二叉樹（算法5.3）；
void CreateBiTree(BiTree &T)
{
//按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），創(chuàng)建二叉鏈表表示的二叉樹T
char ch;
cin>>ch;
if(ch=='#') T=NULL; //遞歸結(jié)束，建空樹
else{
T=new BiTNode; T->data=ch; //生成根結(jié)點(diǎn)
cout<<"請輸入"<<T->data<<"的左孩子(沒有左孩子輸入#)";
CreateBiTree(T->lchild); //遞歸創(chuàng)建左子樹
cout<<"請輸入"<<T->data<<"的右孩子(沒有左孩子輸入#)";
CreateBiTree(T->rchild); //遞歸創(chuàng)建右子樹
}
} //CreateBiTree
//2．輸出二叉樹的中序遍歷結(jié)果（算法5.1）；
void InOrderTraverse(BiTree T)
{
if(T){
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);}
}
//3．輸出二叉樹的前序遍歷結(jié)果（見講稿）；
void PreOrderTraverse(BiTree T)
{
if(T){
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
// 4．輸出二叉樹的后序遍歷結(jié)果（見講稿）；
void PostOrderTraverse(BiTree T)
{
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}
//5．計(jì)算二叉樹的深度（算法5.5）；
int Depth(BiTree T) {
{ int m,n;
if(T == NULL ) return 0; //如果是空樹，深度為0，遞歸結(jié)束
else
{ m=Depth(T->lchild); //遞歸計(jì)算左子樹的深度記為m
n=Depth(T->rchild); //遞歸計(jì)算右子樹的深度記為n
if(m>n) return(m+1); //二叉樹的深度為m 與n的較大者加1
else return (n+1);
}
}
}
//6．統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個(gè)數(shù)（算法5.6）；
int NodeCount(BiTree T){
if(T==NULL) return 0; // 如果是空樹，則結(jié)點(diǎn)個(gè)數(shù)為0，遞歸結(jié)束
else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
//否則結(jié)點(diǎn)個(gè)數(shù)為左子樹的結(jié)點(diǎn)個(gè)數(shù)+右子樹的結(jié)點(diǎn)個(gè)數(shù)+1
}
//7．統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)；
int LeafCount(BiTree T){
if(T==NULL) //如果是空樹返回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ì)二叉樹的度為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) //如果是空樹返回0
return 0;
int n1=0;
n1=n-2*n0+1;
if (n1<0)
return 0;
return n1;
}
int main()
{
BiTree tree;
cout<<"請輸入建立二叉鏈表的序列：\n";
cout<<"請輸入根節(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 = " <<n1 ;
cout<<"\n";
cout<<endl;
return 0;
}
運(yùn)行結(jié)果如下：
?結(jié)論與體會(huì)：
1通過本次操作我對于二叉樹的定義有了更清晰深刻的認(rèn)識；
2.對于遍歷二叉樹中的三種不同的遍歷方法我也有了更深的認(rèn)識，每個(gè)遍歷方法的操作定義最明顯的差異體現(xiàn)在訪問根節(jié)點(diǎn)的順序不同，先序遍歷會(huì)在開頭訪問根節(jié)點(diǎn)，而中序遍歷則會(huì)在中間，后序遍歷則會(huì)在最后訪問，只要改變程序中的輸出語句的順序，便可類似的實(shí)現(xiàn)三個(gè)遍歷。文章來源：http://www.zghlxwxcb.cn/news/detail-463382.html
本篇文章的內(nèi)容如上所示，希望能為大家學(xué)習(xí)提供幫助~喜歡可以點(diǎn)贊收藏~文章來源地址http://www.zghlxwxcb.cn/news/detail-463382.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：二叉樹的基本操作（用遞歸實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
