【数据结构】二叉查找树

建树

树节点的存储方式与普通的二叉树相似，用结构体存储，其中一个 int 变量存储数据，两个指针指向左右儿子。

读入一个新数据，从根节点开始寻找，大于当前节点则继续寻找右子树，右子树为空则直接插入，小于当前节点则继续寻找左子树，左子树为空则直接插入。

注：

初始数据要求随机数，为了产生真正意义上的“随机数”，使用时间作为随机数种子。

查找

从根节点开始寻找，大于当前节点则转向右子树，小于当前节点则转向左子树。直到找到等于的节点。如果转到了空节点，则说明这个数并不在这棵二叉查找树上。

插入

插入的过程与查找相似。从头开始寻找，如果在树上找到了，则说明树上已有此节点，不需再插入。如果没有在树上，那么会走到一个空节点，此时直接将新节点插入空节点处即可。注意与上一级节点的衔接。

删除

首先是寻找要删除的节点。这一步与寻找的过程相似。

当找到要删除的节点后，会出现以下情况：

（1）左右子树为空

直接删除即可

（2）左子树为空

直接将右子树移到待删除节点处即可。

（3）右子树为空

直接将左子树移到待删除节点处即可。

（4）左右子树均不为空

先将左子树整体插入到右子树中，再将右子树移到待删除节点处。

遍历与二分查找

二叉查找树的遍历与普通二叉树相同，可以通过递归实现。先递归左子树，然后输出根节点，最后递归右子树。这样便得到一个有序的序列。

对于这个有序的序列中的任意元素，都可以通过二分查找找到他们的具体位置。二分查找可以通过一个循环实现，对于每一层循环，先比较目标元素与当前区间中心元素进行比较，目标元素大于中间元素时，说明在右区间内，否则在左区间内。直到区间锁定到一个元素，即目标元素。

CODE：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>
#include<time.h>
#define N 100
using namespace std;
 
typedef struct Tree
{
	int data;
	Tree *ls,*rs;	
};
 
Tree  *head;
int sorr[N];
int nn=0;
void build(Tree *T,Tree *now);
void printt(Tree *now,int sorr[]);
void fi(Tree *now,int ii);
void find();
void insee(Tree *now,Tree *ii);
void insert();
void inn(Tree *now,Tree *ii);
void del(Tree *now,int ii);
void delet();
int binSearch(const int *Array,int start,int end,int key);
void find_2(int sorr[]);
 
int main()
{
	srand((unsigned)time(NULL));
	head=NULL;
	
	for (int i=0;i<10;i++) 
	{
		int num=rand()%100+1;
		Tree *T;
		T=new Tree;
		T->data=num;
		T->ls=T->rs=NULL;
		build(T,head);
	}
	cout<<"======PRI======"<<endl;
	printt(head,sorr);
	find();
	insert();
	nn=0;cout<<"---AFTER INSERT---"<<endl;
	printt(head,sorr);
	delet();
	nn=0;cout<<"---AFTER DELETE---"<<endl;
	printt(head,sorr);
	find_2(sorr);
	cout<<"======FINAL======"<<endl;
	printt(head,sorr);
}
 
void build(Tree *T,Tree *now)
{
	if (head==NULL)
	{
		head=T;
		return;	
	}
	if (now->data>T->data)
	{
		if (now->ls!=NULL)
		{
			build(T,now->ls);
		}
		else
		now->ls=T;
	}
	else if (now->data<T->data)
	{
		if (now->rs!=NULL)
		{
			build(T,now->rs);
		}
		else
		now->rs=T;
	}
}
 
void printt(Tree *now,int sorr[])
{
	if (head->data==0) 
	{
		cout<<"NULL!"<<endl;
		return;
	}
	if (now->ls!=NULL)
	printt(now->ls,sorr);
	if (now->data!=0)
	{
	cout<<now->data<<" ";
	//if (now->ls!=NULL) cout<<now->ls->data<<" ";
	//if (now->rs!=NULL) cout<<now->rs->data;
	cout<<endl;
	}
	sorr[nn]=now->data;
	nn++;
	if (now->rs!=NULL)
	printt(now->rs,sorr);
}
 
void fi(Tree *now,int ii)
{
	if (now->data==ii)
	{
		cout<<"GET IT!"<<endl;
		return;
	}
	if (now->rs ==NULL && now->ls==NULL) 
	{
		cout<<"NO!"<<endl;
		return;
	}
	if (now->data>ii) fi(now->ls,ii);
	else fi(now->rs,ii);
	
	return;
}
 
void find()
{
	cout<<"======FIND======"<<endl;
	int n;
	cin>>n;
	while (n!=-1)
	{
		fi(head,n);
		cin>>n;
	}
	//cout<<now->data<<endl;
}
void insee(Tree *now,Tree *ii)
{
	if (now->data==ii->data)
	{
		cout<<"HAVE HAD IT!"<<endl;
		return;
	}
	if (now->data>ii->data)
	{
		if (now->ls==NULL)
		 now->ls=ii;
		 else insee(now->ls,ii);
	}
	else if (now->data<ii->data)
	{
		if (now->rs==NULL)
		 now->rs=ii;
		else insee(now->rs,ii);
	}
	return;
	
}
void insert()
{
		int n;
		cout<<"=====INSERT====="<<endl;
		cin>>n;
		while (n!=-1)
		{
			Tree *T1;
			T1=new Tree;
			T1->data=n;
			T1->ls=T1->rs=NULL;
			insee(head,T1);
			cin>>n;
		}
		
}
void inn(Tree *now,Tree *ii)
{
	if (now->data>ii->data)
	{
		if (now->ls==NULL)
		 now->ls=ii;
		 else inn(now->ls,ii);
	}
	else if (now->data<ii->data)
	{
		if (now->rs==NULL)
		 now->rs=ii;
		else inn(now->rs,ii);
	}
	return;
}
void del(Tree *now,int ii)
{
	//cout<<now->data<<endl;
	if (now->data==ii)
	{
		if (now->ls==NULL && now->rs==NULL) 
		memset(now,sizeof(Tree));
		else if (now->ls==NULL)
		*now=*(now->rs);
		else if (now->rs==NULL)
		*now=*(now->ls);
		else if (now->ls!=NULL)
		{
			inn(now->rs,now->ls);
			*now=*(now->rs);
		}
		cout<<"OK"<<endl;
		return;
	}
	if (now->rs ==NULL && now->ls==NULL) 
	{
		cout<<"NO!"<<endl;
		return;
	}
	if (now->data>ii) del(now->ls,ii);
	else del(now->rs,ii);
	
	return;
}
 
void delet()
{
	cout<<"======DELETE======="<<endl;
	int n;
	cin>>n;
	while (n!=-1)
	{
		del(head,n);
		nn=0;cout<<"...NOW..."<<endl;
		printt(head,sorr);
		cout<<endl;
		cin>>n;
	}
	
	return;
}
int binSearch(const int *Array,int key)
{
    int left,right;
    int mid;
    left=start;
    right=end;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(key==Array[mid])  return mid;
        else if(key<Array[mid]) right=mid-1;
        else if(key>Array[mid]) left=mid+1;
    }
    return -1;
}
void find_2(int sorr[])
{
	cout<<"=====FIND_2===="<<endl;
	int n;
	cin>>n;
	while (n!=-1)
	{
		cout<<binSearch(sorr,nn,n)<<endl;
		cin>>n;
	}
	return;
}

【数据结构】二叉查找树

猜你在找的数据结构相关文章