树 Tree 基本信息及实现

2021-03-12  本文已影响0人  pro648
TreePreview.png

树(Tree)是一种很重要的数据结构,在软件开发的多方面都有使用:

树的类型有很多,其有不同的形状和大小。这一篇文章将介绍树的基本信息,以及如何实现树。

1. 术语

下面是一些与树相关常见术语。

1.1 节点 Node

链表相似,树也由节点构成。

TreeNode.png

每个节点包含数据和指向子节点的引用。

1.2 父节点 Parent、子节点 Child

Tree 从顶部向下看,和植物中的树很像,只是方向相反。

每个节点向上都有一个节点(最顶部节点除外),上面的节点称为父节点(parent node)。节点的下面,与其直接相连的称为子节点(child node)。在树中,每个child只有一个parent。

TreeParentChild.png

1.3 根节点 Root

树最顶部的节点称为根节点(root),根节点是唯一没有父节点的节点。

TreeRoot.png

1.4 叶子节点 Leaf

如果节点没有子节点,则称为叶子节点(leaf)。

TreeLeaf.png

此外,还有以下常用术语:

2. 实现

Tree 由 node 构成,这里先创建TreeNode类。

创建一个 playground,并在 Sources 中添加TreeNode.swift文件,TreeNode代码如下:

public class TreeNode<T> {
    public var value: T
    public var children: [TreeNode] = []
    
    public init(_ value: T) {
        self.value = value
    }
}

每个 node 存储一个值和一个数组,数组里存储着 children。

TreeNode中添加以下代码:

    /// 向当前节点添加子节点
    /// - Parameter child: 要添加的子节点
    public func add(_ child: TreeNode) {
        children.append(child)
    }

在 playground page 中添加以下代码:

example(of: "creating a tree") {
    let beverages = TreeNode("Beverages")
    
    let hot = TreeNode("Hot")
    let cold = TreeNode("Cold")
    
    beverages.add(hot)
    beverages.add(cold)
}

树可以很方便的用于层次结构问题。上述代码定义了三个节点,并组织成逻辑层次,其对应于以下结构:

TreeHierarchical.png

3. 遍历算法 Traversal Algorithms

线性表(如数组、链表、队列)有明确的开始、结束位置,遍历很简单。

TreeLinearCollections.png

与线性表相比,遍历树会变得复杂些。

TreeTraversal.png

遍历时左侧节点有优先权吗?深度与优先权有关联吗?在实际应用时,应根据要解决的问题决定遍历策略。不同类型树、不同类型问题,有不同遍历方式。

3.1 深度优先

TreeNode.swift底部添加以下方法:

extension TreeNode {
    /// 深度优先遍历
    public func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self)
        children.forEach({
            // 使用递归遍历
            $0.forEachDepthFirst(visit: visit)
        })
    }
}

如果不想使用递归,可以使用实现。

在 playground page 添加以下代码,检验深度优先遍历:

func makeBeverageTree() -> TreeNode<String> {
    let tree = TreeNode("Beverages")
    
    let hot = TreeNode("hot")
    let cold = TreeNode("cold")
    
    let tea = TreeNode("tea")
    let coffee = TreeNode("coffee")
    let chocolate = TreeNode("cocoa")
    
    let blackTea = TreeNode("black")
    let greenTea = TreeNode("green")
    let chaiTea = TreeNode("chai")
    
    let soda = TreeNode("soda")
    let milk = TreeNode("milk")
    
    let gingerAle = TreeNode("ginger ale")
    let bitterLemon = TreeNode("bitter lemon")
    
    tree.add(hot)
    tree.add(cold)
    
    hot.add(tea)
    hot.add(coffee)
    hot.add(chocolate)
    
    cold.add(soda)
    cold.add(milk)
    
    tea.add(blackTea)
    tea.add(greenTea)
    tea.add(chaiTea)
    
    soda.add(gingerAle)
    soda.add(bitterLemon)
    
    return tree
}

上述代码创建的树如下:

TreeDepthFirst.png

添加以下代码:

example(of: "depth-first traversal") {
    let tree = makeBeverageTree()
    tree.forEachDepthFirst(visit: {
        print($0.value)
    })
}

输出如下:

--- Example of: depth-first traversal
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

3.2 层序遍历

层序遍历根据 node depth,先遍历同一层节点。

extension TreeNode {
    /// 层序遍历
    public func forEachLevelOrder(visit: (TreeNode) -> Void) {
        visit(self)
        var queue = Queue<TreeNode>()
        children.forEach({
            queue.enqueue($0)
        })
        
        while let node = queue.dequeue() {
            visit(node)
            node.children.forEach{ queue.enqueue($0)}
        }
    }
}

这里使用队列而非栈确保节点读取顺序。

Queue是队列这篇文章创建的数据结构,你可以在文章底部的源码中获取。

forEachLevelOrder函数按照层序遍历:

TreeLevelOrder.png

使用以下代码进行层序遍历:

example(of: "level-order traversal") {
    let tree = makeBeverageTree()
    tree.forEachDepthFirst(visit: {
        print($0.value)
    })
}

运行后输出如下:

--- Example of: level-order traversal
Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

3.3 搜索

前面已经介绍了深度优先、层序遍历两种遍历方式,想要搜索 tree 是否包含指定元素就变得简单了。

extension TreeNode where T: Equatable {
    public func search(_ value: T) -> TreeNode? {
        var result: TreeNode?
        forEachDepthFirst { (node) in
            if node.value == value {
                result = node
            }
        }
        return result
    }
}

使用以下代码搜索指定值:

example(of: "searching for a node") {
    let tree = makeBeverageTree()
    
    if let searchResult1 = tree.search("ginger ale") {
        print("Found node: \(searchResult1.value)")
    }
    
    if let searchResult2 = tree.search("WKD Blue") {
        print(searchResult2.value)
    } else {
        print("Couldn't find WKD Blue")
    }
}

运行后控制台输出如下:

--- Example of: searching for a node
Found node: ginger ale
Couldn't find WKD Blue

深度优先遍历时,如果有多个匹配值,则会取最后一个。

4. 树算法题

4.1 同一层节点打印到同一行

根据节点所在层,将同一层节点打印到同一行。如下图:

TreePrintInLevel.png

输出应如下所示:

15 
1 17 20 
1 5 0 2 5 7 

使用层序遍历可以解决按照层打印的问题,只需判断出何时换行。如下所示:

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()
  }
}

使用nodesLeftInCurrentLevel记录队列当前元素数量,此时打印队列元素时不打印换行符,直到该层打印结束才换行。

该算法时间复杂度为O(n)。由于初始化了队列作为节点的容器,空间复杂度也是O(n)

4.2 为树添加父节点

树的定义中只包含了子节点,删除、旋转等操作时需要用到父节点,应如何为树添加父节点?

可以按照下面方式为树添加一个父节点属性:

public class TreeNode<T> {
    public weak var parent: TreeNode?
    ...
}

根节点没有父节点,因此这里使用了可选类型。节点对子节点强引用,对父节点需为弱引用,否则会产生循环引用。

总结

树有以下这些要点:

Demo名称:Tree
源码地址:https://github.com/pro648/BasicDemos-iOS/tree/master/Tree

欢迎更多指正:https://github.com/pro648/tips

本文地址:https://github.com/pro648/tips/blob/master/sources/树%20Tree%20基本信息及实现.md

上一篇下一篇

猜你喜欢

热点阅读