Tag Archives: 二叉排序树

数据结构重读 – 二叉排序树(BST)

1、前面讨论了静态查找表,它们的特点是,数据是一次性就给好了。

2、而对于动态查找表,数据可以是在查找过程中动态添加、生成的。其实这概念不太严谨。

3、二叉排序树(BST):左子树上所有结点的值均小于根结点的值;右子树上所有结点的值均大于根结点上的值。

4、二叉排序树的查找过程:
(1)若树为空,直接返回/跳出。
(2)树非空,则
(a)若key==root.data,return true。
(b)若key<root.data, root = root.left[……]

继续阅读