Stacks, linked lists, queues are all linear data structures. Tree data structures have many applications in representing hierarchical relationships (such as directories), managing sorted data, and speeding up data lookup.

Some terms

Like a linked list, a tree uses nodes to represent its elements.

Parent node, child node

Here is a common tree that is accessed from top to bottom (a real life tree in reverse order)

In a tree, every node except the topmost node has an upper node, which is called the parent node. A child node has only one parent.

The root node

As shown in red, the root node is the beginning of the tree and has no parent node.

A leaf node

As shown in red, leaf nodes have no children in the tree.

implementation

Since, like linked lists, their elements are nodes, add the tree node implementation below:

Class TreeNode<T> {var value: T var children: [TreeNode] = [] T) { self.value = value } func add(_ child: TreeNode<T>) { children.append(child) } }Copy the code

Add test code:

    let animal = TreeNode(value: "animal")
    animal.add(TreeNode(value: "cat"))
    animal.add(TreeNode(value: "dog"))
Copy the code

Its tree structure looks like this:

traverse

Depth first

Depth-first is accessing the root node first, then its children, then the children of the children, all the way to the leaf node.

The following is the algorithm implementation:

extension TreeNode {
    
    func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self)
        children.forEach({
            $0.forEachDepthFirst(visit: visit)
        })
    }
}
Copy the code

Helper code for creating a tree:

func createAnimals() -> TreeNode<String> {
    let animal = TreeNode(value: "animal")
    
    let cat = TreeNode(value: "cat")
    let dog = TreeNode(value: "dog")
    
    let black = TreeNode(value: "black")
    let white = TreeNode(value: "white")
    
    let big = TreeNode(value: "big")
    let middle = TreeNode(value: "middle")
    let small = TreeNode(value: "small")
    
    let brutal = TreeNode(value: "brutal")
    let cute = TreeNode(value: "cute")
    
    animal.add(cat)
    animal.add(dog)
    
    cat.add(black)
    cat.add(white)
    
    dog.add(big)
    dog.add(middle)
    dog.add(small)
    
    big.add(brutal)
    big.add(cute)
    
    return animal

Copy the code

Its tree structure looks like this:

Code test:

func depthFirstVisit() {
    let animal = createAnimals()
    animal.forEachDepthFirst(visit: { print($0.value) })
}
Copy the code

Output:

animal
cat
black
white
dog
big
brutal
cute
middle
small
Copy the code

Level priority

Hierarchy priority means that all nodes of the same hierarchy are accessed first.

The following is the algorithm implementation:

extension TreeNode { func forEachLevelOrder(visit: (TreeNode) -> Void) {visit(self) var queue = queue <TreeNode>() }) while let node = queue.dequeue() { visit(node) node.children.forEach({ queue.enqueue($0) }) } } }Copy the code

The key to the implementation of the algorithm is to use queues to save all nodes of the current hierarchy. The implementation of queues is described here, and the implementation code is directly pasted here:

struct Queue<T> {
    
    private var leftStack: [T] = []
    private var rightStack: [T] = []
    
    init() {}
    
    var isEmpty: Bool {
        leftStack.isEmpty && rightStack.isEmpty
    }
    
    var peek: T? {
        !leftStack.isEmpty ? leftStack.last : rightStack.first
    }
    
    var count: Int {
        leftStack.count + rightStack.count
    }
    
    @discardableResult mutating func enqueue(_ element: T) -> Bool {
        rightStack.append(element)
        return true
    }
    
    mutating func dequeue() -> T? {
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        return leftStack.popLast()
    }
}
Copy the code

Code test:

func levelVisit() {
    let animal = createAnimals()
    animal.forEachLevelOrder(visit: { print($0.value) })
}
Copy the code

Output:

animal
cat
dog
black
white
big
middle
small
brutal
cute
Copy the code

To find the

Since the tree has implemented depth-first and hierarchy-first traversal algorithms, finding a node in the tree can also be implemented based on different traversal algorithms.

Implementation:

extension TreeNode where T: Equatable { func search(_ value: T) -> TreeNode? { var result: TreeNode? ForEachLevelOrder {node in if node. Value == value {result = node}} return result}} forEachLevelOrder {node in if node.Copy the code

practice

Output by hierarchy, such as the animal tree above, would look like this:

animal

cat dog

black white big middle small

brutal cute

The first code implementation:

func printInLevelOrder<T>(items: [TreeNode<T>]) { print(items.map({ "\($0.value)" }).joined(separator: " ")) var results: [TreeNode<T>] = [] for i in items { i.children.forEach({ results.append($0) }) } if ! results.isEmpty { printInLevelOrder(items: results) } }Copy the code

Test code:

    let animal = createAnimals()
    printInLevelOrder(items: [animal])
Copy the code

You can see that the output is OK.

The second code implementation:

func printEachLevel<T>(for tree: TreeNode<T>) { var queue = Queue<TreeNode<T>>() var nodesLeftInCurrentLevel = 0 queue.enqueue(tree) while ! queue.isEmpty { nodesLeftInCurrentLevel = queue.count while nodesLeftInCurrentLevel > 0 { guard let node = queue.dequeue() else { break } print("\(node.value) ", terminator: "") node.children.forEach { queue.enqueue($0) } nodesLeftInCurrentLevel -= 1 } print() } }Copy the code

The key to the second implementation is to use queues to hold the number of current levels.