Проблема построения полного бинарного дерева высотой 'h' в Python

Question

Вот мой код. Полное двоичное дерево имеет 2 ^ k узлов на глубине k.

class Node:

    def __init__(self, data):
        # initializes the data members
        self.left = None
        self.right = None
        self.data = data


root = Node(data_root)

def create_complete_tree():
        row = [root]

        for i in range(h):

            newrow = []
            for node in row:
                left = Node(data1)  
                right = Node(data2)  

                node.left = left
                node.right = right

                newrow.append(left)
                newrow.append(right)


            row = copy.deepcopy(newrow)



def traverse_tree(node):
        if node == None:
            return
        else:
            traverse_tree(node.left)
            print node.data
            traverse_tree(node.right)

create_complete_tree()

print 'Node traversal'

traverse_tree(root)

Обход дерева дает только данные о корне и его дочерних элементах. Что я делаю не так?

Answer 1

Основная проблема заключается в том, что вы используете глубокую копию во временном списке. Посмотрим, что происходит на каждой итерации:

1. Ваш начальный корень проверяется, а дочерние узлы создаются
2. Эти дочерние узлы размещены в новой строке
3. Копии этих дочерних узлов копируются в строку для следующей итерации.

Это означает, что последующая итерация будет состоять не из созданных вами узлов (и на которые указывают root.left и root.right), а из их копий, оставляя оригиналы в их текущем состоянии (с None для .left и .right)