如何在Python中将二叉树打印为节点结构

2024-03-29 12:32:14 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个python code来将一个字符串数学表达式转换成一个二叉树,并对树的节点进行排序,这样左子节点总是比右子节点小。我想按以下顺序打印二叉树。在

例如,考虑数学表达式((2*75)/4)。buildParseTree()将字符串表达式转换为树,printNodeInLevels()重新排列节点,使每个级别的左子节点小于右子节点。操作数<;运算符和运算符的顺序为“+”<;“-”<;“*”<;“/”。如果树的结构是这样的

  +
  /\
 4  *
    /\
   2  75

我想打印如下。我该怎么做?因为数学表达式的长度一直在变化,例如(24*2),((5-1)*(2/3)),(20-(5+4))等

^{pr2}$

我已经找到了按级别打印节点的方法,就像在按顺序遍历中一样模式。如果我按如下方式调用该方法,它将打印以下内容:

pt = buildParseTree("( ( 2 * 74 ) / 4 )")

printNodesInLevels(pt)

输出:

/ 
4 * 
2 74 

Tags: 方法字符串ltpt节点排序顺序表达式
3条回答

首先,您应该阅读python的PEP8代码约定,因为它说函数、属性和变量应该是snake_的大小写。在

你正在以一种迭代的方式打印,这意味着你不能在等腰三角形中打印它,因为你不知道底部(树的最低部分)的大小,以迭代的方式,你应该像一个90度角的三角形一样打印它。在

或者您可以将所有信息收集到一个列表或一个字符串中,然后将其格式化并打印出来。想想头,然后想想孩子们中间有线。在

简单而粗糙:

from collections import deque
def print_tree(root):
    res = []
    q = deque([root])
    while q:
        row = []
        for _ in range(len(q)):
            node = q.popleft()
            if not node:
                row.append("#")
                continue
            row.append(node.val)
            q.append(node.left)
            q.append(node.right)
        res.append(row)
    rows = len(res)
    base = 2**(rows)
    for r in range(rows):
        for v in res[r]:
            print("." * (base), end = "")
            print(v, end = "")
            print("." * (base - 1), end = "")
        print("|")
        base //= 2

print_tree(root)

我创建了一个函数来打印任何二叉树结构。在

它非常通用,只需要一个起始节点(根)和一个函数(或lambda)就可以获得标签和左/右子节点:

通常在节点类上使用它:

printBTree(rootNode,lambda n: (n.operand, n.left, n.right) )

# assuming the Node class has a string property named operand
# and left,right properties that return a Node or None

一个二次方程(-b+/-sqrt(b**2-4*A*c))/(2*A)可以这样打印:

^{pr2}$

下面是printBTree函数:

import functools as fn

def printBTree(node, nodeInfo=None, inverted=False, isTop=True):

   # node value string and sub nodes
   stringValue, leftNode, rightNode = nodeInfo(node)

   stringValueWidth  = len(stringValue)

   # recurse to sub nodes to obtain line blocks on left and right
   leftTextBlock     = [] if not leftNode else printBTree(leftNode,nodeInfo,inverted,False)

   rightTextBlock    = [] if not rightNode else printBTree(rightNode,nodeInfo,inverted,False)

   # count common and maximum number of sub node lines
   commonLines       = min(len(leftTextBlock),len(rightTextBlock))
   subLevelLines     = max(len(rightTextBlock),len(leftTextBlock))

   # extend lines on shallower side to get same number of lines on both sides
   leftSubLines      = leftTextBlock  + [""] *  (subLevelLines - len(leftTextBlock))
   rightSubLines     = rightTextBlock + [""] *  (subLevelLines - len(rightTextBlock))

   # compute location of value or link bar for all left and right sub nodes
   #   * left node's value ends at line's width
   #   * right node's value starts after initial spaces
   leftLineWidths    = [ len(line) for line in leftSubLines  ]                            
   rightLineIndents  = [ len(line)-len(line.lstrip(" ")) for line in rightSubLines ]

   # top line value locations, will be used to determine position of current node & link bars
   firstLeftWidth    = (leftLineWidths   + [0])[0]  
   firstRightIndent  = (rightLineIndents + [0])[0] 

   # width of sub node link under node value (i.e. with slashes if any)
   # aims to center link bars under the value if value is wide enough
   # 
   # ValueLine:    v     vv    vvvvvv   vvvvv
   # LinkLine:    / \   /  \    /  \     / \ 
   #
   linkSpacing       = min(stringValueWidth, 2 - stringValueWidth % 2)
   leftLinkBar       = 1 if leftNode  else 0
   rightLinkBar      = 1 if rightNode else 0
   minLinkWidth      = leftLinkBar + linkSpacing + rightLinkBar
   valueOffset       = (stringValueWidth - linkSpacing) // 2

   # find optimal position for right side top node
   #   * must allow room for link bars above and between left and right top nodes
   #   * must not overlap lower level nodes on any given line (allow gap of minSpacing)
   #   * can be offset to the left if lower subNodes of right node 
   #     have no overlap with subNodes of left node                                                                                                                                 
   minSpacing        = 2
   rightNodePosition = fn.reduce(lambda r,i: max(r,i[0] + minSpacing + firstRightIndent - i[1]), \
                                 zip(leftLineWidths,rightLineIndents[0:commonLines]), \
                                 firstLeftWidth + minLinkWidth)

   # extend basic link bars (slashes) with underlines to reach left and right
   # top nodes.  
   #
   #        vvvvv
   #       __/ \__
   #      L       R
   #
   linkExtraWidth    = max(0, rightNodePosition - firstLeftWidth - minLinkWidth )
   rightLinkExtra    = linkExtraWidth // 2
   leftLinkExtra     = linkExtraWidth - rightLinkExtra

   # build value line taking into account left indent and link bar extension (on left side)
   valueIndent       = max(0, firstLeftWidth + leftLinkExtra + leftLinkBar - valueOffset)
   valueLine         = " " * max(0,valueIndent) + stringValue
   slash             = "\\" if inverted else  "/"
   backslash         = "/" if inverted else  "\\"
   uLine             = "¯" if inverted else  "_"

   # build left side of link line
   leftLink          = "" if not leftNode else ( " " * firstLeftWidth + uLine * leftLinkExtra + slash)

   # build right side of link line (includes blank spaces under top node value) 
   rightLinkOffset   = linkSpacing + valueOffset * (1 - leftLinkBar)                      
   rightLink         = "" if not rightNode else ( " " * rightLinkOffset + backslash + uLine * rightLinkExtra )

   # full link line (will be empty if there are no sub nodes)                                                                                                    
   linkLine          = leftLink + rightLink

   # will need to offset left side lines if right side sub nodes extend beyond left margin
   # can happen if left subtree is shorter (in height) than right side subtree                                                
   leftIndentWidth   = max(0,firstRightIndent - rightNodePosition) 
   leftIndent        = " " * leftIndentWidth
   indentedLeftLines = [ (leftIndent if line else "") + line for line in leftSubLines ]

   # compute distance between left and right sublines based on their value position
   # can be negative if leading spaces need to be removed from right side
   mergeOffsets      = [ len(line) for line in indentedLeftLines ]
   mergeOffsets      = [ leftIndentWidth + rightNodePosition - firstRightIndent - w for w in mergeOffsets ]
   mergeOffsets      = [ p if rightSubLines[i] else 0 for i,p in enumerate(mergeOffsets) ]

   # combine left and right lines using computed offsets
   #   * indented left sub lines
   #   * spaces between left and right lines
   #   * right sub line with extra leading blanks removed.
   mergedSubLines    = zip(range(len(mergeOffsets)), mergeOffsets, indentedLeftLines)
   mergedSubLines    = [ (i,p,line + (" " * max(0,p)) )       for i,p,line in mergedSubLines ]
   mergedSubLines    = [ line + rightSubLines[i][max(0,-p):]  for i,p,line in mergedSubLines ]                        

   # Assemble final result combining
   #  * node value string
   #  * link line (if any)
   #  * merged lines from left and right sub trees (if any)
   treeLines = [leftIndent + valueLine] + ( [] if not linkLine else [leftIndent + linkLine] ) + mergedSubLines

   # invert final result if requested
   treeLines = reversed(treeLines) if inverted and isTop else treeLines

   # return intermediate tree lines or print final result
   if isTop : print("\n".join(treeLines))
   else     : return treeLines                                       

下面是一个使用简单TreeNode类生成的输出类型的示例。在

class TreeNode:

   def __init__(self,rootValue):
       self.value = rootValue
       self.left  = None
       self.right = None

   def addValue(self,newValue):
      if newValue == self.value: return self
      if newValue < self.value:
         if self.left : return self.left.addValue(newValue)
         self.left = TreeNode(newValue)
         return self.left
      if self.right : return self.right.addValue(newValue)
      self.right = TreeNode(newValue)
      return self.right

   def printTree(self):
      printBTree(self,lambda n:(str(n.value),n.left,n.right))      

root = TreeNode(80)

root.addValue(50)
root.addValue(90)
root.addValue(10)
root.addValue(60)
root.addValue(30)
root.addValue(70)
root.addValue(55)
root.addValue(5)
root.addValue(35)
root.addValue(85)

root.printTree()

这将产生以下输出:

#              80
#          ___/  \___
#        50          90
#     __/  \__      /
#   10        60  85
#  /  \      /  \
# 5    30  55    70
#        \
#         35

该函数的通用性足以处理未存储在对象层次结构中的二叉树结构。以下是如何使用它从包含堆树的列表中打印的示例:

def printHeapTree(tree, inverted=False):

    def getNode(index):
        left  = index * 2 + 1
        right = index * 2 + 2
        left  = left  if left  < len(tree) and tree[left]  else None
        right = right if right < len(tree) and tree[right] else None
        return (str(tree[index]), left, right)

    printBTree(0,getNode,inverted)


formula = ["+","4","*",None,None,"2","75"]
printHeapTree(formula)

#   +
#  / \
# 4   *
#    / \
#   2   75

此功能将自动调整宽标签的缩进:

family = [ "Me","Paul","Rosa","Vincent","Jody","John","Kate"]
printHeapTree(family)

#                Me
#            ___/  \___
#        Paul          Rosa
#        /  \          /  \
# Vincent    Jody  John    Kate

它还可以将树倒置打印(这对于家谱来说是合适的):

printHeapTree(family,inverted=True)

# Vincent    Jody  John    Kate
#        \  /          \  /
#        Paul          Rosa
#            ¯¯¯\  /¯¯¯
#                Me

相关问题 更多 >