數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之-樹與二叉樹的轉(zhuǎn)換

1、. 衡陽師范學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目： 樹與二叉樹的轉(zhuǎn)換 系 別： 計算機(jī)科學(xué)系 專 業(yè)： 計算機(jī)科學(xué)與設(shè)計 班 級： 1302 學(xué)生姓名： 戴志豪 學(xué) 號： 13190217 指導(dǎo)老師： 趙磊 完成日期： 2015年1月3號 目錄一需求分析.3 二概要設(shè)析.3 三詳細(xì)設(shè)計.5 1.樹的建立.5 2.一般樹轉(zhuǎn)化成二叉樹.6 3.先序遍歷樹的遞歸算法.7 4.后序遍歷樹的遞歸算法.7 5.先序遍歷樹的非遞歸算法.7 6.后序遍歷樹的非遞歸算法.8 7.層次序非遞歸的算法.9四設(shè)計與調(diào)試分析.10五用戶手冊.10六測試結(jié)果.11七附錄（源程序）.14 八總結(jié).20一.需求分析本程序的功能是對任意

2、樹進(jìn)行遞歸前序遍歷和后序遍歷，以及實(shí)現(xiàn)樹的非遞歸的前序、和后序遍歷，還有對樹的層序遍歷以及樹與二叉樹的轉(zhuǎn)換。二概要設(shè)計 對于本次設(shè)計，需要用到樹的建立,樹與二叉樹的轉(zhuǎn)換算法先序后序二叉樹的遞歸算法;先序后序非遞歸算法;層次序遍歷算法 1樹的建立用鏈表實(shí)現(xiàn)創(chuàng)建一個樹結(jié)點(diǎn)的結(jié)構(gòu)體，從鍵盤輸入數(shù)據(jù)，存入數(shù)組。把下標(biāo)為2*i+1 的值存入左孩子，為2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。開始參數(shù)數(shù)組是否空或越界把數(shù)組的值賦給結(jié)點(diǎn)的數(shù)據(jù)域 返回根指針結(jié)束返回空指針YN遞歸的給左子樹賦值參數(shù)變?yōu)閍2i+1 遞歸的給右子樹賦

3、值參數(shù)變?yōu)閍2i+2 2一般樹轉(zhuǎn)化成二叉樹轉(zhuǎn)換時結(jié)點(diǎn)的第一個孩子變?yōu)樗淖蠛⒆?，兄弟?jié)點(diǎn)變?yōu)樗挠液⒆?。void exchange()，class Tree3先序遍歷樹的遞歸算法若二叉樹為空，則空操作；否則（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。void PreOrder(BiNode root)。開始判斷結(jié)點(diǎn)是否空訪問根結(jié)點(diǎn)結(jié)束 按前根遍歷方式遍歷左子樹按前根遍歷方式遍歷左子樹YN4后序遍歷樹的遞歸算法若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹。（3）訪問根結(jié)點(diǎn)；void PostOrder(BiNode root)。開始判斷結(jié)點(diǎn)是否空按后根

4、遍歷方式遍歷左子樹結(jié)束按后根遍歷方式遍歷右子樹訪問根結(jié)點(diǎn)YN5先序遍歷樹的非遞歸算法若二叉樹為空，則空操作；否則（1）先將根節(jié)點(diǎn)進(jìn)棧，在棧不為空時循環(huán)；(2)出棧p，訪問*p若其右孩子節(jié)點(diǎn)不空將右孩子節(jié)點(diǎn)進(jìn)棧若其左孩子節(jié)點(diǎn)不空時再將其左孩子節(jié)點(diǎn)進(jìn)棧。6后序遍歷樹的非遞歸算法 采用一個棧保存需要返回的指針，先掃描根節(jié)點(diǎn)所有的左孩子節(jié)點(diǎn)并一一進(jìn)棧，出棧一個節(jié)點(diǎn)*b作為當(dāng)前節(jié)點(diǎn)，然后掃描該節(jié)點(diǎn)的右子樹。當(dāng)一個節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)均訪問后再訪問該節(jié)點(diǎn)，如此重復(fù)操作，直到?？諡橹埂?層次序的非遞歸遍歷按照樹的層次從左到右訪問樹的結(jié)點(diǎn)，層序遍歷用于保存結(jié)點(diǎn)的容器是隊列。void LevelOrder(BiN

5、ode root)。3 詳細(xì)設(shè)計1樹的建立：PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf("輸入第%d結(jié)點(diǎn):n",i);scanf("%d,%d",&fa,&ch);printf("n");p.data=ch;p.parent=fa;T.count+; T.nodeT.count.data = p.data; T.nodeT.count.parent = p.parent;printf("n")

6、;printf("創(chuàng)建的樹具體情況如下:n");print_ptree(T);return T;2一般樹轉(zhuǎn)換成二叉樹BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;i&

7、lt;T.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;i<T.count;i+)ip=&pi;is=&pj;while(T.nodei.parent!=is->data)j+;is=&pj;if(!(is->firstchild)is->firstchild=ip;ir=ip;elseir->rightsib=ip;ir=ip;Tree=&p0;return Tree;3先序遍歷樹的遞歸算法：void preorder(BTNode *T)if(T!=NULL)printf("

8、;%d ",T->data);preorder(T->firstchild);preorder(T->rightsib);4.先序遍歷樹的非遞歸算法void preOrder2(BinTree *root) /非遞歸先序遍歷 stack<BinTree*> s; BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) cout<<p->data<<" " s.push(p); p=p->lchild; if(!s.empty() p=s.to

9、p(); s.pop(); p=p->rchild; 5.后序遍歷樹的遞歸算法void inoeder(BTNode *T)if(T!=NULL)inoeder(T->firstchild);printf("%d ",T->data);inoeder(T->rightsib);6后序遍歷樹的非遞歸算法void postOrder2(BinTree *root) /非遞歸后序遍歷 stack<BTNode*> s; BinTree *p=root; BTNode *temp; while(p!=NULL|!s.empty() while(p

10、!=NULL) /沿左子樹一直往下搜索，直至出現(xiàn)沒有左子樹的結(jié)點(diǎn) BTNode *btn=(BTNode *)malloc(sizeof(BTNode); btn->btnode=p; btn->isFirst=true; s.push(btn); p=p->lchild; if(!s.empty() temp=s.top(); s.pop(); if(temp->isFirst=true) /表示是第一次出現(xiàn)在棧頂 temp->isFirst=false; s.push(temp); p=temp->btnode->rchild; else /第二次

11、出現(xiàn)在棧頂 cout<<temp->btnode->data<<" " p=NULL; 7層次序樹的非遞歸算法void initqueue(linkqueue &q) /初始化一個帶頭結(jié)點(diǎn)的隊列 q.front=q.rear=(queueptr)malloc(sizeof(queuenode); q.front->next=NULL;void enqueue(linkqueue &q,bitrees p) /入隊列 queueptr s; int first=1; s=(queueptr)malloc(sizeof(

12、queuenode); s->ch=p; s->next=NULL; q.rear->next=s; q.rear=s;void dequeue(linkqueue &q,bitrees &p) /出隊列 int data; queueptr s; s=q.front->next; p=s->ch; data=p->data; q.front->next=s->next; if(q.rear=s) q.rear=q.front; free(s); printf("%dt",data);int queueempt

13、y(linkqueue q) /判斷隊列是否為空 if(q.front->next=NULL) return 1; return 0;void traverse(bitrees bt) /按層次遍歷樹中結(jié)點(diǎn) linkqueue q; bitrees p; initqueue(q); p=bt; enqueue(q,p); while(queueempty(q)!=1) dequeue(q,p); if(p->lchild!=NULL) enqueue(q,p->lchild); if(p->rchild!=NULL) enqueue(q,p->rchild); 4

14、 設(shè)計與調(diào)試分析1.二叉樹遍歷中用到的最重要的一個思想就是遞歸調(diào)用，這次作業(yè)使我們對遞歸有了深入的理解，程序調(diào)試比較順利。2.用棧同樣可以實(shí)現(xiàn)二叉樹的遍歷，這是我們認(rèn)識到解決問題可以由多種不同的途徑，應(yīng)隨時將以前學(xué)過的只是靈活應(yīng)用起來，解決新問題。3.因?yàn)楸闅v二叉樹的基本操作是訪問結(jié)點(diǎn)，所以無論哪一種遍歷方式，對含有n個結(jié)點(diǎn)的二叉樹，其時間復(fù)雜度為O（n），所需輔助空間最大容量為樹的深度，最壞為n，所以空間復(fù)雜度為O（n）。4.因該程序?qū)?yīng)不同的遍歷定義了不同的結(jié)構(gòu)，使每種結(jié)構(gòu)的通用性降低，可以往在遞歸和非遞歸中使用同一種結(jié)構(gòu)這一方面做進(jìn)一步的思考。五用戶手冊運(yùn)行程序，首先出現(xiàn)主界面。主界面有

15、七個選項。選項一、以雙親法創(chuàng)建一棵樹。選項二、此選項可以對所創(chuàng)建的樹采用遞歸算法進(jìn)行前序遍歷。選項三、此選項可以對所創(chuàng)建的樹采用遞歸算法進(jìn)行后序遍歷。選項四、此選項可以對所創(chuàng)建的樹采用非遞歸算法進(jìn)行先序遍歷。選項五、此選項可以對所創(chuàng)建的樹采用非遞歸算法進(jìn)行后序遍歷。選項六、此選項可以退出程序。六測試結(jié)果程序開始一般樹轉(zhuǎn)換成二叉樹的情況副菜單選擇：選擇9繼續(xù)操作運(yùn)用各種遍歷形式遍歷樹副菜單選擇0結(jié)束程序七附錄（源程序）#include <stdio.h>#include <malloc.h>#include <stdlib.h>/設(shè)置常量：#define MA

16、X_TREE_SIZE 100/一般樹的存儲結(jié)構(gòu)有以下幾種：雙親結(jié)點(diǎn)，孩子結(jié)點(diǎn)，孩子兄弟結(jié)點(diǎn)。本實(shí)驗(yàn)運(yùn)用到的是雙親結(jié)點(diǎn)和孩子兄弟結(jié)點(diǎn)。具體存儲結(jié)構(gòu)如下：/*樹的雙親表示結(jié)點(diǎn)結(jié)構(gòu)定義*/typedef struct int data; int parent; /雙親位置域PTNode;/*雙親表示法樹結(jié)構(gòu)*/typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和節(jié)點(diǎn)個數(shù)PTree;/*樹的孩子兄弟表示結(jié)點(diǎn)結(jié)構(gòu)定義*/typedef struct nodeint data;struct node *firstchild;struct n

17、ode *rightsib;BTNode,*BTree;/初始化樹(雙親表示法)void init_ptree(PTree *tree) tree->count=-1;/初始化樹結(jié)點(diǎn)(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/樹的先序遍歷(遞歸)void preorder(BTNode *T)if(T!=NULL)printf("%d ",T->data);preorder(T->firstchild);preorder

18、(T->rightsib);/樹的先序遍歷(非遞歸)void preorder2(PTree T)int i;for(i=0;i<T.count;i+)printf("%d ",T.nodei);/樹后序遍歷(遞歸)void inoeder(BTNode *T)if(T!=NULL)inoeder(T->firstchild);printf("%d ",T->data);inoeder(T->rightsib);/樹后序遍歷(非遞歸)void inoeder2(PTree T)int i;for(i=T.count-1;i&

19、gt;=0;i-)printf("%d ",T.nodei);/層次遍歷void level(PTree T)int i;for(i=0;i<T.count;i+)printf("%d ",T.nodei);/水平輸出二叉樹void PrintBTree(BTNode *root,int level) int i; if(root!=NULL) PrintBTree(root->rightsib,level+1); for(i=1;i<=8*level;i+) printf(" "); printf("-%

20、dn",root->data); PrintBTree(root->firstchild,level+1); /輸出樹void print_ptree(PTree tree) int i; printf(" 序號 結(jié)點(diǎn) 雙親n"); for(i=0;i<=tree.count;i+) printf("%8d%8d%8d",i,tree.nodei.data,tree.nodei.parent); printf("n"); /*用雙親表示法創(chuàng)建樹*/PTree CreatTree(PTree T)int i=

21、1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf("輸入第%d結(jié)點(diǎn):n",i);scanf("%d,%d",&fa,&ch);printf("n");p.data=ch;p.parent=fa;T.count+; T.nodeT.count.data = p.data; T.nodeT.count.parent = p.parent;printf("n");printf("創(chuàng)建的樹具體情況如下:n");print_ptree(T);ret

22、urn T;/*一般樹轉(zhuǎn)換成二叉樹*/BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;i<T.count;i+)pi=GetTreeNode(T.nodei.data);for(i=

23、1;i<T.count;i+)ip=&pi;is=&pj;while(T.nodei.parent!=is->data)j+;is=&pj;if(!(is->firstchild)is->firstchild=ip;ir=ip;elseir->rightsib=ip;ir=ip;Tree=&p0;return Tree;/*主菜單*/void Menu()printf("=主菜單=n");printf("*輸入1-以雙親法創(chuàng)建一棵一般樹*n"); printf("*輸入2-樹的先序遍

24、歷(遞歸)*n"); printf("*輸入3-樹的后序遍歷(遞歸)*n"); printf("*輸入4-樹的先序遍歷(非遞歸)*n"); printf("*輸入5-樹的后序遍歷(非遞歸)*n"); printf("*輸入6-層次序的非遞歸遍歷*n"); printf("*輸入0-退出程序*n"); printf("=n"); printf("請輸入執(zhí)行的指令:");/*副菜單*/void Menu2()printf("*副菜單*n&q

25、uot;);printf("*9-返回主菜單繼續(xù)操作*n");printf("*0-退出程序*n");/*主函數(shù)*/int main() int i=0,c1,c2; PTree T; BTNode *Tree; init_ptree(&T); loop: Menu();scanf("%d",&c1); switch(c1) case 1: printf("建立一般樹,依次輸入各個結(jié)點(diǎn)情況:n"); printf("輸入結(jié)點(diǎn)方式:雙親數(shù)據(jù),整型數(shù)據(jù)(第一個結(jié)點(diǎn)雙親數(shù)據(jù)為-1,最后以-1,-1結(jié)束)n例子:-1,1 1,