赵玉伟的博客

二叉查找树

二叉查找树,又叫二叉搜索树、搜索二叉树。

如果在某个数组中查找某个值,比较快的方式是二分查找,但是二分查找的前提是数组有序。如果是一个无序的数组,可以构造成一棵二叉查找树, 二叉查找树是一种增删查相对均衡的数据结构。

二叉查找树满足什么特性?

  • 每个节点最多有2个子节点;
  • 父节点的左子节点 < 父节点, 父节点的右子节点 >= 父节点。

序列:A: 1,2,3,4,5,6,7,8,9; B: 9,8,7,6,5,4,3,2,1 构造成二叉查找树如下:


以上两种结构,虽然是二叉查找树, 但是由于数组已经有序,所以其实已经退化成链表。

序列:6,5,8,3,4,9,7,2,1, 构造成二叉查找树如下: