题目:二叉排序树的查找。
解题思路:其查找过程是:
若二叉排序树为空,则查找失败,结束查找,返回信息null;
否则,将要查找的值与二叉排序树根结点的值进行比较,
若相等,则查找成功,结束查找,返回被查到结点的地址;
若不相等,则根据要查找的值与根结点值的大小关系决定是到根结点的左子树还是右子树中继续查找(查找过程同上),直到查找成功或者查找失败为止。
具体算法:
(一)非递归算法
function searchBST(T, item) {
let p = T
while ( p!=null ) {
if ( p.data == item ) {
return p
}
if ( item < p.data ) {
p = p.lchild
} else {
p = p.rchild
}
}
return null
}
(二)递归算法
function searchBST(T, item) {
if ( T==null ) {
return null
}
if ( T.data == item ) {
return T
}
if ( item < T.data ) {
return searchBST(T.lchild, item)
} else {
return searchBST(T.rchild, item)
}
}
测试:
这里使用到建立二叉排序树sortTree(K)
let K = [5, 10, 5, 20, 17, 12, 19, 2]
var BST = sortTree(K)
searchBST(BST, 17)