9-38.c

数据结构168个实验程序,很全面

#include <stdlib.h>
#define MAX  100
#define NULL 0
#include "stdio.h"
typedef struct tree
{
  int data;
  struct  tree *lchild,*rchild;
  }Btree;
void insert(Btree * * b,Btree *s)
{
  if(* b==NULL) *b=s;
  else if(s->data<(*b)->data)
  insert(&((*b)->lchild),s);

  else if(s->data>(*b)->data)

  insert(&((*b)->rchild),s);
     }

 Btree *creat(Btree *b,int * r,int m)
{
  int i;
  Btree *s;
  b=NULL;
  for(i=0;i<m;i++)
  {
  s=(Btree*)malloc(sizeof(Btree));
  s->data=r[i];
  s->lchild=NULL;
  s->rchild=NULL;
  insert(&b,s);
  }
  return(b);
  }
 void insert_key(Btree * p1,Btree * p2)
 {
	 if (p2->data>p1->data)
	 {
		 if (!p1->rchild) p1->rchild=p2;
		 else insert_key(p1->rchild,p2);
	 }
	 else if(p2->data<p1->data)
	 {
		 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_Merge(T,S->rchild);
  insert_key(T,S);
}

void disp(Btree *b)
{
    Btree *stack[100],*p;
    int level[100],top,n,i;
    if(b!=NULL)
    {
      printf(" binary tree is:\n");
      top=1;
      stack[top]=b;

      level[top]=3;
      while(top)
      {
	 p=stack[top];
	 n=level[top];
	 for(i=1;i<=n;i++)
	   printf(" ");
	   printf("%d\n",p->data);
	   top--;
	   if(p->rchild!=NULL)
	   {
	   top++;
	   stack[top]=p->rchild;
	   level[top]=n+3;
	   }
	   if(p->lchild!=NULL)
	   {
	     top++;
	     stack[top]=p->lchild;
	     level[top]=n+3;
	     }
	    }
	  }
	}


main()
 {
   int r1[20];
   int r2[20];
   int i,r1len,r2len,x;
   Btree *p1,*p2;
   printf("输入二叉排序树A(输入0结束):");
   for (i=0;i<20;i++)
   {
	   scanf("%d",&x);
	   if (x==0) break;
	   else r1[i]=x;
   }
   r1len=i;
   printf("输入二叉排序树B(输入0结束):");
   for (i=0;i<20;i++)
   {
	   scanf("%d",&x);
	   if (x==0) break;
	   else r2[i]=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);
   printf(" MergeTree is:\n");
   BSTree_Merge(p1,p2);
   disp(p1);
   }