用于在二叉树中搜索的伪代码

Question

我需要一个C++的伪代码,它将搜索树以找到值为"z"的节点.

该函数被赋予树的根节点以开始.树具有每个节点最多具有两个子节点的属性.每个节点都有3个属性:left child,right child和value.

Answer 1

以下伪代码将按升序执行树所需的操作.

def findval (node,lookfor):
    if node is null:
        return null
    if node.val is equal to lookfor:
        return node
    if node.val is less than lookfor
        return findval (node.right,lookfor)
    return findval (node.left,lookfor)

被称为:

znode = findval (root, "z")

如果没有节点,它将为您提供节点或null.

如果要避免递归,可以使用迭代解决方案:

def findval (node,lookfor):
    while node is not null:
        if node.val is equal to lookfor:
            break
        if node.val is less than lookfor:
            node = node.right
        else:
            node = node.left
    return node

显然,您可以进行各种增强,例如允许不同的顺序,或回调比较功能,或允许重复键,但这是二叉树搜索的规范示例.