查找——二叉排序树（C语言实现）

二叉排序树（二叉查找树）

1. 树表的提出：
   1）如何在一个大型的数据集合上进行动态查找？
   （1）顺序查找：不要求元素的有序性，插入、删除的性能是O(1)查找性能是O(n)<需要一个个比较>
   （2）折半查找：查找性能是O(log2n)为保证元素的有序性，插入、删除要移动元素，性能是O(n)
   2）树表（树表：将查找集合组织成树的结构–>二叉排序树）这种查找结构使得插入、删除、查找均具有较好效率。
2. 基本概念：
   1）二叉排序树（二叉查找树）：
   是一棵空的二叉树
   是具有下列性质的二叉树：
   （1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值
   （2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值
   （3）它的左右子树也都是二叉排序树
   2）二叉排序树是记录之间满足某种大小关系的二叉树。
3. 二叉排序树的中序遍历结果——升序序列
   
4. 如何存储二叉排序树？——二叉链表(参考二叉树相关知识)

二叉树排序树的操作

1. 插入一个元素
   1）若二叉排序树为空树，则新插入的结点为新的根结点；
   2）否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

void InsertBST(BiNode *root, int x)
{
    if (root == NULL) 
    { 
        BiNode *s = (BiNode *)malloc(sizeof(BiNode)); 
        s->data = x;
        s->lchild = s->rchild = NULL;
        root = s;
    }
    else if (root->data > x) InsertBST(root->lchild, x);//比根节点小去左子树
    else InsertBST(root->rchild, x);//比根节点大去右子树
}

1. 二叉排序树的构造
   1）思路：<按照所给的集合的顺序，不断调用上面的插入代码>
   （1）每次插入的新结点都是二叉排序树上新的叶子结点;
   （2）找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；
   （3）在左子树/右子树的查找过程与在整棵树上查找过程相同；
   （4）新插入的结点没有破坏原有结点之间的关系。
   2）

void CreatBST(BiNode *root, int r[ ], int n)
{
    for (int i = 0; i < n; i++)
    {
        InsertBST(root, r[i]);
    }
}

1. 二叉排序树的删除（设待删除结点为p，其双亲结点为f）
   1）规则：
   （1）从二叉排序树中删除一个结点之后，要仍然保持二叉排序树的特性；
   （2）当删除分支结点时破坏了二叉排序树中原有结点之间的链接关系，需要重新修改指针，使得删除结点后仍为一棵二叉排序树。
   2）
   
   情况3：被删除的结点既有左子树也有右子树
   操作：以其左子树中的最大值结点替换之，然后再删除该结点
   

复制删除法：
如果结点有两个孩子，可以用结点的直接前驱结点代替该结点，然后再删除这个前驱结点，而前驱结点只能是下面两种情况之一：如果前驱结点是叶结点，应用第一种情况；如果它有一个孩子，应用第二种情况

void deleteByCopying(BiTree &T, KeyType k) 
{
  if (T==NULL) return;
  else 
  {
    if (T->data==k) delete(T);
    else if (k<T->data) deleteByCopying(T->lchild, k);
    else deleteByCopying(T->rchild, k);
  }
}
void delete(BiTree &p) 
{
  if (p->rchild==NULL) 
  {
  	q=p; 
  	p=p->lchild; 
  	free(q);
  } //只有左子树                                              
  else 
  {
  	if (p->lchild==NULL) 
  	{
  		q=p; 
  		p=p->rchild; 
  		free(q);
  	}  //只有右子树                                
 	else//p既有左子树，又有右子
 	{      
 		q=p;
    	s=p->lchild;
   		while (s->rchild)//右子树不为空继续循环
   		{
   			q=s; 
   			s=s->rchild;
   		}  //s为p的左子树的最右结点，即直接前驱，q为s的父结点
    	p->data=s->data; //用s替换p的关键字      
	    if (q!=p) 
	    {
	    	q->rchild=s->lchild;
	    }
	    else
	    {
	    	q->lchild=s->lchild;
	    }
    	free(s);
    }
}

这个算法是不对称的：它总是删除直接前驱结点，如果进行多次删除，就会减少左子树的高度而不影响右子树。进行多次删除后，整个树变得向右侧偏，右子树比左子树大得多

为了解决这个问题，可以对算法的对称性作一个简单改进：交替地从左子树删除前驱、从右子树删除后继，这叫做“对称删除法”

对称删除法
1）在二叉排序树中查找给定值 k 的过程是
（1）若root是空树，则查找失败；
（2）若k＝root->data，则查找成功；
（3）若k＜root->data，则在root的左子树上查找；
（4）若k > root->data，在root的右子树上查找。

二叉排序树的查找效率在于只需查找二个子树之一

BiNode *SearchBST(BiNode *root, int k)
{
    if (root == NULL) return NULL;
    if (root->data == k) return root;
    else if (root->data > k)  return SearchBST(root->lchild, k);
    else  return SearchBST(root->rchild, k);
}

2）二叉排序树的查找性能取决于什么？
（1）查找的比较次数不超过树的深度
（2）插入，删除，查找的时间复杂度相同。
3）二叉排序树的深度是多少？取决于什么？——查找集合的初始排列

实验

【问题描述】
从键盘读入<一串整数>构造一棵二叉排序树，并对得到的二叉排序树进行前序遍历。
实验要求：该二叉排序树以二叉链表存储
【输入形式】
输入一串整数（以空格分开），以－1作为结束标志，且－1不作为数据输入。
【输出形式】
<前序遍历>二叉排序树的结果
【样例输入】
23 22 11 32 2 －1
【样例输出】
23 22 11 2 32

#include<stdio.h>
#include<stdlib.h>

typedef struct BNode
{
	int data;
	struct BNode *lchild,*rchild;
}BNode,*BiTree;

//搜索 
int Search(BiTree T,int t,BiTree T1,BiTree *p)
//从头到尾搜索，找到一个为空的，且数值合适的位置插入 
{
	if(!T)//当T为空时 
	{
		*p = T1;
		return 0;
	}
	else//当T不为空时 
	{
		if(t==T->data)//当e==T->data 
		{
			*p = T;
			return 1;
		}
		else
		{
			if(t<T->data)
				return Search(T->lchild,t,T,p);
			else
				return Search(T->rchild,t,T,p);
		}	
	}
}
int Insert(BiTree *T,int t)
{
	BiTree s,p;
	if(!Search(*T,t,NULL,&p))//SearchBST(*T,e,NULL,&p)==0
	{
		s = (BiTree)malloc(sizeof(BNode));
		s->data = t;
		s->lchild = s->rchild = NULL;
		if(!p)//p为空 
		{
			*T = s;
		}
		else
		{
			if(t<p->data)
				p->lchild = s;
			else
				p->rchild = s;
		}
		return 1;
	}
	else
		return 0;
}
int Visit(int t)
{
	printf("%d ",t);
	return 1;
}
int PreOrderTree(BiTree T,int (* Visit)(int t)) //递归前序遍历二叉树
{
	if(T)
	{
		if(Visit(T->data))
		if(PreOrderTree(T->lchild,Visit))
		if(PreOrderTree(T->rchild,Visit))
		return 1;
		return 0;
	}
	else
	return 1;
}
int Create(BiTree *T)
{
	int t;
	scanf("%d",&t);
	while(t!=-1)
	{
		Insert(T,t);
		scanf("%d",&t);
	}
	return 1;
}
int main()
{
	BiTree T=NULL;
	Create(&T);
	PreOrderTree(T,Visit);
	return 0;
}