《2022年数据结构二叉排序树的基本操作参考》由会员分享,可在线阅读,更多相关《2022年数据结构二叉排序树的基本操作参考(10页珍藏版)》请在金锄头文库上搜索。
1、数据结构实验报告院系 _ 专业_ 姓名 _林桢曦 _ 学号 _106052010235_ 电话 _ _级_班_年_月_日1实验题目(1)二叉排序树的基本操作(2)二叉树和Huffman 树2需求分析(1)编写二叉排序树的基本操作函数,调用上述函数实现初始化,插入元素,查找元素,删除元素等操作。(2)编写二叉树的基本操作函数,用递归方法分别实现先序,中序和后序遍历二叉树。3概要设计7.1ADT tree 数据对象: D=ai|aiIntegerSet,i=0,1,2,n,n 0 结构关系: R=|ai,ai+1 D 基本操作:SearchNode(TREE *tree, int key,TREE
2、 *pkpt,TREE *kpt) 操作前提: 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 个函数:
3、主函数 main() 进栈函数 pop() 出栈函数 push() 查找函数 SearchNode() 插入函数 InsertNode() 删除函数DeleteNode() 显示函数OutputTree() 各函数间调用关系如下:主函数调用其他函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义2 (2)主函数的伪码main() 定义各个变量;输入结点个数;For 循环输入元素值;输出元素值
4、;输入删除的元素值;显示元素值; 7.2 ADT tree 数据对象: D=ai|aiIntegerSet,i=0,1,2,n,n 0 结构关系: R=|ai,ai+1 D 基本操作:CreateBiTree(BiTree &T) 操作前提: T 是一个已初始化的二叉树操作结果:创建一颗二叉树re_PreOrder(BiTree &tree) 操作前提: tree 是一个已初始化的二叉树操作结果:先序遍历,递归方法re_MidOrder(BiTree &tree) 操作前提:二叉树tree 已存在操作结果:中序遍历,递归方法re_PostOrder(BiTree &tree) 操作前提:二叉树
5、tree 已存在操作结果:后序遍历,递归方法 本程序包含5个函数:主函数 main() 创建二叉树函数CreateBiTree() 先序函数 re_PreOrder() 中序函数re_MidOrder() 后序函数 re_PostOrder() 各函数间调用关系如下:主函数调用其他函数主函数的伪码main() 定义变量 BiTree T; 调用 CreateBiTree 函数;调用re_PreOrder 函数;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 10 页 -
6、- - - - - - - - 福建师范大学物光院计算机教学辅导讲义3 调用re_MidOrder 函数;调用 re_PostOrder 函数; 4详细设计(1)7.1 类型定义typedef struct tree int data; struct tree *lchild; struct tree *rchild; TREE; typedef struct stack TREE *t; int flag; struct stack *link; STACK; 7.2 类型定义typedef struct BiTNode char data; struct BiTNode *lchild,*
7、rchild; *BiTree; 5调试分析调试时遇到空指针问题,部分值未赋值。6使用说明7.1 首先先输入结点元素个数,然后按要求输入元素值,屏幕显示构造后的树结构,之后屏幕提示要删除的元素,按要求输入之后,屏幕显示删除成功,并显示树结构。7.2 首先按要求输入二叉树的元素值,然后程序调用函数在屏幕显示先序,中序,后序排序的序列。7测试结果7.1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅
8、导讲义4 7.2 8. 参考文献数据结构9附录7.1 #include #include #include typedef struct tree int data; struct tree *lchild; struct tree *rchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义5 TREE; typedef struct stack TREE *t; int flag;
9、 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, int key,TREE
10、*pkpt,TREE *kpt) *pkpt=NULL; *kpt=tree; while(*kpt!=NULL) if(*kpt)-data=key) return; *pkpt=*kpt; if(keydata) *kpt=(*kpt)-lchild; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义6 *kpt=(*kpt)-rchild; int InsertNode(TR
11、EE *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; r-data=key; r-lchild=r-rchild=NULL; if(p=NULL) *tree=r; else if(p-datakey) p-lchild=r; else p-rchild=r; return 0; int DeleteNode(TREE *tree,int key) TREE *p,*q,*r; Se
12、archNode(*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-rchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义7 else if(q-lch
13、ild=NULL) if(q=p-lchild) p-lchild=q-rchild; else p-rchild=q-rchild; else r=q-lchild; while(r-rchild!=NULL) r=r-rchild; r-rchild=q-rchild; if(q=p-lchild) p-lchild=q-lchild; else p-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|t
14、op!=NULL) while(tree!=NULL) push(&top,tree); top-flag=+d; if(mlchild; if(top!=NULL) d=top-flag; n+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义8 pop(&top,&tree); printf(%d,tree-data); fflush(stdout); tree=tree-rchild
15、; 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); OutputTree(t); printf(n 请输入要删除的树结点元素:); scanf(%d,&i); DeleteNode(&t,i); printf( 删除成功,树结构为:n); OutputTree(t); printf(n); 7.2 #include #inclu
16、de typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; *BiTree; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义9 void CreateBiTree(BiTree &T) char ch; scanf(%c,&ch); if(ch= )T=NULL; else BiTNode *p=(BiTNode
17、 *)malloc(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
18、-data); re_MidOrder(tree-rchild); return 1; else return 0; int re_PostOrder(BiTree &tree) if(tree) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义10 re_PostOrder(tree-lchild); re_PostOrder(tree-rchild); if(tree-data) pri
19、ntf(%c ,tree-data); return 1; else return 0; void main() BiTree T; printf( 构造一个二叉树:); CreateBiTree(T); printf( 先序序列为 :); re_PreOrder(T); printf(n 中序序列为 :); re_MidOrder(T); printf(n 后序序列为 :); re_PostOrder(T); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 10 页 - - - - - - - - -