Взаимозаменяемы ли цикл и рекурсия? - PullRequest
Новая
       19

Взаимозаменяемы ли цикл и рекурсия?

0 голосов
/ 02 июля 2019

Многие люди говорят, что цикл и рекурсия в основном одинаковы.Единственное различие между ними состоит в том, что некоторые алгоритмы легче понять в рекурсии или итерации.Кроме того, цикл всегда предпочтителен из-за накладных расходов на вызовы функций.Тем не менее, вот код Python для получения высоты бинарного дерева поиска.Как я могу написать это с помощью цикла?

bst = [(1, 2), (3, None), (None, None), (None, None)]

def recursion_height(tree, v=0):
    if v is None:
        return -1
    else:
        return max(recursion_height(tree, tree[v][0]), recursion_height(tree, tree[v][1])) + 1

1 Ответ

0 голосов
/ 02 июля 2019

Это может быть реализовано итеративно с использованием очередей. 

# A binary tree node 
class Node:
# Constructor to create new node 
def __init__(self, data): 
    self.data = data  
    self.left = None
    self.right = None


# Iterative method to find height of Binary Tree 
def treeHeight(root): 

    # Base Case 
    if root is None: 
        return 0

    # Create a empty queue for level order traversal 
    q = [] 

    # Enqueue Root and Initialize Height  
    q.append(root) 
    height = 0 

    while(True):   
        # nodeCount(queue size) indicates number of nodes 
        # at current level 
        nodeCount = len(q) 
        if nodeCount == 0 : 
            return height  

        height += 1 

        # Dequeue all nodes of current level and Enqueue 
        # all nodes of next level 
        while(nodeCount > 0): 
            node = q[0] 
            q.pop(0) 
            if node.left is not None: 
                q.append(node.left) 
            if node.right is not None: 
                q.append(node.right) 

            nodeCount -= 1

# Driver program to test above function 
# Let us create binary tree shown in above diagram 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 

print "Height of tree is", treeHeight(root)
...