《大大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉樹地遍歷》由會員分享，可在線閱讀，更多相關(guān)《大大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉樹地遍歷（21頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、word
摘要
針對現(xiàn)實(shí)世界中許多關(guān)系復(fù)雜的數(shù)據(jù)，如人類社會的家譜，各種社會組織機(jī)構(gòu),博弈交通等復(fù)雜事物或過程以與客觀世界中廣泛存在的具有分支關(guān)系或?qū)哟翁匦缘膶ο螅绮僮飨到y(tǒng)的文件構(gòu)成、人工智能和算法分析的模型表示以與數(shù)據(jù)庫系統(tǒng)的信息組織形式等，用線性結(jié)構(gòu)難以把其中的邏輯關(guān)系表達(dá)出來，必須借助于數(shù)和圖這樣的非線性結(jié)構(gòu)，因此在以模擬客觀世界問題，解決客觀世界問題為主要任務(wù)的計(jì)算機(jī)領(lǐng)域中樹型結(jié)構(gòu)是信息的一種重要組織形式，樹有著廣泛應(yīng)用。在樹型結(jié)構(gòu)的應(yīng)用中又以二叉樹最為常用。
二叉樹是一種非常重要的非線性結(jié)構(gòu)，所描述的數(shù)據(jù)有明顯的層次關(guān)系，其中的每個元素只有一個前驅(qū)，二叉樹是最為常用的數(shù)據(jù)結(jié)構(gòu)
2、，它的實(shí)際應(yīng)用非常廣泛，二叉樹的遍歷方式有三種，前序遍歷，中序遍歷，后序遍歷，先序遍歷的順序?yàn)椋篘LR先根結(jié)點(diǎn)，然后左子樹，右子樹；中序遍歷順序?yàn)椋籐NR先左子樹，然后根結(jié)點(diǎn)，右子樹；后序遍歷順序?yàn)椋篖RN先左子樹，然后右子樹，根結(jié)點(diǎn)。由前序和中序遍歷，有中序和后序遍歷序列可以唯一確定一棵二叉樹。對于給幾個數(shù)據(jù)的排序或在的幾個數(shù)據(jù)中進(jìn)展查找，二叉樹均能提供一種十分有效的方法，比如在查找問題上，任何借助于比擬法查找長度為Ⅳ的一個序表的算法，都可以表示成一株二叉樹。反之，任何二叉樹都對應(yīng)一個查找有序表的有效方法根據(jù)樹的數(shù)學(xué)理論，對于算法分析的某些最有啟發(fā)性的應(yīng)用，是與給出用于計(jì)算各種類型中不同樹的
3、數(shù)目的公式有關(guān)的。
本文對二叉樹以與二叉樹的各種功能做介紹以與寫出一些根本的程序，讓我們對二叉樹的理解有更好的效果。
關(guān)鍵詞：二叉樹的遍歷；左子樹；右子樹；遞歸
文案大全
目錄
3
3
3
3
3
3
2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：3
3
3
3
3
總結(jié)3
參考文獻(xiàn)3
文案大全
創(chuàng)建二叉樹并遍歷?根本要求：?
該程序集成了如下功能：
〔1〕二叉樹的建立
〔2〕遞歸和非遞歸先序，中序和后序遍歷二叉樹
〔3〕按層次遍歷二叉樹
〔4〕交換二叉樹的左右子樹
〔5〕輸出葉子結(jié)點(diǎn)
〔6〕遞歸和非遞歸計(jì)算葉子結(jié)點(diǎn)的數(shù)目
分先序
4、遍歷，中序遍歷和后序遍歷三種情況考慮。
1. 先序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否如此完畢操作：
① 訪問根結(jié)點(diǎn)；
② 按先序遍歷規(guī)如此遍歷左子樹；
③ 按先序遍歷規(guī)如此遍歷右子樹；
2. 中序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否如此完畢操作：
① 按中序遍歷規(guī)如此遍歷左子樹；
② 訪問根結(jié)點(diǎn)；
③ 按中序遍歷規(guī)3遍歷右子樹。
3. 后序遍歷，當(dāng)二叉樹非空時按以下順序遍歷，否如此完畢操作：
① 按后序遍歷規(guī)如此遍歷左子樹；
② 按后序遍歷規(guī)如此遍歷右子樹；
③ 訪問根結(jié)點(diǎn)。
對任意給定的二叉樹〔頂點(diǎn)數(shù)自定〕建立它的二叉鏈表存貯結(jié)構(gòu)，并
5、利用棧的五種根本運(yùn)算〔清空堆棧、壓棧、彈出、取棧頂元素、判?？铡硨?shí)現(xiàn)二叉樹的先序、中序、后序三種周游，輸出三種周游的結(jié)果。
流程圖與結(jié)構(gòu)圖
YES
YES
NO
NO
圖1.1 流程圖
2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：
1．?二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義為：?
template??struct?BiNode?
{?
BiNode*rchild,*lchild;//指向左孩子的指針
T?data;//結(jié)點(diǎn)數(shù)據(jù)信息?};?
2．?二叉樹數(shù)據(jù)類型定義為：?
template??class?BiTree
6、?{?
template??
friend?ostream?&?operator?<<(ostream?&os?,BiTree?&bt);?public:?
BiTree();//無參構(gòu)造函數(shù)?
BiTree(int?m){};//有參空構(gòu)造函數(shù)?
BiTree(T?ary[],int?num,T?none);//有參構(gòu)造函數(shù)??
BiTree();//析構(gòu)函數(shù)?
void?preorder();//遞歸前序遍歷??
void?inorder();//遞歸中序遍歷??
void?postorder();//遞歸后續(xù)遍歷?
void?levelo
7、rder();//層序遍歷?
int??count();//計(jì)算二叉樹的結(jié)點(diǎn)數(shù)??
void?display(ostream?&os);//打印二叉樹，有層次??
void?LevelNum();//計(jì)算每一層結(jié)點(diǎn)數(shù)??
void?PreOrder();//非遞歸前序遍歷??
void?PostOrder();//非遞歸后序遍歷??
void?creat();//創(chuàng)建二叉樹?
protected:?//以下函數(shù)供上面函數(shù)調(diào)用??//對應(yīng)一樣功能?
Voidcreat(BiNode*&root);//創(chuàng)建??
void?release(BiNode*?&root);
8、//刪除?
BiNode?*?Build(T?ary[],int?num,T?none,int?idx);//用數(shù)組創(chuàng)建二叉樹??
void?PreOrder(BiNode*?root);//前序遍歷??
void?PostOrder(BiNode*?root);//后續(xù)遍歷??
void?LevelNum(BiNode*?root);//層序遍歷??
void?preorder(BiNode*?root);//遞歸前序遍歷??
void?inorder(BiNode*?root);//遞歸中序遍歷??
void?postorder(BiNod
9、e*?root);//遞歸后續(xù)遍歷??
void?levelorder(BiNode*root);//層序遍歷??
int?count(BiNode*?root);//計(jì)算結(jié)點(diǎn)數(shù)???
void?display(ostream&?os,BiNode*?root,int?dep);//打印?
static?bool?leastmanAncestor(BiNode?*root,?T?va,?T?vb,?BiNode???????????????????????
private:BiNode?*rootptr;?
};
#inc
10、lude
using namespace std;
//*************************************************************************************
//二叉樹結(jié)點(diǎn)類的定義
template
struct BTNode
{
T data;
BTNode * Lchild,*Rchild;
BTNode(T nodeValue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NUL
11、L )
:data(nodeValue),Lchild(leftNode),Rchild(rightNode){} //可選擇參數(shù)的默認(rèn)構(gòu)造函數(shù)
};
//**************************************************************************************
//二叉樹的建立
template
void createBinTree(BTNode * &root )
{
BTNode* p = root;
BTNode* k;
12、
T nodeValue ;
cin>>nodeValue;
if(nodeValue==-1)
{
root=NULL;
}
else
{
root=new BTNode();
root->data = nodeValue;
createBinTree(root->Lchild);
createBinTree(root->Rchild);
}
}
//*********************************
13、***************************************************
//二叉樹的先序遍歷
template
void preOrder( BTNode * & p)
{
if(p)
{
cout<data<<" ";
preOrder(p->Lchild);
preOrder(p->Rchild);
}
}
//************************************************************
14、**************************
//二叉樹的中序遍歷
template
void inOrder(BTNode * & p)
{
if(p)
{
inOrder(p->Lchild);
cout<data<<" ";
inOrder(p->Rchild);
}
}
//**************************************************************************************
15、
//二叉樹的后序遍歷
template
void levelOrder(BTNode *& p)
{
if(p)
{
levelOrder(p->Lchild);
levelOrder(p->Rchild);
cout<data<<" ";
}
}
//*************************************************************************************
//統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個數(shù)
templa
16、te
int countNode(BTNode * & p)
{
if(p == NULL) return 0;
return 1+countNode(p->Lchild)+countNode(p->Rchild);
}
//***********************************************************************************
//求二叉樹的深度
template
int depth(BTNode *& p)
{
if(p == NULL
17、)
return -1;
int h1 = depth(p->Lchild);
int h2 = depth(p->Rchild);
if(h1>h2)return (h1+1);
return h2+1;
}
//***********************************************************************************
//二叉樹的消毀操作
template
BTNode* destroy(BTNode* p)
18、 //消毀函數(shù)，用來消毀二叉樹中的各個結(jié)點(diǎn)
{
if(p)
{
return destroy(p->Lchild);
return destroy(p->Rchild);
delete p;
}
}
//********************************************************************************
//主函數(shù)的設(shè)計(jì)
int main ()
{
19、 BTNode * rootNode = NULL;
int choiced = 0;
while(true)
{
system("cls");
cout<<"\n\n\n ---主界面---\n\n\n";
cout<<" 1、創(chuàng)建二叉樹 2、先序遍歷二叉樹\n";
cout<<" 3、中序遍歷二叉樹 4、后序遍歷二叉樹\n";
cout<<"
20、 5、統(tǒng)計(jì)結(jié)點(diǎn)總數(shù) 6、查看樹深度 \n";
cout<<" 7、消毀二叉樹 0、退出\n\n";
cout<<" 請選擇操作：";
cin>>choiced;
if(choiced == 0)
return 0;
else if(choiced == 1)
{
system("cls");
cout<<"請輸入每
21、個結(jié)點(diǎn)，回車確認(rèn)，并以-1完畢：\n";
createBinTree(rootNode );
}
else if(choiced == 2)
{
system("cls");
cout<<"先序遍歷二叉樹結(jié)果：\n";
preOrder(rootNode);
cout<
22、== 3)
{
system("cls");
cout<<"中序遍歷二叉樹結(jié)果：\n";
inOrder(rootNode);
cout<
23、lOrder(rootNode);
cout<
24、if(choiced == 6)
{
system("cls");
int dep = depth(rootNode);
cout<<"此二叉樹的深度為"<
25、oy(rootNode);
cout<
26、試結(jié)果正確。?計(jì)算每層結(jié)點(diǎn)數(shù)：調(diào)用levelNum()函數(shù)，測試結(jié)果正確。??
調(diào)試時遇到諸多問題，其中最主要的問題是死循環(huán)問題，在非遞歸遍歷時，容易進(jìn)入死循環(huán)，經(jīng)過查找資料、分步調(diào)試最終找到循環(huán)完畢條件，順利解決各個難題。
〔1〕初始界面:主界面所包含的內(nèi)容
〔2〕運(yùn)行結(jié)果：進(jìn)展操作1，輸入每個結(jié)點(diǎn)，顯示結(jié)果如下
進(jìn)展操作2，執(zhí)行結(jié)果如下：
進(jìn)展操作3，執(zhí)行結(jié)果如下：
進(jìn)展操作4，執(zhí)行結(jié)果如下：
圖4.5二叉樹后序遍歷:
進(jìn)展操作5，執(zhí)行結(jié)果如下：
進(jìn)展操作6，執(zhí)行結(jié)果如
27、下：
總結(jié)
要能很好的掌握編程,僅僅通過幾個簡單的程序的編寫時無法達(dá)成的,更需要大量積累和深入才可能通過本次課程設(shè)計(jì)。有關(guān)一個課題的所有知識不僅僅是在課本上，多查閱一些資料能夠更好的完成課題，這就需要一種能力，即自學(xué)能力。本次課程設(shè)計(jì)還讓我認(rèn)識到自己的缺點(diǎn)。本次選的課題是二叉樹的遍歷，因?yàn)楸緦W(xué)期所學(xué)的就是二叉樹等數(shù)據(jù)結(jié)構(gòu)，所以認(rèn)為比擬適合。剛開始認(rèn)為會很簡單，但到后來就出現(xiàn)一些難以解決的問題，就像教師請教，并查閱相關(guān)資料。經(jīng)過慢慢的調(diào)試，最終測試成功。?
這次課程設(shè)計(jì)讓我所學(xué)到的數(shù)據(jù)結(jié)構(gòu)知識發(fā)揮的淋漓盡致，而且還拓展了我的知識面，使我更加熟練的掌握各種方法。?
總之，這次課程設(shè)計(jì)增強(qiáng)了我的自學(xué)能力，拓展了我的知識面，讓我對數(shù)據(jù)結(jié)構(gòu)更加了解。
參考文獻(xiàn)
[1] 嚴(yán)蔚敏吳偉民《數(shù)據(jù)結(jié)構(gòu)(C語言版)》清華大學(xué)， 2009年9月
[2] 譚浩強(qiáng)《C程序設(shè)計(jì)(第三版)》清華大學(xué) 2009年1月
大大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉樹地遍歷
