程序设计:算法和数据结构-笔记7——二叉搜索树
搜索树
定义
搜索树是一种可以进行插入、搜素、删除等操作的数据结构,可以用作字典或优先级队列。二叉搜索树属于最基本的搜索树。
性质
设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;
};
本文是原创文章,采用 CC BY-NC-ND 4.0 协议,完整转载请注明来自 程序员小航
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果