Printing a Tree With Indents. Swift

user_7724881 0
Viewed 2041

Implementing a Tree data structure using swift: 

class Node {

    var value: String
    var children: [Node] = []
    weak var parent: Node?

    init(_ value: String) {
        self.value = value
    }

    func add(_ child: Node){
        children.append(child)
        child.parent = self
    }

    func printTree() {
        var text = self.value
        if !self.children.isEmpty {
            text += "\n  " + self.children.map{$0.printTree()}.joined(separator: ", ")
        }
        print(text)
    }

}

My goal is to see something like this: 

A1
    B2
    C3
        G6
    K0
        H7
            L8
        L9

I know there should be some smart way to insert indents, but I also struggle with 'map'. Compiler gives me "ambiguous reference to member 'map'".

tree swift data-structures
3 Answers

If you want to make it pretty, you could do this:

extension Node
{
   func treeLines(_ nodeIndent:String="", _ childIndent:String="") -> [String]
   {
      return [ nodeIndent + value ]
           + children.enumerated().map{ ($0 < children.count-1, $1) }
             .flatMap{ $0 ? $1.treeLines("┣╸","┃ ") : $1.treeLines("┗╸","  ") }
             .map{ childIndent + $0 } 
   }

   func printTree()
   { print(treeLines().joined(separator:"\n")) }
}

a1.printTree()

// A1
// ┣╸B2
// ┣╸C3
// ┃ ┗╸G6
// ┗╸K0
//   ┣╸H7
//   ┃ ┗╸L8
//   ┗╸L9

You could also generalize it into a print function for any tree structure that will let you choose what to print for each node:

func printTree<T>(_ node:T, _ nodeInfo:@escaping (T)->(String,[T]) ) 
{
  func lines(_ aNode:T, _ nodeIndent:String="", _ childIndent:String="") -> [String]
  {
    let (label,children) = nodeInfo(aNode)
    return [ nodeIndent + label]
         + children.enumerated().map{ ($0 < children.count-1, $1) }
           .flatMap{ $0 ? lines($1,"┣╸","┃ ") :lines($1,"┗╸","  ") }
           .map{ childIndent + $0 }
  }
  print( lines(node).joined(separator:"\n") )
}

// print a root node providing a capture to obtain the node's label
// and its array of children

printTree(a1){ ($0.value,$0.children) }

// works for any tree structure.  for example, views :

printTree(view){( "\(type(of:$0)) \($0.frame)", $0.subviews )}
user_52375600

I think vacawama's answer is quite smart, but if you want to practice recursive call including maps, you can write something like this:

class Node {
    //...

    func treeLines() -> [String] {
        return [self.value] + self.children.flatMap{$0.treeLines()}.map{"    "+$0}
    }
    func printTree() {
        let text = treeLines().joined(separator: "\n")
        print(text)
    }
}

To test:

let a1 = Node("A1")
let b2 = Node("B2")
let c3 = Node("C3")
let g6 = Node("G6")
let k0 = Node("K0")
let h7 = Node("H7")
let l8 = Node("L8")
let l9 = Node("L9")
a1.add(b2)
a1.add(c3)
a1.add(k0)
c3.add(g6)
k0.add(h7)
k0.add(l9)
h7.add(l8)
a1.printTree()

Output:

A1
    B2
    C3
        G6
    K0
        H7
            L8
        L9

Some points:

  • Your printTree() is a void function, so using it in map produces an Array of empty tuples, which cannot be joined.

    (In Swift, void functions can be considered as returning empty tuple. And Swift generates ambiguous reference to member when an appropriate overload cannot be found.)

    You may need an intermediate function the result of which can represent a partial tree structure.

  • Indentation needs to be added to each line, so the intermediate result should easily be separated into lines.

user_65410070

Something like this should work:

func printTree(_ indent: String = "") {

    print(indent + self.value)

    for child in children {
        child.printTree(indent + "    ")
    }
}
user_16306180
Related