二叉搜索树 (BST)_二叉树中序序列从小到大吗?

二叉搜索树 (BST : Binary Search Tree) 又名 二叉查找树 或 二叉排序树。

• 二叉搜索树： 左孩子的值 一定小于或等于 父结点的值

• 二叉搜索树： 右孩子的值 一定大于或等于 父结点的值

• 二叉搜索树的左、右子树也分别是二叉搜索树

图二中，结点17 是 结点27的右孩子，但它的值比父结点的值小。所以图二不是二叉搜索树。

---

二叉搜索树的 中序遍历 得到的序列 一定是从小到大的有序序列。

• 如上图一的中序遍历结果为：8 17 27 43 77 80 89 95 ，是从小到大的有序序列。

---

⚾误以为：二叉搜索树 一定是 完全二叉树

• 如图一是二叉搜索树，但不是完全二叉树。

⚾误以为：二叉搜索树的 层序遍历 得到的序列 一定是有序的。

• 如图一的层序遍历结果为：77 43 89 27 80 95 8 17 ，这个序列是无序的。 (只有左孩子或只有右孩子的斜二叉搜索树的层序遍历才是有序的。)

⚾误以为：

---

二叉搜索树的查找时间复杂度和树的高度有关

• 如图一，若二叉搜索树是完全二叉树，则树高为$\log n$ + $1$，则其查找时间复杂度为$O$($\log n$)

• 如图二，若二叉搜索树是完全不平衡二叉树，则树高为$n$，则其查找时间复杂度为$O$($n$)，退化成顺序查找。

二叉搜索树 查找时间复杂度为$O$($\log n$) 到 $O$($n$)之间

---

如何在CSDN上写数学公式