0

我试图在插入的每一步之后打印二叉搜索树的每个阶段。但是，我的代码生成的输出似乎错过了初始根数据插入步骤，并且还重复了某些阶段。我需要一个干净简单的方法来做到这一点。有没有办法使用__dict__.values().

我的代码：

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

    def addNode(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.addNode(data)  # recursively calling addNode method
        else:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.addNode(data)

        if not self.left is None and not self.right is None:
            print self.left.data, self.data, self.right.data
        elif self.left is None and not self.right is None:
            print None, self.data, self.right.data
        elif not self.left is None and self.right is None:
            print self.left.data, self.data, None

if __name__ == '__main__':
    n = Node(5)
    #print n.__dict__.values()
    n.addNode(3)
    n.addNode(2)
    n.addNode(8)
    n.addNode(4)

生成的输出：

3 5 None
2 3 None
3 5 None
3 5 8
2 3 4
3 5 8

预期输出：

None 5 None
3 5 None
2 3 None
3 5 8
2 3 4
4

2 回答 2

1

由于您设计的方式，打印步骤发生在每个递归步骤中，从内到外。所以，为了更有意义，让我们来看看这个。n.addNode(3)给我们的你

3 5 None

没有惊喜。但是当你说你期望：

2 3 None

但两者兼得，

2 3 None
3 5 None

这是因为要做n.addNode(2)的是检查第一级（3 5 None）然后查看较低级别（具有data属性 =的节点3）。因此，“从内到外”打印，我们得到2 3 None(new subtree) 然后又是第一级，3 5 None. 出于同样的原因，当你期待时，

2 3 4

你反而得到，

2 3 4
3 5 8

None 5 None初始树（您期望的位置）没有打印的事实是一个单独的问题。这只是因为您正在初始化data属性并且永远不会进入打印部分，因为您没有调用addNone.

一个可能的解决方案（仍然保持您的结构）是仅在您将节点添加到树结构并手动打印初始子树时打印。也许写这样的东西：

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

    def addNode(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
                self.printSubtree()
            else:
                self.left.addNode(data)  # recursively calling addNode method
        else:
            if self.right is None:
                self.right = Node(data)
                self.printSubtree()
            else:
                self.right.addNode(data)

    def printSubtree(self):
        if not self.left is None and not self.right is None:
            print self.left.data, self.data, self.right.data
        elif self.left is None and not self.right is None:
            print None, self.data, self.right.data
        elif not self.left is None and self.right is None:
            print self.left.data, self.data, None
        else:
            print None, self.data, None

if __name__ == '__main__':
    n = Node(5)
    n.printSubtree()
    n.addNode(3)
    n.addNode(2)
    n.addNode(8)
    n.addNode(4)
于 2013-03-29T04:29:29.507 回答
0

1-您在添加节点后打印，因此您无法按预期找到具有 None、Number、None 的元素。（因此请尝试在添加节点之前移动此部分）。2-打印时您只考虑了三种可能性，但还有另一种可能性，当左右节点均为无时，请尝试添加此选项。

于 2013-03-29T03:44:40.407 回答