如何在Swift4中画二叉树？

Question

基于 this 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([=11=]) }
tree.search(searchValue: 5)

我在堆栈上找到了很多示例来可视化 Android 中的这样一棵树 Graphical binary tree in Android or PHP draw binary tree with php 但 Swift 中没有任何内容。我想到了 Core Graphics 库，但从哪里开始呢？谁能给我举个例子吗？

Answer 1

关于如何画线的基础知识，您：

创建UIBezierPath;
移动到起点 move(to:);
用 addLine(to:);

然后您可以通过以下任一方式在 UI 中呈现该路径：

创建 CAShapeLayer，指定其 strokeWidth、strokeColor 和 fillColor；设置其 path，然后将该形状层添加为视图 layer 的子层；或
创建UIView子类，在它的draw(_:)方法中你可以调用setStroke所需的UIColor，设置[=14的lineWidth =]，然后 stroke() UIBezierPath。

通常，我会使用 CAShapeLayer 方法，我基本上配置形状层，但让 OS 为我渲染那个形状层。

话虽如此，我可能会更进一步，将线条图包装在它自己的 UIView 子类中。思考过程是，不仅高级视图通常由 UIView 个对象组成，而且它还为各种高级用户体验打开了大门（例如，您可能想要检测节点上的点击并做一些事情） .

无论如何，我会将“连接线”绘图代码包装在 UIView 子类中，如下所示：

class ConnectorView: UIView {
    enum ConnectorType {
        case upperRightToLowerLeft
        case upperLeftToLowerRight
        case vertical
    }

    var connectorType: ConnectorType = .upperLeftToLowerRight { didSet { layoutIfNeeded() } }

    override class var layerClass: AnyClass { return CAShapeLayer.self }
    var shapeLayer: CAShapeLayer { return layer as! CAShapeLayer }

    convenience init(connectorType: ConnectorType) {
        self.init()
        self.connectorType = connectorType
    }

    override init(frame: CGRect = .zero) {
        super.init(frame: frame)
        configure()
    }

    required init?(coder aDecoder: NSCoder) {
        super.init(coder: aDecoder)
        configure()
    }

    override func layoutSubviews() {
        let path = UIBezierPath()

        switch connectorType {
        case .upperLeftToLowerRight:
            path.move(to: CGPoint(x: bounds.minX, y: bounds.minY))
            path.addLine(to: CGPoint(x: bounds.maxX, y: bounds.maxY))

        case .upperRightToLowerLeft:
            path.move(to: CGPoint(x: bounds.maxX, y: bounds.minY))
            path.addLine(to: CGPoint(x: bounds.minX, y: bounds.maxY))

        case .vertical:
            path.move(to: CGPoint(x: bounds.midX, y: bounds.minY))
            path.addLine(to: CGPoint(x: bounds.midX, y: bounds.maxY))
        }

        shapeLayer.path = path.cgPath
    }

    override var description: String { return String(format: "<ConnectorView: %p; frame = %@, type = %@", self, frame.debugDescription, connectorType.string) }
}

private extension ConnectorView {
    func configure() {
        shapeLayer.lineWidth = 3
        shapeLayer.strokeColor = UIColor.black.cgColor
        shapeLayer.fillColor = UIColor.clear.cgColor
    }
}

这定义了形状图层以从一个角描边到另一个角，它会随着此视图的 frame 变化而自动更新。通过这样做，我现在可以通过更新此 UIView 子类的 frame 来控制连接线视图的呈现位置。这种方法的优点是我现在可以为这个 ConnectorView 定义约束，这样 top/bottom/left/right 锚点绑定到 [=23= 的 centerX 和 centerY ] 为各自的节点。通过将节点放在这些连接线视图的前面，它会产生所需的外观。

仅供参考，对于简单的矩形节点，您可能只是将 UILabel 子类化为节点本身：

class NodeView: UILabel {
    weak var containerView: UIView!

    override init(frame: CGRect = .zero) {
        super.init(frame: frame)
        configure()
    }

    required init?(coder aDecoder: NSCoder) {
        super.init(coder: aDecoder)
        configure()
    }
}

private extension NodeView {
    func configure() {
        backgroundColor = UIColor.white
        layer.borderColor = UIColor.black.cgColor
        layer.borderWidth = 3
        textAlignment = .center
    }
}

现在，诀窍在于放置节点的位置，以便 space 有足够的空间容纳它们的所有子节点。如果你是 iOS 约束系统的新手，这看起来会非常混乱（坦率地说，即使你熟悉它，它也有点难看），但你可以这样做：

private let nodeSpacing: CGFloat = 50
private let nodeVerticalSpace: CGFloat = 50
private let nodeHorizontalSpace: CGFloat = 50
private let nodeHeight: CGFloat = 40
private let nodeWidth: CGFloat = 60

extension BinaryTree {

    func addNodes(to view: UIView) -> NodeView? {
        guard case .node(let leftNode, let value, let rightNode) = self else { return nil }

        let containerView = UIView()
        containerView.translatesAutoresizingMaskIntoConstraints = false
        view.addSubview(containerView)

        let thisNodeView = NodeView()
        thisNodeView.translatesAutoresizingMaskIntoConstraints = false
        thisNodeView.text = String(describing: value)
        thisNodeView.containerView = containerView
        containerView.addSubview(thisNodeView)

        NSLayoutConstraint.activate([
            containerView.topAnchor.constraint(equalTo: thisNodeView.topAnchor),

            thisNodeView.widthAnchor.constraint(equalToConstant: nodeWidth),
            thisNodeView.heightAnchor.constraint(equalToConstant: nodeHeight),
        ])

        switch (leftNode, rightNode) {
        case (.empty, .empty):
            NSLayoutConstraint.activate([
                containerView.bottomAnchor.constraint(equalTo: thisNodeView.bottomAnchor),
                containerView.leftAnchor.constraint(equalTo: thisNodeView.leftAnchor),
                containerView.rightAnchor.constraint(equalTo: thisNodeView.rightAnchor)
            ])

        case (let node, .empty), (.empty, let node):
            let nodeView = node.addNodes(to: containerView)!
            let connector = ConnectorView(connectorType: .vertical)
            connector.translatesAutoresizingMaskIntoConstraints = false
            containerView.insertSubview(connector, belowSubview: thisNodeView)

            NSLayoutConstraint.activate([
                thisNodeView.bottomAnchor.constraint(equalTo: nodeView.topAnchor, constant: -nodeVerticalSpace),
                thisNodeView.centerXAnchor.constraint(equalTo: nodeView.centerXAnchor),
                connector.topAnchor.constraint(equalTo: thisNodeView.centerYAnchor),
                connector.bottomAnchor.constraint(equalTo: nodeView.centerYAnchor),
                connector.leadingAnchor.constraint(equalTo: thisNodeView.leadingAnchor),
                connector.trailingAnchor.constraint(equalTo: thisNodeView.trailingAnchor),

                containerView.bottomAnchor.constraint(equalTo: nodeView.containerView.bottomAnchor),
                containerView.leftAnchor.constraint(equalTo: nodeView.containerView.leftAnchor),
                containerView.rightAnchor.constraint(equalTo: nodeView.containerView.rightAnchor)
            ])

        case (let leftNode, let rightNode):
            let leftNodeView = leftNode.addNodes(to: containerView)!
            let rightNodeView = rightNode.addNodes(to: containerView)!

            let leftConnector = ConnectorView(connectorType: .upperRightToLowerLeft)
            leftConnector.translatesAutoresizingMaskIntoConstraints = false
            containerView.insertSubview(leftConnector, belowSubview: thisNodeView)

            let rightConnector = ConnectorView(connectorType: .upperLeftToLowerRight)
            rightConnector.translatesAutoresizingMaskIntoConstraints = false
            containerView.insertSubview(rightConnector, belowSubview: thisNodeView)

            for nodeView in [leftNodeView, rightNodeView] {
                NSLayoutConstraint.activate([
                    thisNodeView.bottomAnchor.constraint(equalTo: nodeView.topAnchor, constant: -nodeVerticalSpace),
                ])
            }
            NSLayoutConstraint.activate([
                leftNodeView.containerView.rightAnchor.constraint(lessThanOrEqualTo: rightNodeView.containerView.leftAnchor, constant: -nodeHorizontalSpace),

                leftConnector.topAnchor.constraint(equalTo: thisNodeView.centerYAnchor),
                leftConnector.bottomAnchor.constraint(equalTo: leftNodeView.centerYAnchor),
                leftConnector.leadingAnchor.constraint(equalTo: leftNodeView.centerXAnchor),
                leftConnector.trailingAnchor.constraint(equalTo: thisNodeView.centerXAnchor),

                rightConnector.topAnchor.constraint(equalTo: thisNodeView.centerYAnchor),
                rightConnector.bottomAnchor.constraint(equalTo: rightNodeView.centerYAnchor),
                rightConnector.leadingAnchor.constraint(equalTo: thisNodeView.centerXAnchor),
                rightConnector.trailingAnchor.constraint(equalTo: rightNodeView.centerXAnchor),

                leftConnector.widthAnchor.constraint(equalTo: rightConnector.widthAnchor),

                containerView.bottomAnchor.constraint(greaterThanOrEqualTo: leftNodeView.containerView.bottomAnchor),
                containerView.bottomAnchor.constraint(greaterThanOrEqualTo: rightNodeView.containerView.bottomAnchor),
                containerView.leftAnchor.constraint(equalTo: leftNodeView.containerView.leftAnchor),
                containerView.rightAnchor.constraint(equalTo: rightNodeView.containerView.rightAnchor)
            ])
        }

        return thisNodeView
    }
}

这可能看起来很丑陋，但我认为这比编写自己的基于规则的节点定位引擎要好。但是这些约束捕获的规则有几个基本的“规则”：

每个节点都有特定的固定大小。
每个节点到下一层都有一定的距离
当一个节点有子节点时，将节点居中放置在两个子节点和space子节点之上一定的固定距离。
当间隔对等节点时，将整个二叉树包裹在容器视图中的给定节点下方，并将其用于间隔。因此，查看其中一个较低的节点，即二叉树左侧的 -，其子节点的容器视图如下：

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

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

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

override func viewDidLoad() {
    super.viewDidLoad()

    // 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
    let tree = BinaryTree.node(timesLeft, "+", timesRight)

    let nodeView = tree.addNodes(to: view)!
    NSLayoutConstraint.activate([
        nodeView.containerView.centerXAnchor.constraint(equalTo: view.centerXAnchor),
        nodeView.containerView.centerYAnchor.constraint(equalTo: view.centerYAnchor)
    ])
}

产量：

Answer 2

很简单，创建 html 页面，根据这个 link 绘制树： http://fperucic.github.io/treant-js/

将生成的HTML字符串加载到UIWebView

如果您也在编写 Android 程序，则可以使用相同的技巧。

你也可以通过Swift处理UIWebView内部的事件：

如何在Swift4中画二叉树？

How to draw a binary tree in Swift 4?

binary-tree

core-graphics

swift