Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
BinaryTree.playground
Images
README.markdown
README_en.markdown

README.markdown

二叉树(Binary Tree)

二叉树是一种,其中每个节点具有0,1或2个子节点。 这是一个二叉树:

一个二叉树

子节点通常称为 子节点 和 子节点。 如果节点没有任何子节点,则称为 叶子节点。 是树顶部的节点(程序员习惯树颠倒了😀)。

节点通常会有一个返回其父节点的连接,但这不是绝对必要的。

二叉树通常用作二叉搜索树。 在这种情况下,节点必须按特定顺序排列(左侧是较小的值,右侧是较大的值)。 但这不是所有二叉树的要求。

例如,这是一个二叉树,表示一系列算术运算,(5 * (a - 10)) + (-4 * (3 / b))

一个二叉树

代码

以下是在Swift中实现通用二叉树的方法:

public indirect enum BinaryTree<T> {
  case node(BinaryTree<T>, T, BinaryTree<T>)
  case empty
}

如何使用它的一个例子,让我们构建上面算术运算树:

// 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)

您需要反向构建树,从叶子节点开始,一直到顶部。

添加description属性以便打印树,这会很有用的:

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

如果你 print(tree) 你应该看到这样的东西:

value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]

通过一点想象力,您可以看到树形结构。 ;-)如果你缩进它会清晰的看到:

value: +, 
	left = [value: *, 
		left = [value: 5, left = [], right = []], 
		right = [value: -, 
			left = [value: a, left = [], right = []], 
			right = [value: 10, left = [], right = []]]], 
	right = [value: *, 
		left = [value: -, 
			left = [], 
			right = [value: 4, left = [], right = []]], 
		right = [value: /, 
			left = [value: 3, left = [], right = []], 
			right = [value: b, left = [], right = []]]]

另一个有用的属性是计算树中的节点数:

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

对于示例的树,tree.count应该是12。

您经常需要对树进行的操作遍历它们,即以某种顺序查看所有节点。 遍历二叉树有三种方法:

  1. In-order(或深度优先): 首先查看节点的左子节点,然后查看节点本身,最后查看其右子节点。
  2. Pre-order: 首先查看节点,然后查看其左右子节点。
  3. Post-order: 首先查看左右子节点最后处理节点本身。

以下是您实现的方法:

  public func traverseInOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      left.traverseInOrder(process: process)
      process(value)
      right.traverseInOrder(process: process)
    }
  }
  
  public func traversePreOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      process(value)
      left.traversePreOrder(process: process)
      right.traversePreOrder(process: process)
    }
  }
  
  public func traversePostOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      left.traversePostOrder(process: process)
      right.traversePostOrder(process: process)
      process(value)
    }
  }

这些函数会被递归调用,在使用树结构时很常见。

例如,如果您按 Post-order 遍历算术运算树,您将按以下顺序查看值:

5
a
10
-
*
4
-
3
b
/
*
+

叶子节点首先出现。 根节点最后出现。

您可以使用堆栈计算机来评估这些表达式,类似于以下伪代码:

tree.traversePostOrder { s in 
  switch s {
  case this is a numeric literal, such as 5:
    push it onto the stack
  case this is a variable name, such as a:
    look up the value of a and push it onto the stack
  case this is an operator, such as *:
    pop the two top-most items off the stack, multiply them,
    and push the result back onto the stack
  }
  the result is in the top-most item on the stack
}

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

You can’t perform that action at this time.