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

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

當(dāng)非空時(shí)，將待插結(jié)點(diǎn)關(guān)鍵字S->key和樹(shù)根關(guān)鍵字t->key進(jìn)行比較，

若s->key = t->key,則無(wú)須插入，若s->key< t->key,則插入到根的左子樹(shù)中，

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

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

說(shuō)明：

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

② 由不同順序的關(guān)鍵字序列，會(huì)得到不同二叉排序樹(shù)。

③ 對(duì)于一個(gè)任意的關(guān)鍵字序列構(gòu)造一棵二叉排序樹(shù)，其實(shí)質(zhì)上對(duì)關(guān)鍵字進(jìn)行排序。

查找的過(guò)程類似，從根結(jié)點(diǎn)開(kāi)始進(jìn)行比較，小于根結(jié)點(diǎn)的在左子樹(shù)上，大于根結(jié)點(diǎn)的在右子樹(shù)上，以此查找下去，直到查找成功或不成功（比較到葉子結(jié)點(diǎn)）。