a13-5二叉排序树实验报告

1、实验题目：试写一算法，先将两棵二叉排序树合并为一棵二叉排序树。一，需求分析1， 建立一个二叉树，然后排序。2， 本程序可以将两个二叉排序树合并一个二叉排序树，然后输出。二，概要设计1， 抽象数据类型二叉树的定义如下：ADT Btree数据对象 D:D 是具有相同特性的数据元素的集合；数据关系:R如 D=,则 R=,称 Btree 为空二叉树；如 D，则 R=H;基本操作 p;InitBitree(&T);操作结果：构造空二叉树。DestroyTree(&T)初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T. CreateBitree(&definition);初始条件：definitio

2、n 给出二叉树 T 的定义；操作结果：按 definition 构造二叉树。 InserChild(T,p,LR,c);初始条件：二叉树 T 存在，p 指向T 中某个结点，LR 为 0 或 1，非空二叉树c 与 T 不相交且右子树为空。操作结果：根据 LR 为 0 或 1，有左或右子树则成为c 的右子树c 为 T 中 p 所指结点的左或右子树。P 所指结点的原三，详细设计主程序：#include #define MAX100#define NULL 0#include stdio.htypedef struct treedata;structtree *lchild,*rchild;Btree

3、;void insert(Btree * * b,Btree *s)if(* b=NULL) *b=s;else if(s-datadata) insert(&(*b)-lchild),s);else if(s-data(*b)-data)insert(&(*b)-rchild),s);Btree *creat(Btree *b,* r,m)i; Btree *s; b=NULL;for(i=0;idata=ri;s-lchild=NULL; s-rchild=NULL; insert(&b,s);return(b);void insert_key(Btree * p1,Btree * p2)

4、if (p2-datap1-data)if (!p1-rchild) p1-rchild=p2; else insert_key(p1-rchild,p2);else if(p2-datadata)if(!p1-lchild) p1-lchild=p2; else insert_key(p1-lchild,p2);p2-lchild=NULL;p2-rchild=NULL;void BSTree_Merge(Btree * T,Btree * S)/把二叉排序树S 合并到 T 中if(S-lchild) BSTree_Merge(T,S-lchild); if(S-rchild) BSTree

5、_Merge(T,S-rchild); insert_key(T,S);void disp(Btree *b)Btree *stack100,*p; level100,top,n,i;if(b!=NULL)prf( binary tree is:n); top=1;stacktop=b;leveltop=3; while(top)p=stacktop; n=leveltop; for(i=1;idata); top-;if(p-rchild!=NULL)top+;stacktop=p-rchild; leveltop=n+3;if(p-lchild!=NULL)top+;stacktop=p-

6、lchild; leveltop=n+3;main()r120;r220;i,r1len,r2len,x; Btree *p1,*p2;prf(输入二叉排序树 A(输入 0 结束):);for (i=0;i20;i+)scanf(%d,&x); if (x=0) break; else r1i=x;r1len=i;prf(输入二叉排序树 B(输入 0 结束):); for (i=0;i20;i+)scanf(%d,&x); if (x=0) break; else r2i=x;r2len=i;p1=(Btree *)malloc(sizeof(Btree); p2=(Btree *)malloc(sizeof(Btree); p1=creat(p1,r1,r1len);disp(p1); p2=creat(p2,r2,r2len); disp(p2);prf( MergeTree is:n); BSTree_Merge(p1,p2); disp(p1);三，输入二叉排序树 A(输入 0 结束)；4 5 2 3 0输入二叉排序树 B (输入 0 结束)；