python - BST 层序遍历

Question

我有一些关于 BST 的代码，我想打印出输入，使用 BST Level-Order Traversal，node-left-right。这是代码:

import sys

class Node:
    def __init__(self,data):
        self.right=self.left=None
        self.data = data
class Solution:
    def insert(self,root,data):
        if root==None:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                cur=self.insert(root.right,data)
                root.right=cur
        return root


    def levelOrder(self,root):
        #Write your code here
        nodes_to_search = list()
        nodes_traversed = ''
        nodes_to_search.append(root)
        while len(nodes_to_search) > 0:
            nodes = nodes_to_search.pop(0)
            if nodes.left:
                nodes_to_search.append(nodes.left)
            if nodes.right:
                nodes_to_search.append(nodes.right)
            nodes_traversed += str(nodes.data) + ' '
        print(nodes_traversed)


T=int(input())
myTree=Solution()
root=None
for i in range(T):
    data=int(input())
    root=myTree.insert(root,data)
myTree.levelOrder(root)


6
3
5
4
7
2
1 # it prints out 3 5 2 1 4 7

输出如我所料，node-left-right。但我不明白 levelOrder() 函数是如何打印出来的？

Answer 1

简单的List操作，保持顺序

1. 每次我们从 nodes_search_list 中获取第一个元素

nodes = nodes_to_search.pop(0)

1. 将左 child 推到右 child 之前(所以我们总是先左再右)

            if nodes.left:
                nodes_to_search.append(nodes.left)
            if nodes.right:
                nodes_to_search.append(nodes.right)