二叉排序樹定義

一、定義

二叉排序樹，又叫二叉查找樹，它或者是一棵空樹；或者是具有以下性質的二叉樹：
1. 若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；
2. 若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；
3. 它的左右子樹也分別為二叉排序樹。

二叉搜索樹（BST）又稱二叉查找樹或二叉排序樹。一棵二叉搜索樹是以二叉樹來組織的，可以使用一個鏈表數據結構來表示，其中每一個結點就是一個對象。一般地，除了key和衛(wèi)星數據之外，每個結點還包含屬性lchild、rchild和parent，分別指向結點的左孩子、右孩子和雙親（父結點）。如果某個孩子結點或父結點不存在，則相應屬性的值為空（NIL）。根結點是樹中唯一父指針為NIL的結點，而葉子結點的孩子結點指針也為NIL。