《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹(shù)與二叉樹(shù)的轉(zhuǎn)換(共14頁(yè)).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之-樹(shù)與二叉樹(shù)的轉(zhuǎn)換(共14頁(yè)).doc（14頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 綱要一 程序設(shè)計(jì)要求與目的二 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)三 算法設(shè)計(jì)（流程圖）四 詳細(xì)設(shè)計(jì)（源代碼）五 調(diào)試與分析六 實(shí)驗(yàn)總結(jié)七 參考文獻(xiàn)第一章 程序設(shè)計(jì)要求與目的題目：樹(shù)與二叉樹(shù)的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹(shù)的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)，應(yīng)包含建樹(shù)的實(shí)現(xiàn)。第二章 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)引入頭文件：#include <stdio.h>#include <malloc.h>#include <stdlib.h>設(shè)置常量：#define MAX_TREE_SIZE 100一般樹(shù)的存儲(chǔ)結(jié)構(gòu)有以下幾種：雙親結(jié)點(diǎn)，孩子結(jié)點(diǎn)，孩子兄弟結(jié)點(diǎn)。

2、本實(shí)驗(yàn)運(yùn)用到的是雙親結(jié)點(diǎn)和孩子兄弟結(jié)點(diǎn)。具體存儲(chǔ)結(jié)構(gòu)如下：/*樹(shù)的雙親表示結(jié)點(diǎn)結(jié)構(gòu)定義*/typedef struct int data; int parent; /雙親位置域PTNode;/*雙親表示法樹(shù)結(jié)構(gòu)*/typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和節(jié)點(diǎn)個(gè)數(shù)PTree;/*樹(shù)的孩子兄弟表示結(jié)點(diǎn)結(jié)構(gòu)定義*/typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;第三章 算法設(shè)計(jì)（流程圖）流程圖：退出

3、程序?qū)哟伪闅v開(kāi)始雙親法建樹(shù)按照格式輸入各個(gè)結(jié)點(diǎn)輸出樹(shù)的結(jié)點(diǎn)情況1主菜單前序遍歷（遞歸）后序遍歷（遞歸）前序遍歷（非遞歸）后序遍歷（非遞歸）輸出遍歷結(jié)果副菜單退出程序23540069第四章 詳細(xì)設(shè)計(jì)（源代碼）詳細(xì)設(shè)計(jì)共有以下函數(shù)的實(shí)現(xiàn)：樹(shù)的初始化函數(shù)（雙親法和孩子結(jié)點(diǎn)法兩種），建樹(shù)函數(shù)，輸出樹(shù)函數(shù)，樹(shù)的前序遍歷函數(shù)（遞歸和非遞歸兩種），樹(shù)的后序遍歷函數(shù)(遞歸和非遞歸兩種）,樹(shù)的層次遍歷函數(shù)，一般樹(shù)和二叉樹(shù)的轉(zhuǎn)換函數(shù)。主菜單和副菜單。主函數(shù)。具體代碼如下：/初始化樹(shù)(雙親表示法)void init_ptree(PTree *tree) tree->count=-1;/初始化樹(shù)結(jié)點(diǎn)(孩子兄弟表

4、示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/樹(shù)的前序遍歷(遞歸)void preorder(BTNode *T)if(T!=NULL)printf("%d ",T->data);preorder(T->firstchild);preorder(T->rightsib);/樹(shù)的前序遍歷(非遞歸)void preorder2(PTree T)int i;for(i=0;i<T.count;i+)printf("%d &q

5、uot;,T.nodei);/樹(shù)后序遍歷(遞歸)void inoeder(BTNode *T)if(T!=NULL)inoeder(T->firstchild);printf("%d ",T->data);inoeder(T->rightsib);/樹(shù)后序遍歷(非遞歸)void inoeder2(PTree T)int i;for(i=T.count-1;i>=0;i-)printf("%d ",T.nodei);/層次遍歷void level(PTree T)int i;for(i=0;i<T.count;i+)print

6、f("%d ",T.nodei);/水平輸出二叉樹(shù)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("-%dn",root->data); PrintBTree(root->firstchild,level+1); /輸出樹(shù)void print_ptree(PTree tree) i

7、nt i; printf(" 序號(hào) 結(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)建樹(shù)*/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",&

8、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)建的樹(shù)具體情況如下:n");print_ptree(T);return T;/*一般樹(shù)轉(zhuǎn)換成二叉樹(shù)*/BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;i

9、p=(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=1;i<T.count;i+)ip=&pi;is=&pj;while(T.nodei.parent!=is->data)j+;is=&pj;if(!(is->

10、firstchild)is->firstchild=ip;ir=ip;elseir->rightsib=ip;ir=ip;Tree=&p0;return Tree;/*主菜單*/void Menu()printf("=主菜單=n");printf("*輸入1-以雙親法創(chuàng)建一棵一般樹(shù)*n"); printf("*輸入2-樹(shù)的前序遍歷(遞歸)*n"); printf("*輸入3-樹(shù)的后序遍歷(遞歸)*n"); printf("*輸入4-樹(shù)的前序遍歷(非遞歸)*n"); print

11、f("*輸入5-樹(shù)的后序遍歷(非遞歸)*n"); printf("*輸入6-層次序的非遞歸遍歷*n"); printf("*輸入0-退出程序*n"); printf("=n"); printf("請(qǐng)輸入執(zhí)行的指令:");/*副菜單*/void Menu2()printf("*副菜單*n");printf("*9-返回主菜單繼續(xù)操作*n");printf("*0-退出程序*n");/*主函數(shù)*/void main() int i=0,c1,c2; PTree T; BTNode *Tree; init_ptree(&T); loop: Menu();scanf("%d",&c1); switch(c1) case 1: printf("建立一般樹(shù),依次輸入各個(gè)結(jié)點(diǎn)情況:n"); printf("輸入結(jié)點(diǎn)方式:雙親數(shù)據(jù),整型數(shù)據(jù)(第一個(gè)結(jié)點(diǎn)雙親數(shù)據(jù)為-1,最后以-1,-1結(jié)束)n例子:-1,1 1,3n");T=CreatTree(T);Tree=change(T);p