1、數據結構實驗報告院系_ 專業 _姓名_林楨曦_ 學號_ _ _級 _班 _年_月_日1 實驗題目(1) 二叉排序樹的基本操作(2) 二叉樹和Huffman樹2 需求分析 （1）編寫二叉排序樹的基本操作函數，調用上述函數實現初始化，插入元素，查找元素，刪除元素等操作。(2)編寫二叉樹的基本操作函數，用遞歸方法分別實現先序，中序和后序遍歷二叉樹。3概要設計ADT tree 數據對象：D=ai|aiIntegerSet,i=0,1,2,n,n0 結構關系：R=|ai,ai+1 D 基本操作： SearchNode(TREE *tree,int key,TREE *pkpt,TREE *kpt) 操作

2、前提：tree是一個已初始化的二叉樹 操作結果：查找樹根結點，鍵值賦給key，并返回key結點的父節點指針和key結點的指針 InsertNode(TREE *tree,int key) 操作前提：tree是一個已初始化的二叉樹 操作結果：將key值插入tree中 DeleteNode(TREE *tree,int key) 操作前提：二叉樹tree已存在 操作結果：將二叉樹中的元素值為key的元素刪除 OutputTree(TREE *tree) 操作前提：二叉樹tree已存在 操作結果：將二叉樹中的元素值輸出 （1） 本程序包含7個函數： 主函數main() 進棧函數pop() 出棧函數p

3、ush() 查找函數SearchNode() 插入函數InsertNode() 刪除函數 DeleteNode()顯示函數 OutputTree()各函數間調用關系如下：主函數調用其他函數mainInsLinkListDelLinkListLocLinkLis（2） 主函數的偽碼main() 定義各個變量；輸入結點個數；For循環輸入元素值；輸出元素值；輸入刪除的元素值；顯示元素值； ADT tree 數據對象：D=ai|aiIntegerSet,i=0,1,2,n,n0 結構關系：R=|ai,ai+1 D 基本操作： CreateBiTree(BiTree &T) 操作前提：T是一個已初始化

4、的二叉樹 操作結果：創建一顆二叉樹 re_PreOrder(BiTree &tree) 操作前提：tree是一個已初始化的二叉樹 操作結果：先序遍歷，遞歸方法 re_MidOrder(BiTree &tree) 操作前提：二叉樹tree已存在 操作結果：中序遍歷，遞歸方法 re_PostOrder(BiTree &tree) 操作前提：二叉樹tree已存在 操作結果：后序遍歷，遞歸方法 本程序包含5個函數： 主函數main() 創建二叉樹函數CreateBiTree() 先序函數re_PreOrder() 中序函數 re_MidOrder() 后序函數re_PostOrder()各函數間調用關

5、系如下：主函數調用其他函數主函數的偽碼main() 定義變量BiTree T;調用CreateBiTree函數；調用 re_PreOrder函數；調用re_MidOrder函數； 調用re_PostOrder函數； 4詳細設計（1） 類型定義typedef struct treeint data;struct tree *lchild;struct tree *rchild;TREE;typedef struct stackTREE *t;int flag;struct stack *link;STACK;typedef struct BiTNodechar data;struct BiTNo

6、de *lchild,*rchild;*BiTree;5調試分析調試時遇到空指針問題，部分值未賦值。6 使用說明7.1首先先輸入結點元素個數，然后按要求輸入元素值，屏幕顯示構造后的樹結構，之后屏幕提示要刪除的元素，按要求輸入之后，屏幕顯示刪除成功，并顯示樹結構。7.2 首先按要求輸入二叉樹的元素值，然后程序調用函數在屏幕顯示先序，中序，后序排序的序列。7 測試結果8. 參考文獻數據結構9附錄#include#include#includetypedef struct treeint data;struct tree *lchild;struct tree *rchild;TREE;typede

7、f struct stackTREE *t;int flag;struct stack *link;STACK;void push(STACK *top,TREE *tree)STACK *p;p=(STACK *)malloc(sizeof(STACK);p-t=tree;p-link=*top;*top=p;void pop(STACK *top,TREE *tree)STACK *p;if(*top=NULL)*tree=NULL;else*tree=(*top)-t;p=*top;*top=(*top)-link;free(p);void SearchNode(TREE *tree,i

8、nt key,TREE *pkpt,TREE *kpt)*pkpt=NULL;*kpt=tree;while(*kpt!=NULL)if(*kpt)-data=key)return;*pkpt=*kpt;if(keydata)*kpt=(*kpt)-lchild;else*kpt=(*kpt)-rchild;int InsertNode(TREE *tree,int key)TREE *p,*q,*r;SearchNode(*tree,key,&p,&q);if(q!=NULL)return 1;if(r=(TREE *)malloc(sizeof(TREE)=NULL) return -1;

9、r-data=key;r-lchild=r-rchild=NULL;if(p=NULL)*tree=r;elseif(p-datakey)p-lchild=r;elsep-rchild=r;return 0;int DeleteNode(TREE *tree,int key)TREE *p,*q,*r;SearchNode(*tree,key,&p,&q);if(q=NULL)if(q-lchild=NULL)*tree=q-rchild;else*tree=q-lchild;r=q-lchild;while(r-rchild!=NULL)r=r-rchild;r-rchild=q-rchil

10、d;elseif(q-lchild=NULL)if(q=p-lchild)p-lchild=q-rchild;elsep-rchild=q-rchild;elser=q-lchild;while(r-rchild!=NULL)r=r-rchild;r-rchild=q-rchild;if(q=p-lchild)p-lchild=q-lchild;elsep-rchild=q-rchild;free(q);return 0;void OutputTree(TREE *tree)STACK *top;int d=0,n=0,m=0;top=NULL;while(tree!=NULL|top!=NU

11、LL)while(tree!=NULL)push(&top,tree);top-flag=+d;if(mlchild;if(top!=NULL)d=top-flag;n+;pop(&top,&tree);printf(%d,tree-data);fflush(stdout);tree=tree-rchild;void main()TREE *t;int i,n,m;t=NULL;printf(請輸入樹結點個數：); scanf(%d,&m);printf(請輸入樹結點元素：);for(i=0;im;i+) scanf(%d,&n);InsertNode(&t,n);printf(樹結構為：n)

12、;OutputTree(t);printf(n請輸入要刪除的樹結點元素：);scanf(%d,&i);DeleteNode(&t,i);printf(刪除成功，樹結構為：n);OutputTree(t);printf(n);#include#includetypedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;*BiTree;void CreateBiTree(BiTree &T)char ch; scanf(%c,&ch); if(ch= )T=NULL; else BiTNode *p=(BiTNode *)malloc

13、(sizeof(BiTNode); T=p; T-data=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); void re_PreOrder(BiTree &tree)if(tree) printf(%c ,tree-data); re_PreOrder(tree-lchild); re_PreOrder(tree-rchild); int re_MidOrder(BiTree &tree)if(tree) re_MidOrder(tree-lchild); if(tree-data) printf(%c ,tree-data);re_MidOrder(tree-rchild);return 1;else return 0;int re_PostOrder(BiTree &tree)if(tree) re_PostOrder(tree-lchild); re_PostOrder(tree-rchi