为什么在构建二叉树时会忽略具有重复值的二叉树节点？

Question

我正在编写代码来创建和打印二叉树。

这是我的代码：

class Node:
    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(1)
root.insert(2)
root.insert(2)
root.insert(3)
root.insert(4)
root.insert(4)
root.insert(3)

root.PrintTree()

我知道上面的代码是正确的，但输出不是我所期望的，我得到 1,2,3,4 ；当我期待 output 成为 1,2,2,3,4,4,3

我怀疑这与数字的重复有关，尤其是 2 和 4。有什么想法可以调整代码以产生我期望的输出吗？谢谢

Answer 1

这是因为当您为重复值插入数据时，您的 if 条件的 none 计算结果为 True，因为您测试 [=15] =] 和 data > self.data 但不适用于 data <= self.data、data >= self.data 或 data == self.data.

采用一种约定，知道你应该把它放在右叶还是左叶，你的代码应该可以正常工作。比如代码：

class Node:
    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data: # Note the <= operator
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data >= self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(1)
root.insert(2)
root.insert(2)
root.insert(3)
root.insert(4)
root.insert(4)
root.insert(3)

root.PrintTree()

产生输出：

请注意，正如@sabik 在评论中指出的那样，使用“右叶”约定可能更有意义。这样做的原因是为了使排序一致。例如，假设您使用“左叶”约定，并执行以下代码：

root = Node(1)
root.insert(2)
root.insert(10)
root.insert(10)

使用“左叶”约定，最后一个 10 将在最左边的树中，而我们可能期望它在最右边的树中。这将使您的树成为“枯叶”：不会使用此叶子作为根添加更多节点。

为什么在构建二叉树时会忽略具有重复值的二叉树节点？

Why do nodes with duplicated values for binary tree get ignored- when I build the binary tree?

python

binary-tree