非递归先序遍历#

previsit(node,visitor) {
	s := [node]
	while Some(node) = s.pop() {
		if node is null { continue }
		visitor.visit(node)
		s.push(node.right)
		s.push(node.left)
	}
}

非递归中序遍历#

invisit(node, visitor) {
	s := []
	cur := node
	while s.not_empty() or cur !== null {
		if cur !== null {
			s.push(cur)
			cur = cur.left
		} else {
			node = s.pop()
			visitor.visit(node)
			cur = node.right
		}
	}
}

层次遍历#

levelorder(node, visitor) {
	q := [node]
	while Some(node) = q.deqeque() {
		if node is null { continue }
			visitor.visit(node)
			q.enqueue(node.left)
			q.enqueue(node.right)
	}
}

遍历序列构造二叉树#

树有两个维度的信息，而序列是一维的

中序序列转（二叉）树#

在正则二叉树的条件下能够转换，等价于中缀表达式的构造语法树问题中缀表达式求值

中序前序#

中序后序#

中序层次#

层次序列的第一个节点是根，可以把中序序列划分成两个子树的中序序列…

线索化#

…