二叉排序樹構(gòu)造過程

二叉排序樹的構(gòu)造過程：按照給定序列，以此將結(jié)點插入二叉排序樹中，在二叉排序樹中插入新結(jié)點，要保證插入后的二叉樹仍符合二叉排序樹的定義。

插入過程：若二叉排序樹為空，則待插入結(jié)點*S作為根結(jié)點插入到空樹中；

當非空時，將待插結(jié)點關鍵字S->key和樹根關鍵字t->key進行比較，

若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，

若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，

如此進行下去，直到把結(jié)點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹已有相同關鍵字的結(jié)點為止。

說明：

① 每次插入的新結(jié)點都是二叉排序樹上新的葉子結(jié)點。

② 由不同順序的關鍵字序列，會得到不同二叉排序樹。

③ 對于一個任意的關鍵字序列構(gòu)造一棵二叉排序樹，其實質(zhì)上對關鍵字進行排序。

查找的過程類似，從根結(jié)點開始進行比較，小于根結(jié)點的在左子樹上，大于根結(jié)點的在右子樹上，以此查找下去，直到查找成功或不成功（比較到葉子結(jié)點）。