2022年数据结构二叉排序树的基本操作参考 .pdf

数据结构实验报告院系 _ 专业_ 姓名 _林桢曦 _ 学号 _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 *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 个函数：主函数 main() 进栈函数 pop() 出栈函数 push() 查找函数 SearchNode() 插入函数 InsertNode() 删除函数DeleteNode() 显示函数OutputTree() 各函数间调用关系如下：主函数调用其他函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义2 （2）主函数的伪码main() 定义各个变量；输入结点个数；For 循环输入元素值；输出元素值；输入删除的元素值；显示元素值； 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) 操作前提：二叉树tree 已存在操作结果：后序遍历，递归方法 本程序包含5个函数：主函数 main() 创建二叉树函数CreateBiTree() 先序函数 re_PreOrder() 中序函数re_MidOrder() 后序函数 re_PostOrder() 各函数间调用关系如下：主函数调用其他函数主函数的伪码main() 定义变量 BiTree T; 调用 CreateBiTree 函数；调用re_PreOrder 函数；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义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,*rchild; *BiTree; 5调试分析调试时遇到空指针问题，部分值未赋值。6使用说明7.1 首先先输入结点元素个数，然后按要求输入元素值，屏幕显示构造后的树结构，之后屏幕提示要删除的元素，按要求输入之后，屏幕显示删除成功，并显示树结构。7.2 首先按要求输入二叉树的元素值，然后程序调用函数在屏幕显示先序，中序，后序排序的序列。7测试结果7.1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义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; 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 *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(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; 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; 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-rchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 福建师范大学物光院计算机教学辅导讲义7 else if(q-lchild=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|top!=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; 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 #include 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 *)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-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) printf(%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 页 - - - - - - - - -