二叉排序树的实现er.cpp

这是数据结构二叉排序树的算法,可能不是比较好,但对于初学者来说应该还是算可以的.

 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> // malloc()等
 #include<limits.h> // INT_MAX等
 #include<stdio.h> // EOF(=^Z或F6),NULL
 #include<stdlib.h> // atoi()
 #include<io.h> // eof()
 #include<math.h> // floor(),ceil(),abs()
 #include<process.h> // exit()
 #include<iostream.h> // cout,cin
 typedef int KeyType;
 // 函数结果状态代码
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 // #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

  #define   NULL   0   
 #define EQ(a,b) ((a)==(b))
 #define LT(a,b) ((a)<(b))
 #define LQ(a,b) ((a)<=(b))

    
    
  typedef   struct   node                 /*二叉树结构定义*/   
  {   int   data;   
      struct   node   *left,*right;   
  } BiTNode,*BiTree;   
    
  BiTNode  *bt;   
    
   void   insert(BiTNode   **b,BiTNode   *s)         /*排序二叉树中插入节点*/   
  {   
          if   ((*b)   ==   NULL)   (*b)   =   s;   
          else   if   (s->data==(*b)->data)   return;   
          else   if   (s->data<(*b)->data)   insert((&(*b)->left),s);   
          else   if   (s->data>(*b)->data)   insert((&(*b)->right),s);   
  }  
    
  void   *creat(BiTree  b)         /*建立排序二叉树*/   
  {   
          int   x;   
          BiTree  s;   
          b=NULL;                               /*初始化二叉数*/   
          scanf("%d",&x);   
          s=(BiTree)malloc(sizeof(BiTNode));   
    
          while   (x!=-1)                   /*反复读入节点,直至-1结束*/   
          {   
                  s->data=x;   
                  s->left=NULL;   
                  s->right=NULL;   
                  insert(&bt,s);   
                  scanf("%d",&x);         /*节点插入排序二叉树中*/           
                  s=(BiTree )malloc(sizeof(BiTNode));   
          }   
  return   NULL;   
      }   
    
  void   inorder(BiTree  p)         /*中序递归打印*/   
    {   if   (p!=NULL)   
    
			{         
	        inorder(p->left);   
            printf("%d   ",p->data);   
            inorder(p->right);   
			}   
    } 
  
  //-----------------------------------------------------------
   void PreOrderTraverse(BiTree  b)
 { // ----------------------------------------初始条件: 二叉树T存在,Visit是对结点操作的应用函数。------------易明
   // ----------------------------------------操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次
   if(b) // ----------------------------------T不空
   {
     printf("%d ",b->data); // ----------------------先访问根结点
     PreOrderTraverse(b->left); // ----再先序遍历左子树
     PreOrderTraverse(b->right); // ---最后先序遍历右子树
   }
 }


   void exchange(BiTree b)

/*本算法采用后根遍历递归访问的方法，交换每一个结点的左右子树。*/

{   BiTree  p;
	if (b)            /*非空*/

  {
   exchange(b->left); /*交换左子树所有结点指针*/
   exchange(b->right); /*交换右子树所有结点指针*/
   p=b->left;           /*交换根结点左右指针*/
   b->left=b->right;  
   b->right =p;

}

}



   BiTree SearchBST(BiTree &b,KeyType key)
 { // 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，
   // 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。算法9.5(a)
   if((!b)||EQ(key,b->data))
     return b; // 查找结束
   else if LT(key,b->data) // 在左子树中继续查找
     return SearchBST(b->left,key);
   else
     return SearchBST(b->right,key); // 在右子树中继续查找
 }

 void SearchBST(BiTree &b,KeyType key,BiTree f,BiTree &p,Status &flag) // 算法9.5(b)改
 { // 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找
   // 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上
   // 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL
   if(!b) // 查找不成功
   {
     p=f;
     flag=FALSE;
   }
   else if EQ(key,b->data) //  查找成功
   {
     p=b;
     flag=TRUE;
   }
   else if LT(key,b->data)
     SearchBST(b->left,key,b,p,flag); // 在左子树中继续查找
   else
     SearchBST(b->right,key,b,p,flag); //  在右子树中继续查找
 }


 Status InsertBST(BiTree &b, KeyType e)
 { // 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，
   // 否则返回FALSE。算法9.6(改)
   BiTree p,s;
   Status flag;
   SearchBST(b,e,NULL,p,flag);
   if(!flag) // 查找不成功
   {
     s=(BiTree)malloc(sizeof(BiTNode));
     s->data=e;
     s->left=s->right=NULL;
     if(!p)
       b=s; // 被插结点*s为新的根结点
     else if LT(e,p->data)
       p->left=s; // 被插结点*s为左孩子
     else
       p->right=s; // 被插结点*s为右孩子
     return TRUE;
   }
   else
     return FALSE; // 树中已有关键字相同的结点，不再插入
 }

    
  main()   

  {      int m,n; 
          BiTree q;
	      printf("请输入你的值，并以-1结束！\n"); 
          creat(bt);  
		  printf("中序递归遍历为:\n");
          inorder(bt);  /*中序打印*/  
		  printf("\n先序递归遍历为:\n");
		  PreOrderTraverse(bt);
		  printf("交换左右结点后，二叉树为:\n");
          exchange(bt);
		  inorder(bt);//中序递归遍历
		  printf("输入你要查找的元素!\n");
		  scanf("%d",&m);
		  q=SearchBST(bt,m);
		  if(q)
   {
     printf("表中存在此值。");
     printf("\n");
   }
   else
     printf("表中不存在此值\n");
   printf("插入一个值:\n");
   scanf("%d",&n);
   InsertBST(bt, n);
   PreOrderTraverse(bt);
          return   0;   
  }