二叉排序樹定義

一、定義

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

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