空二进制树输出中的Python打印特定字符

Question

我现在有一个二进制树，如下所示，

class Node:
    def __init__(self,data):
        # Left Child
        self.left = None
        # Right Child
        self.right = None
        # Node Value
        self.data = data

    def insert(self, data):
    # Compare the new value with the parent node
        if self.data:
            # Less than or equal goes to the Left
            if data <= self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            # Greater than goes to the right
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

假设我们填充了以下二进制树，

Numbers = [4, 7, 9, 1 , 3]

for index in range(len(Numbers)):
    if index == 0:
        root = Node(Numbers[index])
    else:
         root.insert(Numbers[index])

该树生成以下二进制树：

      4
     / \
   1     7
  / \    / \
 .   3  .   9

我已经写了以下二进制树来打印二进制树：

def PrintTree(self, root):
    thislevel = [root]

    while thislevel:
        nextlevel = list()
        Curr_Level = ""
        for n in thislevel:
            Curr_Level += " " + str(n.data)

            if n.left: 
                nextlevel.append(n.left)
            if n.right: 
                nextlevel.append(n.right)

        print(Curr_Level)
        thislevel = nextlevel

root.PrintTree(root=root)

它生成以下输出，

4
1 7
3 9

但是，我希望代码打印代码带有“@”的空条目，即我希望我的代码输出以下内容：

4
1 7
@ 3 @ 9

如何调整我的printtree函数以实现这一目标？

Answer 1

运行BFS的修改版本。更具体地说，从根节点开始运行广度第一次搜索（BFS）。这将为每个节点分配一个级别。在BFS期间，当当前节点有一个失踪的孩子时，将其位置添加到FIFO队列。每次将其从队列中删除时打印一个节点。每次从队列中删除具有新级别的节点时，都会以新的线路打印。