menu 李昊天的个人博客
程序设计:算法和数据结构-笔记7——二叉搜索树
374 浏览 | 2019-08-19 | 分类:算法笔记 | 标签:算法,学习笔记,搜索

搜索树

定义

搜索树是一种可以进行插入、搜素、删除等操作的数据结构,可以用作字典或优先级队列。二叉搜索树属于最基本的搜索树。

性质

设x为二叉搜索树的结点,如果y是x左子树的结点,那么y的键值小于等于x的键值。如果z是x的右子树中的结点,那么x的键值小于等于z的键值。

如图所示

当数据进行插入或者删除操作后,所有结点仍然满足上述的性质。

插入

伪代码

insert方法用于在二叉搜索树T中插入新值v,insert 将键值为v,左子树为NIL,右子树为NIL的点z作为实参传入

insert(T,z)
    y=NIL //x的父结点
    x='T的根节点'
    while x!=NIL
        y=x //设置父结点
        if z.key < x.key
            x=x.left
        else
            x=x.right
    z.p=y
    
    if y==NIL //T为空时
         'T的根节点'=z
    else if z.key <y.key
        y.left=z //将z定为y的左子结点
    else
        y.right=z //将z定为y的右子结点

定义

struct Node{
    int key;
    struct Node * parent,*left,*right;
};
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!