查找-二叉排序树查找

男娘i 2022-05-12 03:18 238阅读 0赞

**二叉排序树的性质：**

(1)若某节点的左子树非空，则左子树上所有元素的值都小于该元素的值。

(2)若某节点的右子树非空，则右子树上所有元素的值都大于该元素的值。

**问题：**在二叉排序树种，原则上各元素关键字是唯一的。然而在实际运用中，不能保证各元素之间的关键字都不相同。因此性质中，可以把”大于“或”小于“修改成”大于等于“或者“小于等于”。

**特点：**

1.二叉排序树是有序的

2.构造的二叉排序树高度越小，其查找的效率越高。

**时间复杂度：**

O(nlog2(n))

**优点：**无须移动元素，只修改指针就实现插入和删除操作。

![70][]

**代码：**

#include<stdio.h>
    #include<malloc.h>
    int path[100];
    //数据表
    typedef struct node
    {
    	int key;
    	struct node *lchild,*rchild;
    }BSTNode;
    //插入数据
    int InsertBST(BSTNode *&p,int k)
    {
    	if(p==NULL)
    	{
    		p=(BSTNode*)malloc(sizeof(BSTNode));
    		p->key=k;
    		p->lchild=NULL;
    		p->rchild=NULL;
    		return 1;
    	}
    	else if(k==p->key)
    	{
    		return 0;
    	}
    	else if(k<p->key)
    	{
    		return InsertBST(p->rchild,k);
    	}
    	else
    	{
    		return InsertBST(p->rchild,k);
    	}
    }
    //创建二叉树
    BSTNode *CreateBST(int arr[],int n)
    {
    	BSTNode *bt=NULL;
    	int i=0;
    	while(i<n)
    		if(InsertBST(bt,arr[i])==1)
    		{
    			i++;
    		}
    		return bt;
    }
    //非递归查找
    void SearchBST_NoRec(BSTNode *bt,int k,int path[],int i)
    {
    	int j;
    	if(bt==NULL)
    	{
    		return;
    	}
    	else if(k==bt->key)
    	{
    		path[i]=bt->key;
    		
    		for(j=0;j<=i;j++)
    			printf("%3d",path[j]);
    		printf("\n");
    	}
    	else
    	{
    		path[i]=bt->key;
    		if(k<bt->key)
    			SearchBST_NoRec(bt->lchild,k,path,i+1);
    		else
    			SearchBST_NoRec(bt->rchild,k,path,i+1);
    	}
    }
    //递归查找
    int SearchBST_Rec(BSTNode *bt,int k)
    {
    	if(bt==NULL)
    		return 0;
    	else if(k==bt->key)
    	{
    		printf("%3d",bt->key);
    		return 1;
    	}
    	else if(k<bt->key)
    		SearchBST_Rec(bt->lchild,k);
    	else
    		SearchBST_Rec(bt->rchild,k);
    	printf("%3d",bt->key);
    	
    }
    void main()
    {
    	BSTNode *bt;
    	int k=6;
    	int arr[]={4,9,0,1,8,6,3,5,2,7},n=10;
    	bt=CreateBST(arr,n);
    	printf("查找%d关键字(非递归)：",k);
    	SearchBST_NoRec(bt,k,path,0);
    	printf("查找%d关键字（递归）：",k);
    	SearchBST_Rec(bt,k);
    }

[70]: /images/20220512/ee4d61e9cc814491b6bd6662758e804e.png