数据结构 二叉排序树

二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树:
   如果它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
   如果它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

      #include <stdio.h>
      #include <stdlib.h>
      #define TRUE 1
      #define FALSE 0
      #define OVERFLOW -2
      typedef int TElemType;
      typedef struct BiTNode
      {
      	TElemType data;
     	struct BiTNode *lchild,*rchild;
      }BiTNode,*BiTree;
      /****************二叉排序树的查找*******************
      参数说明：
       T 二叉排序树
       key 待查找的关键字
       f 指向T的双亲
       p 查找成功则指向该关键字的结点，返回TRUE，
       失败则指向查找路径的最后一个结点，返回FALSE
      ****************************************************/
      int SearchBST(BiTree T, TElemType key, BiTree f, BiTree &p)
      {
     	if (!T)
      	{//查找失败
      		p = f;
     		return FALSE;
      	}
     	else if(key == T->data)
      	{//查找成功
      		p = T;
     		return TRUE;
      	}
     	else if (key < T->data)
      	{//关键字小于当前结点的值，则查找其左子树
      		SearchBST(T->lchild,key, T, p);
      	}
     	else
      	{//关键字大于当前结点的值，则查找其右子树
      		SearchBST(T->rchild,key, T, p);
      	}
      }
      /****************二叉排序树的插入*******************
      二叉排序树的中序遍历是一个有序序列
      参数说明：
       T 二叉排序树
       key 待插入的关键字
       插入成功返回TRUE，失败返回FALSE
      ****************************************************/
      int InsertBST(BiTree &T, TElemType key)
      {
      	BiTree p,s;
     	if (!SearchBST(T,key,NULL,p))
      	{//如果该二叉排序树没有该关键字则插入
      		s = (BiTree)malloc(sizeof(BiTNode));
     		if (!s)
      		{
     			exit(OVERFLOW);
      		}
      		s->data = key;
      		s->lchild = NULL;
      		s->rchild = NULL;   //插入新的结点
     		if (!p)
      		{//如果当前是一棵空树
      			T = s;   //插入s为新的根结点
      		}
     		else if (key < p->data)
      		{//关键字小则为其左子树
      			p->lchild = s;
      		}
     		else
      		{//关键字大则为其右子树
      			p->rchild = s;
      		}
     		return TRUE;
      	}
     	else
      	{//插入失败，即二叉树包含有该关键字的结点
     		return FALSE;
      	}
      }
      /****************二叉排序树的删除*******************
      函数int Delete(BiTree &p);p是待删除的结点，并整理其左右子树
      函数int DeleteBST(BiTree &T, int key)删除值为key的结点
      ****************************************************/
      /*
      int Delete(BiTree &p)
      {
       BiTree q,s;
       if (p->rchild == NULL)
       {//如果右子树为空，则直接拼接左子树
       q = p;
       p = p->lchild;
       free(q);
       }
       else if (p->lchild == NULL)
       {//如果左子树为空，则直接拼接右子树
       q = p;
       p = p->rchild;
       free(q);
       }
       else
       {//左右子树均不为空的情况,找到其中序序列的直接前驱
       q = p;
       s = p->lchild;
       while (s->rchild)
       {//转左，然后向右到尽头(找待删结点的前驱)
       q = s;
       s = s->rchild;
       }
       p->data = s->data ; //s指向被删结点的直接前驱
       if (q != p)
       {//重接q的右子树
       q->rchild = s->lchild ;
       }
       else
       {//重接q的左子树
       q->rchild = s->lchild ;
       }
       free(s);
       }
       return TRUE;
      }
      */
      int Delete(BiTree &p)
      {
      	BiTree q,s;
     	if (p->rchild == NULL)
      	{//如果右子树为空，则直接拼接左子树
      		q = p;
      		p = p->lchild;
     		free(q);
      	}
     	else if (p->lchild == NULL)
      	{//如果左子树为空，则直接拼接右子树
      		q = p;
      		p = p->rchild;
     		free(q);
      	}
     	else
      	{//左右子树均不为空的情况,找到其中序序列的直接前驱
      		q = p;
      		s = p->rchild;
     		while (s->lchild)
      		{//转左，然后向右到尽头(找待删结点的前驱)
      			q = s;
      			s = s->lchild;
      		}
      		p->data = s->data ;   //s指向被删结点的直接前驱
     		if (q != p)
      		{//重接q的左子树,不相等，则说明q->lchild = s;
      			q->lchild = s->rchild ;
      		}
     		else
      		{//重接q的右子树，相等，则说明s = q->rchild,即只有一个结点的时候;
      			q->rchild = s->rchild ;
      		}
     		free(s);
      	}
     	return TRUE;
      }
      int DeleteBST(BiTree &T, int key)
      {
     	if (!T)
      	{
     		return FALSE;
      	}
     	else
      	{
     		if (key == T->data)
      		{
     			return Delete(T);
      		}
     		else if (key < T->data)
      		{
     			return DeleteBST(T->lchild, key);
      		}
     		else
      		{
     			return DeleteBST(T->rchild, key);
      		}
      	}
      }
      void InOrderTraverse(BiTree T)
      {
     	if (T == NULL)
      	{
     		return;
      	}
      	InOrderTraverse(T->lchild);//访问左子树
     	printf("%d ",T->data);//访问根结点
      	InOrderTraverse(T->rchild);//访问右子树
      }
      int main()
      {
     	int i,n;
     	int a[] = {62,88,58,47,35,73,51,99,37,93,29,37,36,49,56,48,50};
      	BiTree T = NULL,p;
     	for (i=0; i<sizeof(a) / sizeof(a[0]); i++)
      	{
      		InsertBST(T,a[i]);
      	}
     	printf("该二叉排序树的中序遍历:");
      	InOrderTraverse(T);
     	printf("\n");
     	printf("请输入您要查找的关键字:");
     	scanf("%d",&n);
     	if (SearchBST(T,n,NULL,p))
      	{
     		printf("查找成功!\n");
      	}
     	else
      	{
     		printf("查找失败，待查序列中不包含该关键字\n");
      	}
     	printf("请输入您要插入的关键字:");
     	scanf("%d",&n);
      	InsertBST(T,n);
     	printf("插入关键字 %d 后的二叉树的中序遍历:",n);
      	InOrderTraverse(T);
     	printf("\n");
     	printf("请输入您要删除的关键字:");
     	scanf("%d",&n);
     	if (DeleteBST(T,n))
      	{
     		printf("删除关键字 %d 后的二叉树的中序遍历:",n);
      		InOrderTraverse(T);
     		printf("\n");
      	}
     	else
      	{
     		printf("二叉树不包含关键字 %d\n!",n);
      	}
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17268233