这篇文章展示了用ruby使用不同的方法对二叉树进行遍，并且实现了不同遍历方式的iterator，希望对大家有所帮助。
Talk is cheap, show me the code!
1. Pre-order Traversal (前序遍历先访问当前的节点，然后再访问它的孩子节点)
Non-recursive
def pre_order_traversal(root) return [] if root.nil? res = [] stack = [] node = root while node || !stack.empty? while node res << node.val stack << node node = node.left end if (!stack.empty?) node = stack.pop node = node.right end end resend
Recursive
def pre_order_traversal(root) return [] if root.nil? res = [] res << root.val res += pre_order_traversal(root.left) res += pre_order_traversal(root.right)end
Iterator
class BTIterator @@stack = [] def initialize(root) @@stack << root end def has_next? !@@stack.empty? end def next if !has_next? return -(1 << 32) end node = @@stack.pop if node.right @@stack << node.right end if node.left @@stack << node.left end node.val endend
2. In-order Traversal (中序遍历先访问当前节点左边分支，然后访问当前节点，最后访问右边的分支)
Non-recursive
def in_order_traversal(root) return [] if root.nil? res = [] stack = [] node = root while node || !stack.empty? while node stack << node node = node.left end if (!stack.empty?) node = stack.pop res << node.val node = node.right end end resend
Recursive
def in_order_traversal(root) return [] if root.nil? res = [] res += pre_order_traversal(root.left) res << root.val res += pre_order_traversal(root.right)end
Iterator
class BTIterator @@stack = [] def initialize(root) add_node_to_stack(root) end def has_next? !@@stack.empty? end def next if !has_next? return -(1 << 32) end node = @@stack.pop add_node_to_stack(node.right) node.val end def add_node_to_stack(node) while node @@stack << node node = node.left end endend
3. Post-order Traversal (后序遍历先访问当前节点的所有孩子节点，然后再访问当前节点)
Non-recursive
def post_order_traversal(root) return [] if root.nil? res = [] stack = [] cur = root prev = nil while cur stack << cur cur = cur.left end while !stack.empty? cur = stack.pop if cur.right && cur.right != prev stack << cur cur = cur.right while cur stack << cur cur = cur.left end else res << cur.val prev = cur end end resend
recursive
def post_order_traversal(root) return [] if root.nil? res = [] res += post_order_traversal(root.left) res += post_order_traversal(root.right) res << root.valend
Iterator
class BTIterator @@stack = [] def initialize(root) find_next_leaf(root) end def has_next? !@@stack.empty? end def next if !has_next? return -(1 << 32) end node = @@stack.pop if !@@stack.empty? top = @@stack.last if node == top.left find_next_leaf(top.right) end end node.val end def find_next_leaf(node) while node @@stack << node if node.left node = node.left else node = node.right end end endend