二叉查找树

二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有结点的值均大于或等于它的根结点的值; 3.左右子树也分别为二叉查找树; 4.等于的情况只能出现在左子树或右子树中的某一侧,一般二叉查找树中无重复节点。 5.二叉查找树的中序遍历从小到大的顺序,故又名二叉排序树。

struct TreeNode{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode(int x); val(x), left(NULL),right(NULL){}
};
二叉查找树插入节点

将某节点(insert_node),插入至以node为根二叉查找树种: 如果insert_node节点值小于当前node节点值: 1.如果node有左子树,则递归的将该节点插入至左子树为根二叉排序树中 2.否则,将node->left赋值为该节点地址 否则(大于等于情况): 1.如果node有右子树,则递归的将该节点插入至右子树为根二叉排序树中 2.否则,将node->right赋值为该节点地址

二叉查找树插入节点复杂度为O(h),h为树的高度,若二叉查找树较为平衡,则平均查找复杂度为log(n)

递归实现
void BST_insert(TreeNode *node, TreeNode *insert_node){
    if(insert_node->val < node->val ){
        if(node->left){
            BST_insert(node->left, insert_node);
        }
        else{
            node->left = insert_node;
        }
    }
    else{
        if(node->right){
           BST_insert(node->right,insert_node); 
        }
        else{
            node->right = node_insert;
        }
    }
  
}
循环实现
void BST_insert(TreeNode *node, TreeNode * insert){
    while(node != insert_node){
        if(insert_node -> val < node->val){
            if( !node->left){
                node->left = insert_node;
            }
            node = node->left;
        }
        else{
            if(!node->rifht){
                node->rifht = insert_node;
            }
            node = node->rifht;
        }
    }
}

二叉查找树查找数值

查找数值value是否在二叉查找树中出现: 如果value等于当前查看node的节点 值:返回True 如果value节点值小于当前node节点值: 1.如果当前节点值有左子树,继续在左子树中查找该值;否则,返回假 否则(value)节点值大于当前node节点值: 如果当前节点值有右子树,继续在右子树中查找该值;否则,返回假

二叉查找树查找数值复杂度为O(h),h为树的高度,若二叉查找树较为平衡,则平均查找复杂度为log(n)

递归实现
bool BST_search(TreeNode * node, int value){
    if(node->val == value){
        return true;
    }
    if(value < node-> val){
        if(node->left){
           return  BST_search(node->left, value);
        }
        else{
            return false;
        }
    }
    else{
        if(node->right){
           return BST_search(node-right, value);
        }
        else{
            return false;
        }
    }
}
循环实现
bool BST_search(*node, value){
    while(node){
        if(node->val == value){
            return true;
        }
        if(value < node->val){
            node = node->left;
        }
        else{
            node = node->right
        }
    }
     return false;
}
测试

··· int main(){ TreeNode a(8); TreeNode b(3); TreeNode c(10); TreeNode d(1); TreeNode e(6); TreeNode f(15); a.left = &b; a.rifht = &c; b.left = &d; b.right = &e; c.right = &f; for(int i = 0; i <20; i++){ if(BST_search(&a, i)){ printf("%d is in the BST.\n",i) } else{ printf("%d is not in the BST.\n",i) } } return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 排序数组转换为二叉查找树

    已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

    小飞侠xp
  • 二叉树基础知识

    树是n(n>=0)个节点的有限集,且这些节点满足如下关系: (1)有且仅有一个节点没有父结点,该节点称为树的根。 (2)除根外,其余的每个节点都有且仅有一个...

    小飞侠xp
  • 堆的基础知识

    二叉堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。最大堆,树种各个父 节点的值总是大于或等于任何一个子节点的值;最小堆,树种各个父节点的值总是小于或 等...

    小飞侠xp
  • 【剑指offer:两个链表的第一个公共节点】双解法

    题目提示了,空间复杂度可以降低到$O(1)$。这时候不能用哈希表,可以使用快慢指针的思路来处理。整体思路如下:

    心谭博客
  • hdu1009

    @坤的
  • javascript进阶必备的二叉树知识

    每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于0-3年的前端程序员...

    徐小夕
  • P3372 【模板】线段树 1 线段树模版+懒惰标记

    用户2965768
  • jQuery动画与ajax

    小胖
  • 性能分析之OS资源饱和度

    在做性能分析的时候,我们不可避免地判断资源到底够不够用?哪里不够?为什么不够?证据是什么?

    高楼Zee
  • 算法:跳跃表的实现

    在跳跃表中,每个节点的level数随机按1-5生成并不是很好,可以引入一个算法。在redis中,每个节点的level有1-32层。层数越大的节点越少。具体上,可...

    超级大猪

扫码关注云+社区

领取腾讯云代金券