数据结构07二叉排序树的基本操作

1、?数据结构?实验报告院系_ 专业 _姓名_林桢曦_ 学号_ _ _级 _班 _年_月_日1 实验题目(1) 二叉排序树的根本操作(2) 二叉树和Huffman树2 需求分析 1编写二叉排序树的根本操作函数，调用上述函数实现初始化，插入元素，查找元素，删除元素等操作。(2)编写二叉树的根本操作函数，用递归方法分别实现先序，中序和后序遍历二叉树。3概要设计ADT tree 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 结构关系：R=<ai,ai+1>|ai,ai+1 D 根本操作： SearchNode(TREE *tree,int key,TREE *pkp

2、t,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()

3、进栈函数pop() 出栈函数push() 查找函数SearchNode() 插入函数InsertNode() 删除函数 DeleteNode()显示函数 OutputTree()各函数间调用关系如下：主函数调用其他函数mainInsLinkListDelLinkListLocLinkLis（2） 主函数的伪码main() 定义各个变量；输入结点个数；For循环输入元素值；输出元素值；输入删除的元素值；显示元素值； ADT tree 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 结构关系：R=<ai,ai+1>|ai,ai+1 D 根本操作： CreateB

4、iTree(BiTree &T) 操作前提：T是一个已初始化的二叉树 操作结果：创立一颗二叉树 re_PreOrder(BiTree &tree) 操作前提：tree是一个已初始化的二叉树 操作结果：先序遍历，递归方法 re_MidOrder(BiTree &tree) 操作前提：二叉树tree已存在 操作结果：中序遍历，递归方法 re_PostOrder(BiTree &tree) 操作前提：二叉树tree已存在 操作结果：后序遍历，递归方法 本程序包含5个函数： 主函数main() 创立二叉树函数CreateBiTree() 先序函数re_PreOrder(

5、) 中序函数 re_MidOrder() 后序函数re_PostOrder()各函数间调用关系如下：主函数调用其他函数主函数的伪码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;STAC

6、K;typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;*BiTree;5调试分析调试时遇到空指针问题，局部值未赋值。6 使用说明7.1首先先输入结点元素个数，然后按要求输入元素值，屏幕显示构造后的树结构，之后屏幕提示要删除的元素，按要求输入之后，屏幕显示删除成功，并显示树结构。7.2 首先按要求输入二叉树的元素值，然后程序调用函数在屏幕显示先序，中序，后序排序的序列。7 测试结果8. 参考文献数据结构9附录#include<stdio.h>#include<malloc.h>#include&l

7、t;conio.h>typedef struct treeint data;struct tree *lchild;struct tree *rchild;TREE;typedef 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(

8、*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(key<(*kpt)->data)*kpt=(*kpt)->lchild;else*kpt=(*kpt)->rchild;int Insert

9、Node(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;elseif(p->data>key)p->lchild=r;elsep->rchild=r;return 0;int DeleteNode(TREE *tree

10、,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;elseif(q->lchild=NULL)if(q=p->lchild)p->lchild=q->rchild;elsep->rchild=q

11、->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!=NULL)while(tree!=NULL)push(

12、&top,tree);top->flag=+d;if(m<d)m=d;tree=tree->lchild;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(&qu

13、ot;请输入树结点元素：");for(i=0;i<m;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");#include<stdio

14、.h>#include<stdlib.h>typedef 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(sizeof(BiTNode); T=p; T->data=ch; CreateBiTree(T->lchild); Cr

15、eateBiTree(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->rchild); if(tree->data) printf(&quo