二叉排序树的建立和查找（面试常考）详解编程语言

在众多查找方法中，二叉排序树查找是比较好的一种查找，其效率比顺序查找，折半查找，插值查找，斐波纳契查找等都要好。

二叉排序树的建立

首先要了解而叉排序树如何建立，给定一组数组，建立一个而叉排序树

#include <iostream>  
 
typedef struct BitNode{ 
   int data; 
   struct BitNode *lchild, *rchild;  
}BitNode, *BiTree; 
 
bool BSTInsert(BitNode * &p, int element)   
{   
    if(NULL == p) // 空树   
    {   
        p = new BitNode;   
        p->data = element;   
        p->lchild = p->rchild = NULL;   
        return true;   
    }   
 
    if(element == p->data) // BST中不能有相等的值   
        return false;   
 
    if(element < p->data)  // 递归   
        return BSTInsert(p->lchild, element);   
 
    return BSTInsert(p->rchild, element); // 递归   
}   
 
void createBst(BitNode * &T, int a[], int n){ 
    T = NULL; 
    int i; 
    for(i = 0; i < n; i++){ 
        BSTInsert(T, a[i]); 
    } 
} 
 
//先序遍历 
void preOrderTraverse(BiTree T)   
{   
    if(T)   
    {   
        printf("%d ", T->data); 
        preOrderTraverse(T->lchild);   
        preOrderTraverse(T->rchild);   
    }   
}   
 
//中序遍历 
void inOrderTraverse(BiTree T)   
{   
    if(T)   
    {   
        inOrderTraverse(T->lchild);   
        printf("%d ", T->data); 
        inOrderTraverse(T->rchild);   
    }   
}   
 
int main(){ 
    int a[10] = {1,3,5,2,9,4,6,0,7,8}; 
    BiTree T; 
    createBst(T, a, 10); 
 
    preOrderTraverse(T);  
    printf("/n"); 
    inOrderTraverse(T); 
 
 
    return 0; 
}

看看结果：

第一个是先序遍历的结果，第二个是中序遍历的结果

先序遍历：中->左->右
中序遍历：左->中->右

二叉树建立后的样子是这样的：

二叉排序树的查找操作

查找操作代码在原代码中修改

#include <iostream>  
 
static int i = 0; 
 
typedef struct BitNode{ 
   int data; 
   struct BitNode *lchild, *rchild;  
}BitNode, *BiTree; 
 
bool BSTInsert(BitNode * &p, int element)   
{   
    if(NULL == p) // 空树   
    {   
        p = new BitNode;   
        p->data = element;   
        p->lchild = p->rchild = NULL;   
        return true;   
    }   
 
    if(element == p->data) // BST中不能有相等的值   
        return false;   
 
    if(element < p->data)  // 递归   
        return BSTInsert(p->lchild, element);   
 
    return BSTInsert(p->rchild, element); // 递归   
}   
 
void createBst(BitNode * &T, int a[], int n){ 
    T = NULL; 
    int i; 
    for(i = 0; i < n; i++){ 
        BSTInsert(T, a[i]); 
    } 
} 
 
//查找 
void searchBst(BiTree T, int key){ 
    //记录第几次查找到  
    ++i;  
    if(T){ 
        if(key == T->data){ 
            printf("第%d次查询/n", i); 
            printf("查得：%d", T->data); 
        } else if(key < T->data) 
            searchBst(T->lchild, key); 
        else  
            searchBst(T->rchild, key); 
    } 
} 
 
int main(){ 
    int a[10] = {1,3,5,2,9,4,6,0,7,8}; 
    BiTree T; 
    createBst(T, a, 10); 
 
    searchBst(T, 8); 
    return 0; 
}

结果如下：

二叉排序树很好理解，同时也是面试题中较常出现的，是应该掌握的知识点。（上述例子，由于只是为了演示，没有考虑内存泄露的问题）