設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均查找長(zhǎng)度為？二層正解最壞的情況是深度為n的單叉樹為（N1）/2最好的情況是形狀均勻，半搜索約為log2 nPS:如果構(gòu)造完成，例如：則平均搜索長(zhǎng)度為：（1

設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均查找長(zhǎng)度為？

二層正解

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

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

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

則平均搜索長(zhǎng)度為：（1×12×23×44×3）/10=2.9二叉樹和二叉排序樹的區(qū)別在于：節(jié)點(diǎn)不同，鍵值不同，子樹類型不同。

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

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

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

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

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

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