Así que estoy intentando implementar una función de búsqueda en mi clase BinaryTree. Básicamente, devuelvo un valor True de la función recursiva _search, pero sigue ejecutando el resto del ciclo en lugar de romper el método _search. Pensé que se suponía que return saldría del método. A continuación se muestra la salida y el código.

Salida:

1
2
4
5
3
 
1
2
4
5
3

Código:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def print_tree(self):
        """Print out all tree nodes
        as they are visited in
        a pre-order traversal."""
        
        return ""

    def preorder_print(self, start, traversal):
        """Helper method - use this to create a 
        recursive print solution."""
        return traversal


    def search(self, find_val):
        """Return True if the value
        is in the tree, return
        False otherwise."""
        return self._search(self.root, find_val)

        
    def _search(self, current_node, find_val):
        """Helper method - use this to create a 
        recursive search solution."""
        # check if current node = val
        print(current_node.value)
        if current_node.value == find_val:
            return True 
        # 
        elif current_node.left or current_node.right:
            self._search(current_node.left, find_val)
            self._search(current_node.right, find_val)
        return False
        



# Set up tree
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

# Test search
# Should be True
tree.search(4)
print(" ")
# Should be False
tree.search(6)

# Test print_tree
# Should be 1-2-4-5-3
print tree.print_tree()
1
Trituraite 2 dic. 2020 a las 13:25

2 respuestas

La mejor respuesta

Lo primero que da la entrada no es un árbol de búsqueda binario, es un árbol binario.

Para BST, todos los nodos secundarios del lado derecho deben ser mayores que la raíz y todos los nodos del lado izquierdo deben ser más pequeños que la raíz.

Pero para esta solución de árbol binario, el problema está a continuación:

        elif current_node.left or current_node.right:
            self._search(current_node.left, find_val)
            self._search(current_node.right, find_val) 

Entonces, si el nodo izquierdo o derecho está allí, está buscando recursivamente en ambos lados y no devuelve nada. Por lo tanto, debe cambiarlo de la siguiente manera:

        elif current_node.left:
            return self._search(current_node.left, find_val)
        elif current_node.right:
            return self._search(current_node.right, find_val)
0
Vijay 2 dic. 2020 a las 10:49

Como dijo @Vijay, debe cambiar el siguiente fragmento de código:

elif current_node.left or current_node.right:
    self._search(current_node.left, find_val)
    self._search(current_node.right, find_val)

A algo similar al siguiente código:

        if current_node.value == find_val:
            return True
        if current_node.left:
            if self._search(current_node.left, find_val) == True:
                return True
        if current_node.right:
            if self._search(current_node.right, find_val) == True:
                return True

        return False

Lo que funcionó para mí en todo el ejemplo:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def print_tree(self):
        """Print out all tree nodes
        as they are visited in
        a pre-order traversal."""

        return ""

    def preorder_print(self, start, traversal):
        """Helper method - use this to create a
        recursive print solution."""
        return traversal

    def search(self, find_val):
        """Return True if the value
        is in the tree, return
        False otherwise."""
        return self._search(self.root, find_val)

    def _search(self, current_node, find_val):
        """Helper method - use this to create a
        recursive search solution."""
        # check if current node = val
        print(current_node.value)
        if current_node.value == find_val:
            return True
        if current_node.left:
            if self._search(current_node.left, find_val) == True:
                return True
        if current_node.right:
            if self._search(current_node.right, find_val) == True:
                return True

        return False


# Set up tree
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

# Test search
# Should be True
print("Should be True")
print(tree.search(4))
print(tree.search(1))
print(tree.search(2))
print(tree.search(3))
print(tree.search(5))

print("Should be False")
# Should be False
print(tree.search(6))
print(tree.search(0))
print(tree.search(8))

Salida

Should be True
1
2
4
True
1
True
1
2
True
1
2
4
5
3
True
1
2
4
5
True

Should be False
1
2
4
5
3
False
1
2
4
5
3
False
1
2
4
5
3
False
0
Rene 2 dic. 2020 a las 11:03