/**
* Beispiel aus
*
* - Algorithmen und Datenstrukturen für Dummies
* - von Andreas Gogol-Döring und Thomas Letschert
* - Verlag Wiley-VCH; Oktober 2019
* - Kapitel 5, Bäume: Immer einer über den anderen
*
* @author A. Gogol-Döring, Th. Letschert
*/
import Foundation
struct AuD_05_03_InorderTraversal {
enum BinTree : CustomStringConvertible {
case Empty
indirect case Node(value: A,
left: BinTree,
right: BinTree
)
var description : String {
switch self {
case .Empty: return "."
case .Node(let v, let l, let r): return "[\(v), \(l.description), \(r.description) ]"
}
}
}
static func inorder(tree: BinTree) -> [A] {
switch tree {
case .Empty :
return []
case .Node(let v, let l, let r) :
return inorder(tree: l) + ([v] + inorder(tree: r))
}
}
static func run() {
let tree: BinTree =
.Node(value: 1,
left: .Node(value: 2,
left: .Empty, right: .Empty),
right: .Node(value: 3,
left: .Node(value: 4, left: .Empty, right: .Empty),
right: .Node(value: 5,
left: .Node(value: 6, left: .Empty, right: .Node(value: 7, left: .Empty, right: .Empty)),
right: .Node(value: 8, left: .Empty, right: .Node(value: 9, left: .Empty, right: .Empty)))
)
)
print(inorder(tree: tree))
}
}