查找-二叉排序树查找-蒲公英云

查找-二叉排序树查找

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

二叉排序树的性质：

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

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

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

特点：

1.二叉排序树是有序的

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

时间复杂度：

O(nlog2(n))

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

代码：

#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);
}