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 队列中。每次从队列中删除节点时打印一个节点。每次从队列中删除具有新级别的节点时，在新行中打印。

Python 在空二叉树输出中打印特定字符

Python Printing Specific Character in Empty Binary Tree Output

python

binary-tree