计算机考研考点解析：数据结构之BST树（上）

计算机考研的考生们注意啦，下面是计算机考研数据结构之BST树的相关介绍，包括BST树的定义和性质等知识点，各位考生要认真复习，预祝大家能够取得好成绩。

1、定义和性质

一棵BST树或者是空二叉树，或者是具有如下性质的二叉树：

(1)左子树上所有结点的关键字(若存在)均小于根结点的关键字。

(2)右子树上所有结点的关键字(若存在)均大于根结点的关键字。

(3)左子树和右子树又各是一棵二叉排序树。

二叉排序树的特点：中序遍历二叉排序树，可以得到一个递增的有序序列。BST树仍然可以用二叉链表来存储，在二叉排序树中删除后又插入同一结点，得到的二叉排序树与原来的不一定相同，但中序序列一定相同，因为在二叉排序树中插入的新结点均作为叶子结点。

2、查找

二叉树的操作是从根开始的，那么对二叉排序树的进行查找也是从根结点开始。

(1)将给定值与根结点的关键字比较，若相等，则查找成功。

(2)当根结点的关键字大于给定关键字值时，在根结点的左子树中查找。

(3)否则在根结点的右子树中查找。

二叉排序树的一条查找路径也必然满足二叉排序树的性质。二叉排序树的查找效率最好为O(log2N)，最差为O(N)。其复杂度取决于树的形态。

从查找过程可以发现，在随机的情况下，二叉排序树的的平均查找长度和树的深度是等数量级的。

以上就是为大家整理的计算机考研数据结构知识点介绍，考生们在备考过程中遇到问题，可以在右侧咨询窗口留言，会有老师一对一为大家解答，助力大家顺利通过考研初试、考研复试。