如何在控制台中“绘制”二叉树？

Question

如何在控制台中“绘制”二叉树？

3

如何在Swift中打印二叉树，使得输入的79561打印出以下输出：

我尝试使用For循环和If语句编写代码进行排列，但是它没有成功。

我的代码如下：

import UIKit

//Variable "node" used only to arrange it in output.
var node = "0"
var space = " "
var linkLeft = "/"
var linkRight = "\\"
var str = "Hello, playground"

var height = 6
var width = height * 2 + 1

print()

//Height
for h in 1...height {
    //Width
    for w in 1...width {
        switch h {
        case 1:
            if(w == width/2 + h) {
                print(node, terminator: "")
            } else {
                print(space, terminator: "")
            }

            if (w == width) {
                print()
            }
        case 2:
            //print(linkLeft, terminator: "")
            if(w == width/3 + h) {
                print(linkLeft, terminator: "")
            } else if(w == width/3 + h + 4) {
                print(linkRight, terminator: "")
            } else {
                print(space, terminator: "")
            }

            if (w == width) {
                print()
            }
        case 3:
            if(w == width/5 + h) {
                print(node, terminator: "")
            } else if(w == width/h + h){
                print(node, terminator: "")
            } else {
                print(space, terminator: "")
            }

            if (w == width) {
                print()
            }
            break
        default:
            break
        }
    }
}

我尝试使用两个For循环，一个用于高度，另一个用于宽度。但是，如果节点数量发生变化，它将无法正常工作。目前我只尝试调整链接（/和\），节点和空格的位置，因此它无法正常工作。有可能有其他方法吗？

- Emm

您可以根据以下链接适应https://dev59.com/K2445IYBdhLWcg3wQX6G。 - Jean-Baptiste Yunès

@Jean-BaptisteYunès 是的，但那是用Java编写的，而我对Java和Swift都是初学者。所以对我来说很难从Java转换成Swift。 - Emm

嗯，你需要（1）对数据树进行递归解析，（2）使用节点之间的距离作为树高度函数，通常可以使用2的幂次方函数（叶子节点距离为1，叶子节点的父节点距离为2，父节点的父节点距离为4，以此类推）。 - Jean-Baptiste Yunès

严格来说，这是不可能的，因为树的宽度呈线性增长，但你必须绘制的节点数量呈指数增长。 - taylor swift

2个回答

0

我发现并稍作修改的适用于Swift的简单方法

import UIKit
// Binary tree by class
class TreeNode
{
    var value : Int
    var left  : TreeNode? = nil
    var right : TreeNode? = nil
    
    init(_ rootValue:Int) {
        value = rootValue
    }
    
    @discardableResult
    func addValue( _ newValue:Int) -> TreeNode
    {
        if newValue == value {
            return self
        }
        else if newValue < value {
            if let newNode = left?.addValue(newValue) {
                return newNode
            }
            left = TreeNode(newValue)
            return left!
        }
        else {
            if let newNode = right?.addValue(newValue) {
                return newNode
            }
            right = TreeNode(newValue)
            return right!
        }
    }
    func myPrint () {
        printTree(prefix: "", n: self, isLeft: false)
    }
}

func printTree(prefix: String, n: TreeNode, isLeft: Bool) {
        print(prefix, (isLeft ? "|-- " : "\\-- "), n.value)
        if n.left != nil {
            printTree(prefix: "\(prefix) \(isLeft ? "|   " : "   ") ", n: n.left!, isLeft: true)
        }
        if n.right != nil {
            printTree(prefix: "\(prefix) \(isLeft ? "|   " : "   ") ", n: n.right!, isLeft: false)
        }
    }

输入

var 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.addValue(84)
root.addValue(86)
root.addValue(92)
root.addValue(100)

root.myPrint()

输出

 \--  80
      |--  50
      |     |--  10
      |     |     |--  5
      |     |     \--  30
      |     |          \--  35
      |     \--  60
      |          |--  55
      |          \--  70
      \--  90
           |--  85
           |     |--  84
           |     \--  86
           \--  92
                \--  100

- Artem Lushchan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alain T. · Accepted Answer

首先你需要定义一个层次树结构（类），它允许递归遍历树节点。如何实现并不重要，只要它能提供一个描述性字符串并访问其左右子节点即可。

例如（我用这个来进行测试）：

class TreeNode
{
   var value : Int
   var left  : TreeNode? = nil
   var right : TreeNode? = nil

   init(_ rootValue:Int)
   { value = rootValue }

   @discardableResult
   func addValue( _ newValue:Int) -> TreeNode
   {
      if newValue == value // exclude duplicate entries
      { return self }
      else if newValue < value
      { 
         if let newNode = left?.addValue(newValue)
         { return newNode }
         left = TreeNode(newValue)
         return left!
      }
      else
      {
         if let newNode = right?.addValue(newValue)
         { return newNode }
         right = TreeNode(newValue)
         return right!
      }
   }
}

然后，您可以创建一个递归函数来获取要打印的行。每行都需要知道较低级别的行，因此行列表需要从下往上构建。递归是实现这种相互依存关系的简单方法。

以下是一个通用函数的示例，可用于任何二叉树类。它需要一个根节点和一个函数（或闭包）来访问节点的描述和左/右子节点：

public func treeString<T>(_ node:T, reversed:Bool=false, isTop:Bool=true, using nodeInfo:(T)->(String,T?,T?)) -> String
{
   // node value string and sub nodes
   let (stringValue, leftNode, rightNode) = nodeInfo(node)

   let stringValueWidth  = stringValue.count

   // recurse to sub nodes to obtain line blocks on left and right
   let leftTextBlock     = leftNode  == nil ? []
                         : treeString(leftNode!,reversed:reversed,isTop:false,using:nodeInfo)
                           .components(separatedBy:"\n")

   let rightTextBlock    = rightNode == nil ? []
                         : treeString(rightNode!,reversed:reversed,isTop:false,using:nodeInfo)
                           .components(separatedBy:"\n")

   // count common and maximum number of sub node lines
   let commonLines       = min(leftTextBlock.count,rightTextBlock.count)
   let subLevelLines     = max(rightTextBlock.count,leftTextBlock.count)

   // extend lines on shallower side to get same number of lines on both sides
   let leftSubLines      = leftTextBlock  
                         + Array(repeating:"", count: subLevelLines-leftTextBlock.count)
   let rightSubLines     = rightTextBlock 
                         + Array(repeating:"", count: subLevelLines-rightTextBlock.count)

   // 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
   let leftLineWidths    = leftSubLines.map{$0.count}                             
   let rightLineIndents  = rightSubLines.map{$0.prefix{$0==" "}.count  } 

   // top line value locations, will be used to determine position of current node & link bars
   let firstLeftWidth    = leftLineWidths.first   ?? 0
   let firstRightIndent  = rightLineIndents.first ?? 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:    / \   /  \    /  \     / \ 
   //
   let linkSpacing       = min(stringValueWidth, 2 - stringValueWidth % 2)
   let leftLinkBar       = leftNode  == nil ? 0 : 1
   let rightLinkBar      = rightNode == nil ? 0 : 1
   let minLinkWidth      = leftLinkBar + linkSpacing + rightLinkBar
   let 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                                                                                                                                 
   let minSpacing        = 2
   let rightNodePosition = zip(leftLineWidths,rightLineIndents[0..<commonLines])
                           .reduce(firstLeftWidth + minLinkWidth)
                           { max($0, $1.0 + minSpacing + firstRightIndent - $1.1) }


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

   // build value line taking into account left indent and link bar extension (on left side)
   let valueIndent       = max(0, firstLeftWidth + leftLinkExtra + leftLinkBar - valueOffset)
   let valueLine         = String(repeating:" ", count:max(0,valueIndent)) 
                         + stringValue
   let slash             = reversed ? "\\" : "/"
   let backSlash         = reversed ? "/"  : "\\"
   let uLine             = reversed ? "¯"  : "_"
   // build left side of link line
   let leftLink          = leftNode == nil ? "" 
                         : String(repeating: " ", count:firstLeftWidth)
                         + String(repeating: uLine, count:leftLinkExtra)
                         + slash

   // build right side of link line (includes blank spaces under top node value) 
   let rightLinkOffset   = linkSpacing + valueOffset * (1 - leftLinkBar)                      
   let rightLink         = rightNode == nil ? ""
                         : String(repeating:  " ", count:rightLinkOffset)
                         + backSlash 
                         + String(repeating:  uLine, count:rightLinkExtra)

   // full link line (will be empty if there are no sub nodes)                                                                                                    
   let 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                                                
   let leftIndentWidth   = max(0,firstRightIndent - rightNodePosition) 
   let leftIndent        = String(repeating:" ", count:leftIndentWidth)
   let indentedLeftLines = leftSubLines.map{ $0.isEmpty ? $0 : (leftIndent + $0) }

   // 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
   let mergeOffsets      = indentedLeftLines
                           .map{$0.count}
                           .map{leftIndentWidth + rightNodePosition - firstRightIndent - $0 }
                           .enumerated()
                           .map{ rightSubLines[$0].isEmpty ? 0  : $1 }


   // 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.
   let mergedSubLines    = zip(mergeOffsets.enumerated(),indentedLeftLines)
                           .map{ ( $0.0, $0.1, $1 + String(repeating:" ", count:max(0,$0.1)) ) }
                           .map{ $2 + String(rightSubLines[$0].dropFirst(max(0,-$1))) }

   // Assemble final result combining
   //  * node value string
   //  * link line (if any)
   //  * merged lines from left and right sub trees (if any)
   let treeLines = [leftIndent + valueLine]
                 + (linkLine.isEmpty ? [] : [leftIndent + linkLine])
                 + mergedSubLines

   return (reversed && isTop ? treeLines.reversed(): treeLines)
          .joined(separator:"\n")                                        
}

要实际打印，您需要向函数提供您的类节点和一个闭包来访问节点描述以及左右子节点。

extension TreeNode
{       
   var asString:String { return treeString(self){("\($0.value)",$0.left,$0.right)}  }       
}

var root = TreeNode(7)

root.addValue(9)
root.addValue(5)
root.addValue(6)
root.addValue(1)

print(root.asString)

//     7
//    / \
//   5   9
//  / \
// 1   6
//

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)

print(root.asString)

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

[编辑] 改进了逻辑，以在右侧比左侧更深的树上使用更少的空间。清理了代码并添加了注释以解释其工作原理。

//
//       12
//      /  \
//    10    50
//   /   __/  \__
//  5  30        90
//       \      /
//        35  70
//           /  \
//         60    85
//        /
//      55
//

//                12
//               /  \
//             10    30
//            /        \
//           5          90
//                     /
//                   85
//                  /
//                70
//               /
//             55
//            /
//          48
//         /
//       45
//      /
//    40
//   /
// 35
//

< p > [EDIT2] 将函数设为通用型并改进了解释。

< p > 有了这个通用函数，数据甚至不需要以实际的树结构表示。

< p > 例如，您可以打印包含堆树的数组：

 extension Array
 {    
    func printHeapTree(reversed:Bool = false)
    {
       let tree = treeString( 0, reversed:reversed )
       {
          let left  = { $0 < self.count ? $0 : nil}($0 * 2 + 1)
          let right = { $0 < self.count ? $0 : nil}($0 * 2 + 2)
          return ( "\(self[$0])", left, right )
       }
       print(tree) 
    }
 }

let values = [7,5,9,1,6]
values.printHeapTree()

//     7
//    / \
//   5   9
//  / \
// 1   6

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

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

但是对于最后一个例子，家谱通常是倒过来呈现的。因此，我调整了函数以允许打印反转的家谱：

family.printHeapTree(reversed:true)

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

< p >【编辑3】根据Emm的要求，在示例类（TreeNode）中添加了排除重复条目的条件。

【编辑4】更改了mergedSubLines公式，以便在实际项目中可以编译（此前是在游乐场中测试）。

【编辑5】对Swift4进行了微调，添加了打印反向树的能力，并将数组示例更改为堆树。