二叉排序樹或者是一棵空樹,或者是具有以下幾條性質(zhì)的二叉樹:
1. 若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值;
2. 若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值;
3. 它的左右子樹也分別為二叉排序樹。
二叉排序樹又可以被稱為二叉查找樹,根據(jù)上述定義的結(jié)構(gòu)不難知道,它的查找過程十分簡單,只需要通過不斷的將當(dāng)前結(jié)點(diǎn)的值與需要查找的值進(jìn)行比較,如果相等則直接輸出,如果要查找的值更小則深入至左子樹進(jìn)行比較,否則就深入右子樹進(jìn)行比較,直到找到相應(yīng)的值或者進(jìn)入了一棵不存在的子樹為止。
其查找過程可以描述如下:
而其插入過程同樣也十分簡潔,可以描述如下:
而刪除操作可以描述為如下的兩個(gè)算法:
在本題中,讀入一串整數(shù),首先利用這些整數(shù)構(gòu)造一棵二叉排序樹。另外給定多次查詢,利用構(gòu)造出的二叉排序樹,判斷每一次查詢是否成功。