二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具备下列性质的二叉树:web
- 任意节点的左子树不空,则左子树上全部结点的值均小于它的根结点的值;
下面 4 张 GIF 动图,是 penjee 官博制做分享。,分享给你们。
###图1:查找 BST 中的某个元素算法
在二叉搜索树b中查找x的过程为:数组
- 若b是空树,则搜索失败,不然:
###图2 ↓ :从有序数组构造一个二叉查找树数据结构
###图3 ↓:往 BST 中插入元素svg
向一个二叉搜索树b中插入一个节点s的算法,过程为:xml
- 若b是空树,则将s所指结点做为根节点插入,不然:
###图4 ↓:BST 转成有序数组
blog