二叉排序樹(shù)的構(gòu)造和查找方法？二叉排序樹(shù)的構(gòu)造過(guò)程：按照給定的順序，將節(jié)點(diǎn)插入到二叉排序樹(shù)中，再將新節(jié)點(diǎn)插入到二叉排序樹(shù)中，以保證插入的二叉樹(shù)仍然符合二叉排序樹(shù)的定義。插入過(guò)程：如果二叉排序樹(shù)為空，則將

二叉排序樹(shù)的構(gòu)造和查找方法？

二叉排序樹(shù)的構(gòu)造過(guò)程：按照給定的順序，將節(jié)點(diǎn)插入到二叉排序樹(shù)中，再將新節(jié)點(diǎn)插入到二叉排序樹(shù)中，以保證插入的二叉樹(shù)仍然符合二叉排序樹(shù)的定義。插入過(guò)程：如果二叉排序樹(shù)為空，則將要插入的節(jié)點(diǎn)*s作為根節(jié)點(diǎn)插入到空樹(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ò)程相同。此過(guò)程將繼續(xù)，直到節(jié)點(diǎn)*作為新葉插入到二叉排序樹(shù)中，或者直到在樹(shù)中找到具有相同關(guān)鍵字的節(jié)點(diǎn)為止。注：①每插入一個(gè)新節(jié)點(diǎn)，在二叉排序樹(shù)中都是一個(gè)新的葉節(jié)點(diǎn)。（2） 不同的關(guān)鍵字序列可以得到不同的二叉排序樹(shù)。（3） 對(duì)于任意的關(guān)鍵字序列，構(gòu)造一個(gè)二叉排序樹(shù)對(duì)關(guān)鍵字進(jìn)行實(shí)質(zhì)性排序。搜索過(guò)程類(lèi)似，從根節(jié)點(diǎn)開(kāi)始進(jìn)行比較，小于根節(jié)點(diǎn)的在左子樹(shù)中，大于根節(jié)點(diǎn)的在右子樹(shù)中，這樣查找下去，直到搜索成功或不成功（與葉節(jié)點(diǎn)相比）。