欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树(Tree)——(三)搜索二叉树(BST)插入、查找

程序员文章站 2022-03-24 16:05:32
...

 

目录

搜索树的创建和插入(C++)

迭代版 (未用递归):

递归版:

BST的查找:

BST寻找最大最小值:

查找父节点:

 


之前用到的二叉树是基本不用的,只是具备了二叉树的样子。二叉树的作用是为了方便查找,所以我们需要构建一个搜索二叉树。

二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树。 

二叉搜索树不同于一般的二叉树,它是一种特殊的二叉树,如果对这棵树进行中序遍历,你就会得到一个递增的队列。

 

搜索树的创建和插入(C++)

迭代版 (未用递归):

#include <iostream>
using namespace std;
struct TreeNode
{
        int _data;
        TreeNode* _left;
        TreeNode*_right;
};

void insertBst(TreeNode**root,int data)
{
    TreeNode*t =*root;
   // TreeNode***chen =&root;   

/* 这里是我多想了个方法,因为二级指针想要访问内部的必须用更上一级的指针,这里我用了三级指针,这里的chen可以代替下面根初始化的(*root),实际上用(*root)更加便于理解一点            */


    if((**chen)==NULL)  //若为根节点,则是树的最初初始化 ,或者改成 (*root) == NULL
    {
        (*root)=(TreeNode*)malloc(sizeof(TreeNode));
        (*root)->_data = data;
        (*root)->_left = (*root)->_right = NULL;
    }
    else
    {
        while(1)  //这里就在遍历这个加入的数在哪一边,判断在每一层深度的左边还是右边
        {
            if(data > t->_data)  //若要加入的数比原来的大
            {
                if(t->_right==NULL)
                {
                    TreeNode* ch=(TreeNode*)malloc(sizeof(TreeNode));  //开辟一个树节点
                    ch->_data=data;
                    t->_right=ch;
                    ch->_left = ch->_right = NULL;
                    break;
                }
                else
                    t=t->_right;
            }
            else     //比原来的小于或等于
            {
                if(t->_left==NULL)
                {
                    TreeNode* ch=(TreeNode*)malloc(sizeof(TreeNode));
                    ch->_data=data;
                    t->_left=ch;
                    ch->_left = ch->_right = NULL;
                    break;
                }
                else
                    t=t->_left;
            }
        }

    }
}


//中序遍历
void midOrderTraverse(TreeNode*r)
{
    if(r)
    {
        midOrderTraverse(r->_left);
        printf("%d ",r->_data);
        midOrderTraverse(r->_right);
    }

}
/* 例子
 *                   30
 *
 *            8             36
 *
 *               15    32        100
 */

int main()
{   
    TreeNode *root=NULL;   //树的初始化
    insertBst(&root,30);         //利用例子建造树
    insertBst(&root,8);
    insertBst(&root,15);
    insertBst(&root,36);
    insertBst(&root,100);
    insertBst(&root,32);

    midOrderTraverse(root);  //中序递归遍历
    return 0;
}


 

递归版:

void insertBstRecusive(TreeNode ** root, int data)
{
    if((*root) == NULL)
    {
        (*root) = (TreeNode*)malloc(sizeof(TreeNode));
        (*root)->_data = data;
        (*root)->_left = (*root)->_right = NULL;
    }
    else if(data >(*root)->_data)
    {
        insertBstRecusive(&(*root)->_right,data);
    }
    else
    {
        insertBstRecusive(&(*root)->_left,data);
    }
}

//这里其他的就不贴了,主要就是把这个放入上面迭代版,函数名改一下就可以运行。

 

BST的查找:

//遍历版(非递归)

TreeNode* searchBst(TreeNode*r ,int find)
{
    while(r)
    {
        if(r->_data == find)
            return r;
        else if(find> r->_data)
            r=r->_right;
        else
            r=r->_left;
    }
    return NULL;
}

//递归版
TreeNode* searchBstRecursive(TreeNode*r ,int find)
{
    if(r)
    {
        if(r->_data == find)
                return r;
        else if(find > r->_data)
            return searchBstRecursive(r->_right,find);
        else
            return searchBstRecursive(r->_left,find);
    }
    return NULL;
}

这个在main函数中函数调用,加入寻找的数就可以了。

 

BST寻找最大最小值:

//找最小数(肯定在最左边)
TreeNode* getMinNodeBst(TreeNode*r)
{
    if(r)
    {
        while(r->_left)
        {
                r=r->_left;
        }
        return r;
    }
    return NULL;
}

//找最大数(肯定在最右边)
TreeNode* getMaxNodeBst(TreeNode*r)
{
    if(r)
    {
        while(r->_right)
        {
                r=r->_right;
        }
        return r;
    }
    return NULL;
}


 

查找父节点:

//递归版

TreeNode* getParentBst(TreeNode * r,TreeNode * child)
{
    static TreeNode * parent = NULL;  //这里使用了静态变量,静态变量的话在函数中只存在一个
    if(r)
    {
        if(r->_left == child || r->_right== child)
            parent = r;
        getParentBst(r->_left,child);
        getParentBst(r->_right,child);
    }
    return parent;
}

//非递归版用队列就可以解决,若要看代码点击这里

 

 

相关标签: 数据结构