在Python中构建高度为'h'的完整二叉树的问题

Question

这是我的代码。完整的二叉树在深度k的时候有2^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. 这些子节点的副本被复制到下一次循环的行里。

这意味着在后续的循环中，你并没有改变你创建的节点（也就是根节点的左子节点和右子节点指向的节点），而是它们的副本，这样原来的节点就保持不变了（它们的左子节点和右子节点都是None）。