如何在 Swift 4 中绘制二叉树？

Question

根据Ray Wenderlich 的这篇文章，我能够创建一个如下的二叉树数据结构：

  enum BinaryTree<T: Comparable> {

  case empty
  indirect case node(BinaryTree<T>, T, BinaryTree<T>)

  var count: Int {
    switch self {
    case let .node(left, _, right):
      return left.count + 1 + right.count
    case .empty:
      return 0
    }
  }

  // 1.
  mutating func naiveInsert(newValue: T) {
    // 2.
    guard case .node(var left, let value, var right) = self else {
      // 3. 
      self = .node(.empty, newValue, .empty)
      return 
    }

    // 4. TODO: Implement naive algorithm!
    if newValue < value {
      left.naiveInsert(newValue: newValue)
    } else {
      right.naiveInsert(newValue: newValue)
    }

  }

  private func newTreeWithInsertedValue(newValue: T) -> BinaryTree {
    switch self {
    // 1
    case .empty:
      return .node(.empty, newValue, .empty)
    // 2 
    case let .node(left, value, right):
      if newValue < value {
        return .node(left.newTreeWithInsertedValue(newValue: newValue), value, right)
      } else {
        return .node(left, value, right.newTreeWithInsertedValue(newValue: newValue))
      }
    }
  }

  mutating func insert(newValue: T) {
    self = newTreeWithInsertedValue(newValue: newValue)
  }

    func traverseInOrder(process: (T) -> ()) {
    switch self {
    // 1
    case .empty:
      return 
    // 2
    case let .node(left, value, right):
      left.traverseInOrder(process: process)
      process(value)
      right.traverseInOrder(process: process)
    }
  }

    func traversePreOrder( process: (T) -> ()) {
    switch self {
    case .empty:
      return
    case let .node(left, value, right):
      process(value)
      left.traversePreOrder(process: process)
      right.traversePreOrder(process: process)
    }
  }

    func traversePostOrder( process: (T) -> ()) {
    switch self {
    case .empty:
      return
    case let .node(left, value, right):
      left.traversePostOrder(process: process)
      right.traversePostOrder(process: process)
      process(value) 
    }
  }

  func search(searchValue: T) -> BinaryTree? {
    switch self {
    case .empty:
      return nil
    case let .node(left, value, right):
      // 1
      if searchValue == value {
        return self
      }

      // 2
      if searchValue < value {
        return left.search(searchValue: searchValue)
      } else {
        return right.search(searchValue: searchValue)
      }
    }
  }

}

extension BinaryTree: CustomStringConvertible {
  var description: String {
    switch self {
    case let .node(left, value, right):
      return "value: \(value), left = [" + left.description + "], right = [" + right.description + "]"
    case .empty:
      return ""
    }
  }
}

// leaf nodes
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)

// intermediate nodes on the left
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", Aminus10)

// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// root node
var tree: BinaryTree<Int> = .empty
tree.insert(newValue: 7)
tree.insert(newValue: 10)
tree.insert(newValue: 2)
tree.insert(newValue: 1)
tree.insert(newValue: 5)
tree.insert(newValue: 9)
tree.insert(newValue: 3)

tree.traverseInOrder { print($0) }
tree.search(searchValue: 5)

我在堆栈上找到了很多示例，可以在 Android 中可视化这样的树。 Android 中的图形二叉树或 PHP使用 php 绘制二叉树，但在 Swift 中却没有。我考虑过 Core Graphics 库，但从哪里开始呢？谁能给我举个例子吗？

Answer 1

In terms of the basics of how to draw a line, you:

\n\n

\n
1. Create UIBezierPath;
\n
2. Move to the starting point with move(to:);
\n
3. Adding line to the end point with addLine(to:);
\n

\n\n

You can then render that path in your UI by either:

\n\n

\n
• Create CAShapeLayer, specifying its strokeWidth, strokeColor, and fillColor; set its path, and then add that shape layer as a sublayer of the view\xe2\x80\x99s layer; or
\n
• Create UIView subclass and in its draw(_:) method you can call setStroke of the desired UIColor, set the lineWidth of the UIBezierPath, and then stroke() the UIBezierPath.
\n

\n\n

Generally, I\xe2\x80\x99d use the CAShapeLayer approach, where I basically configure the shape layer, but let the OS render that shape layer for me.

\n\n\n\n

That having been said, I\xe2\x80\x99d probably take this a step further, and wrap the line drawing in its own UIView subclass. The thought process is that not only are high-level views generally composed of UIView objects, but it also opens the door for all sorts of advanced UX (e.g. you might want to detect a tap on a node and do something).

\n\n

Anyway, I\xe2\x80\x99d wrap that \xe2\x80\x9cconnector line\xe2\x80\x9d drawing code in a UIView subclass, like so:

\n\n

class ConnectorView: UIView {\n    enum ConnectorType {\n        case upperRightToLowerLeft\n        case upperLeftToLowerRight\n        case vertical\n    }\n\n    var connectorType: ConnectorType = .upperLeftToLowerRight { didSet { layoutIfNeeded() } }\n\n    override class var layerClass: AnyClass { return CAShapeLayer.self }\n    var shapeLayer: CAShapeLayer { return layer as! CAShapeLayer }\n\n    convenience init(connectorType: ConnectorType) {\n        self.init()\n        self.connectorType = connectorType\n    }\n\n    override init(frame: CGRect = .zero) {\n        super.init(frame: frame)\n        configure()\n    }\n\n    required init?(coder aDecoder: NSCoder) {\n        super.init(coder: aDecoder)\n        configure()\n    }\n\n    override func layoutSubviews() {\n        let path = UIBezierPath()\n\n        switch connectorType {\n        case .upperLeftToLowerRight:\n            path.move(to: CGPoint(x: bounds.minX, y: bounds.minY))\n            path.addLine(to: CGPoint(x: bounds.maxX, y: bounds.maxY))\n\n        case .upperRightToLowerLeft:\n            path.move(to: CGPoint(x: bounds.maxX, y: bounds.minY))\n            path.addLine(to: CGPoint(x: bounds.minX, y: bounds.maxY))\n\n        case .vertical:\n            path.move(to: CGPoint(x: bounds.midX, y: bounds.minY))\n            path.addLine(to: CGPoint(x: bounds.midX, y: bounds.maxY))\n        }\n\n        shapeLayer.path = path.cgPath\n    }\n\n    override var description: String { return String(format: "<ConnectorView: %p; frame = %@, type = %@", self, frame.debugDescription, connectorType.string) }\n}\n\nprivate extension ConnectorView {\n    func configure() {\n        shapeLayer.lineWidth = 3\n        shapeLayer.strokeColor = UIColor.black.cgColor\n        shapeLayer.fillColor = UIColor.clear.cgColor\n    }\n}\n

\n\n

This defines the shape layer to stroke the line from one corner to another, which it will automatically update accordingly as the frame of this view changes. By doing this, I can now control where the connector line view is rendered by updating a frame of this UIView subclass. The virtue of this approach is that I can now define the constraints for this ConnectorView such that the top/bottom/left/right anchors are tied to the centerX and centerY of the UIView for the respective nodes. And by putting the nodes in front of these connector line views, it results in the desired look and feel.

\n\n

FYI, for simple rectangular nodes, you might just subclassed UILabel for the nodes, themselves:

\n\n

class NodeView: UILabel {\n    weak var containerView: UIView!\n\n    override init(frame: CGRect = .zero) {\n        super.init(frame: frame)\n        configure()\n    }\n\n    required init?(coder aDecoder: NSCoder) {\n        super.init(coder: aDecoder)\n        configure()\n    }\n}\n\nprivate extension NodeView {\n    func configure() {\n        backgroundColor = UIColor.white\n        layer.borderColor = UIColor.black.cgColor\n        layer.borderWidth = 3\n        textAlignment = .center\n    }\n}\n

\n\n

Now, the trick is where to place the nodes so that there\xe2\x80\x99s enough space for all their child nodes. If you\xe2\x80\x99re new to the iOS constraints system this is going to look super confusing (frankly, even if you are familiar with it, it\xe2\x80\x99s a bit ugly), but you can do something like:

\n\n

private let nodeSpacing: CGFloat = 50\nprivate let nodeVerticalSpace: CGFloat = 50\nprivate let nodeHorizontalSpace: CGFloat = 50\nprivate let nodeHeight: CGFloat = 40\nprivate let nodeWidth: CGFloat = 60\n\nextension BinaryTree {\n\n    func addNodes(to view: UIView) -> NodeView? {\n        guard case .node(let leftNode, let value, let rightNode) = self else { return nil }\n\n        let containerView = UIView()\n        containerView.translatesAutoresizingMaskIntoConstraints = false\n        view.addSubview(containerView)\n\n        let thisNodeView = NodeView()\n        thisNodeView.translatesAutoresizingMaskIntoConstraints = false\n        thisNodeView.text = String(describing: value)\n        thisNodeView.containerView = containerView\n        containerView.addSubview(thisNodeView)\n\n        NSLayoutConstraint.activate([\n            containerView.topAnchor.constraint(equalTo: thisNodeView.topAnchor),\n\n            thisNodeView.widthAnchor.constraint(equalToConstant: nodeWidth),\n            thisNodeView.heightAnchor.constraint(equalToConstant: nodeHeight),\n        ])\n\n        switch (leftNode, rightNode) {\n        case (.empty, .empty):\n            NSLayoutConstraint.activate([\n                containerView.bottomAnchor.constraint(equalTo: thisNodeView.bottomAnchor),\n                containerView.leftAnchor.constraint(equalTo: thisNodeView.leftAnchor),\n                containerView.rightAnchor.constraint(equalTo: thisNodeView.rightAnchor)\n            ])\n\n        case (let node, .empty), (.empty, let node):\n            let nodeView = node.addNodes(to: containerView)!\n            let connector = ConnectorView(connectorType: .vertical)\n            connector.translatesAutoresizingMaskIntoConstraints = false\n            containerView.insertSubview(connector, belowSubview: thisNodeView)\n\n            NSLayoutConstraint.activate([\n                thisNodeView.bottomAnchor.constraint(equalTo: nodeView.topAnchor, constant: -nodeVerticalSpace),\n                thisNodeView.centerXAnchor.constraint(equalTo: nodeView.centerXAnchor),\n                connector.topAnchor.constraint(equalTo: thisNodeView.centerYAnchor),\n                connector.bottomAnchor.constraint(equalTo: nodeView.centerYAnchor),\n                connector.leadingAnchor.constraint(equalTo: thisNodeView.leadingAnchor),\n                connector.trailingAnchor.constraint(equalTo: thisNodeView.trailingAnchor),\n\n                containerView.bottomAnchor.constraint(equalTo: nodeView.containerView.bottomAnchor),\n                containerView.leftAnchor.constraint(equalTo: nodeView.containerView.leftAnchor),\n                containerView.rightAnchor.constraint(equalTo: nodeView.containerView.rightAnchor)\n            ])\n\n        case (let leftNode, let rightNode):\n            let leftNodeView = leftNode.addNodes(to: containerView)!\n            let rightNodeView = rightNode.addNodes(to: containerView)!\n\n            let leftConnector = ConnectorView(connectorType: .upperRightToLowerLeft)\n            leftConnector.translatesAutoresizingMaskIntoConstraints = false\n            containerView.insertSubview(leftConnector, belowSubview: thisNodeView)\n\n            let rightConnector = ConnectorView(connectorType: .upperLeftToLowerRight)\n            rightConnector.translatesAutoresizingMaskIntoConstraints = false\n            containerView.insertSubview(rightConnector, belowSubview: thisNodeView)\n\n            for nodeView in [leftNodeView, rightNodeView] {\n                NSLayoutConstraint.activate([\n                    thisNodeView.bottomAnchor.constraint(equalTo: nodeView.topAnchor, constant: -nodeVerticalSpace),\n                ])\n            }\n            NSLayoutConstraint.activate([\n                leftNodeView.containerView.rightAnchor.constraint(lessThanOrEqualTo: rightNodeView.containerView.leftAnchor, constant: -nodeHorizontalSpace),\n\n                leftConnector.topAnchor.constraint(equalTo: thisNodeView.centerYAnchor),\n                leftConnector.bottomAnchor.constraint(equalTo: leftNodeView.centerYAnchor),\n                leftConnector.leadingAnchor.constraint(equalTo: leftNodeView.centerXAnchor),\n                leftConnector.trailingAnchor.constraint(equalTo: thisNodeView.centerXAnchor),\n\n                rightConnector.topAnchor.constraint(equalTo: thisNodeView.centerYAnchor),\n                rightConnector.bottomAnchor.constraint(equalTo: rightNodeView.centerYAnchor),\n                rightConnector.leadingAnchor.constraint(equalTo: thisNodeView.centerXAnchor),\n                rightConnector.trailingAnchor.constraint(equalTo: rightNodeView.centerXAnchor),\n\n                leftConnector.widthAnchor.constraint(equalTo: rightConnector.widthAnchor),\n\n                containerView.bottomAnchor.constraint(greaterThanOrEqualTo: leftNodeView.containerView.bottomAnchor),\n                containerView.bottomAnchor.constraint(greaterThanOrEqualTo: rightNodeView.containerView.bottomAnchor),\n                containerView.leftAnchor.constraint(equalTo: leftNodeView.containerView.leftAnchor),\n                containerView.rightAnchor.constraint(equalTo: rightNodeView.containerView.rightAnchor)\n            ])\n        }\n\n        return thisNodeView\n    }\n}\n

\n\n

这可能看起来很难看，但我认为它比编写自己的基于规则的节点定位引擎更好。但这些约束捕获了一些基本的\xe2\x80\x9crules\xe2\x80\x9d 的规则：

\n\n

\n

1. 每个节点都有特定的固定大小。

\n

2. 每个节点到下面的级别都有一定的距离。

\n

3. 当一个节点有子节点时，将该节点置于两个子节点上方的中心，并将子节点间隔一定的固定距离。

\n

4. 当间隔对等节点时，将整个二叉树包装在容器视图中给定节点的下方，并使用它来间隔。因此，查看二叉树左侧的较低节点之一-，其子节点的容器视图如下：

   \n\n

   

   \n\n

   当查看上面的节点时，它的容器不仅包含两个直接子节点，还包含它们的容器：

   \n\n

   

   \n\n

   最终效果是一棵二叉树，其中所有子节点都有合理的间距，但父节点仍然以其两个直接子节点为中心。

\n

\n\n

无论如何，视图控制器可以像这样调用上面的内容：

\n\n

override func viewDidLoad() {\n    super.viewDidLoad()\n\n    // leaf nodes\n    let node5 = BinaryTree.node(.empty, "5", .empty)\n    let nodeA = BinaryTree.node(.empty, "a", .empty)\n    let node10 = BinaryTree.node(.empty, "10", .empty)\n    let node4 = BinaryTree.node(.empty, "4", .empty)\n    let node3 = BinaryTree.node(.empty, "3", .empty)\n    let nodeB = BinaryTree.node(.empty, "b", .empty)\n\n    // intermediate nodes on the left\n    let Aminus10 = BinaryTree.node(nodeA, "-", node10)\n    let timesLeft = BinaryTree.node(node5, "*", Aminus10)\n\n    // intermediate nodes on the right\n    let minus4 = BinaryTree.node(.empty, "-", node4)\n    let divide3andB = BinaryTree.node(node3, "/", nodeB)\n    let timesRight = BinaryTree.node(minus4, "*", divide3andB)\n\n    // root node\n    let tree = BinaryTree.node(timesLeft, "+", timesRight)\n\n    let nodeView = tree.addNodes(to: view)!\n    NSLayoutConstraint.activate([\n        nodeView.containerView.centerXAnchor.constraint(equalTo: view.centerXAnchor),\n        nodeView.containerView.centerYAnchor.constraint(equalTo: view.centerYAnchor)\n    ])\n}\n

\n\n

产量：

\n\n

\n