如何在控制台中“画”二叉树？ [英] How to “draw” a Binary Tree in Console?
本文介绍了如何在控制台中“画”二叉树？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
如何在SWIFT中打印二叉树，以便输入79561打印输出如下：
7
/
5 9
/
1 6
我尝试使用For Loops和If Statements用一些代码来安排，但没有成功。
我的代码是：
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 Loops，一个用于高度，另一个用于宽度。但是如果节点数改变了，它就不工作了。现在我只是尝试排列links(/和)、nodes和空格的位置，所以不起作用。
是否有可能执行此操作？
推荐答案
首先，您必须定义允许递归遍历树节点的分层树结构(类)。您如何实现它并不重要，只要它能提供描述性字符串并访问其左子节点和右子节点即可。
例如(我将其用于测试目的)：
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:"
")
let rightTextBlock = rightNode == nil ? []
: treeString(rightNode!,reversed:reversed,isTop:false,using:nodeInfo)
.components(separatedBy:"
")
// 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:"
")
}
若要实际打印，您需要为函数提供类的节点和闭包以访问节点描述以及左子节点和右子节点。
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
//
[EDIT2]对该函数进行了泛型和改编说明。
使用泛型函数，数据甚至不需要位于实际的树结构中。
例如，您可以打印包含堆树的数组：
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
[EDIT3]根据EMM的请求添加了从示例类(TreeNode)的树中排除重复条目的条件
[EDIT4]已更改mergedSubLines的公式，以便它可以在实际项目中编译(在操场上进行测试)。
[EDIT5]对Swift4进行了细微调整，添加了打印反转树的功能，将数组示例更改为堆树。
这篇关于如何在控制台中“画”二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
