在Python中以水平顺序横穿二进制树

Question

我有一个python脚本，该脚本生成了给定数学表达式的二进制树。我正在尝试编写一个函数以打印二进制树，如果我在级别订单中穿越它。

例如。如果函数为((2 3(-4(输出应为

   -
  / 
 +   4
/ 
2  3
output: 
-
+ 4
2 3

代码将数学表达式转换为二进制树

from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree
def buildParseTree(fpexp):
        fplist = fpexp.split()
        pStack = Stack()
        eTree = BinaryTree('')
        pStack.push(eTree)
        currentTree = eTree
        for i in fplist:
            if i == '(':
                currentTree.insertLeft('')
                pStack.push(currentTree)
                currentTree = currentTree.getLeftChild()
            elif i not in ['+', '-', '*', '/', ')']:
                currentTree.setRootVal(int(i))
                parent = pStack.pop()
                currentTree = parent
            elif i in ['+', '-', '*', '/']:
                currentTree.setRootVal(i)
                currentTree.insertRight('')
                pStack.push(currentTree)
                currentTree = currentTree.getRightChild()
            elif i == ')':
                currentTree = pStack.pop()
            else:
                raise ValueError
        return eTree

我正在使用标准伪代码进行广度优先搜索。

printTree(Node root)
   if(root == NULL) return
   else
      create a queue 'q'
      q.enqueue(root)
      while(q is not empty)
           root = q.dequeue
           print(root)
           if(leftChild != NULL)
              q.enqueue(leftChild)
           if(rightChild != NULL)
              q.enqueue(rightChild)

以下是我写的python代码，以打印树级。

import sys
class Node:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChid = None

class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self,item):
        self.items.insert(0, item)
    def dequeue(self):
        self.items.pop()
def printNodesInLevels(root):
    if root is None:
        return
    else:
        q = Queue()
        q.enqueue(root)
        while(q is not None):
            root = q.dequeue()
            print(root.getRootVal())
            if(root.leftChild is not None):
                q.enqueue(root.leftChild)
            if(root.rightChild is not None):
                q.enqueue(root.rightChild)

这就是我调用函数的方式。

pt = buildParseTree("( ( 2 + 3 ) - 4 )")
printNodesInLevels(pt)

以下是我收到的错误消息。我认为我没有正确地将树的根传递到打印功能。

无

trackback(最近的最新通话(：文件 " c：/users/yasoda/pycharmprojects/helloworld/binarytree.py"，第77行， 在 printNodesInlevels(pt(文件" c：/users/yasoda/pycharmprojects/helledorld/binarytree.py"，第67行， 在printnodesinlevels中 if(root.leftchild不是一个(：attributeError：'nontype'对象没有属性'leftChild'

Answer 1

您的代码中有两个错误。第一个是，您需要返回Dequeue，

class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self,item):
        self.items.insert(0, item)
    def dequeue(self):
        return self.items.pop()

第二个在while循环中检查队列是否为空，

while(not q.isEmpty()):