每棵子树头节点的值都比各自左子树上所有节点值要大,也都比各自右子树上所有节点值要小。

二叉查找树的中序遍历序列一定是从小到大排列的。

毕竟二叉搜索树的查询复杂度只是介于 二叉查找树BST-LMLPHP~二叉查找树BST-LMLPHP 之间,并不存在查询优势。(二分法logn)

二叉树节点个数确定的情况下,整颗树的高度越低,节点的查询复杂度越低。

中序遍历所得关键字的值序列从小到大

二叉搜索树的两种极端情况:

完全二叉树,所有节点尽量填满树的每一层,上一层填满后还有剩余节点的话,则由左向右尽量填满下一层。如上图BST所示,即为一颗完全二叉树;

二叉查找树BST-LMLPHP

每一层只有一个节点的二叉树:

二叉查找树BST-LMLPHP

05-27 02:54