2046533912671160在等概率的情况下，查找成功的平均查找长度为：1×1+2×2+3×3+3×4+2×5+1×6=3.5ASL成动1211/81
18 25 2 4 11 46 39 32 53 74 67 60 在等概率的情况下，查找成功的平均查找长度为： 11/81
25184653393274671160在等概率的情况下，查找不成功的平均查找长度为：1×2+3×3+4×4+3×5+2×64.15ASL不成功1312/81
18 25 2 4 11 46 39 32 53 74 67 60 在等概率的情况下，查找不成功的平均查找长度为： 12/81
3．二叉排序树的查找//在二叉排序树中查找关键字为k的结点public BSTNode SearchBST(int k)t//r为二叉排序树的根结点returnSearchBsTi(r,k);TprivateBSTNodeSearchBST1（BSTNodep，intk）//被SearchBST方法调用//空树返回null{if (p==null) return null;//找到后返回pif (p.key==k) return p;if (k<p.key)1/在左子树中递归查找return SearchBsT1(p.lchild,k);else1/在右子树中递归查找return SearchBSTi(p.rchild,k);13/81
3. 二叉排序树的查找 public BSTNode SearchBST(int k) //在二叉排序树中查找关键字为k的结点 { return SearchBST1(r,k); //r为二叉排序树的根结点 } private BSTNode SearchBST1(BSTNode p,int k) //被SearchBST方法调用 { if (p==null) return null; //空树返回null if (p.key==k) return p; //找到后返回p if (k<p.key) return SearchBST1(p.lchild,k); //在左子树中递归查找 else return SearchBST1(p.rchild,k); //在右子树中递归查找 } 13/81
与折半查找的判定树类似，在二叉排序树中每个空指针处添加一个外部结点。在二叉排序树中查找时，若查找成功，则是从根结点出发走了一条从根结点到查找到结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个外部结点的路。因此与折半查找类似，查找中关键字比较的次数不超过树的高度。14/81
与折半查找的判定树类似，在二叉排序树中每个空指针处添加一个外 部结点。 在二叉排序树中查找时，若查找成功，则是从根结点出发走了一条从 根结点到查找到结点的路径。 若查找不成功，则是从根结点出发走了一条从根到某个外部结点的路 径。 因此与折半查找类似，查找中关键字比较的次数不超过树的高度。 14/81
说明一个关键字集合可以有多个不同顺序的关键字序列，对于不同的关键字序列，CreateBST()算法创建的二叉排序树可能不同。例如，关键字序列为（5，2，1，6，7，4，3），创建的二叉排序树如图（a)所示。若关键字序列为（1，2，3，4，5，6，7），创建的二叉排序树如图（b）所示。（a）高度为4(b) 高度为715/81
一个关键字集合可以有多个不同顺序的关键字序列，对于不同的关键字 序列，CreateBST()算法创建的二叉排序树可能不同。 例如，关键字序列为（5，2，1，6，7，4，3），创建的二叉排序树如 图(a)所示。若关键字序列为（1，2，3，4，5，6，7），创建的二叉 排序树如图(b)所示。 1 2 3 4 5 6 7 （b）高度为7 5 2 6 1 4 3 7 （a）高度为4 说明 15/81