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

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

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

二叉查找樹和二叉排序樹有什么區(qū)別？

二叉樹和二叉排序樹的區(qū)別在于：不同的子樹節(jié)點(diǎn)、不同的鍵值和不同的子樹類型。

1、 1. 二叉樹：二叉樹左/右子樹上所有節(jié)點(diǎn)的值可以大于、等于或小于其根節(jié)點(diǎn)的值。

2. 二叉排序樹：如果二叉排序樹的左/右子樹不為空，則左/右子樹上所有節(jié)點(diǎn)的值都小于其根節(jié)點(diǎn)的值。

2、二叉樹：二叉樹可以有具有相等鍵值的節(jié)點(diǎn)。

2. 二叉排序樹：二叉排序樹沒有具有相等鍵值的節(jié)點(diǎn)。

3、 1. 二叉樹：二叉樹的左右子樹也是二叉樹。

2. 二叉排序樹：二叉排序樹的左右子樹也是二叉排序樹

二層正解

最壞的情況是深度為n的單叉樹是（n1）/2

最好的情況是形狀均勻，半搜索約為log2n

PS:如果構(gòu)造完成，例如：

則平均搜索長度為：（1×12×23×44×3）/10=2.9