Class: CodeCook::Tree::BinaryTree

Inherits:
Object
  • Object
show all
Defined in:
手写代码必备手册(Ruby版).rb

Overview

5.1 二叉树的遍历

Instance Attribute Summary (collapse)

Instance Method Summary (collapse)

Constructor Details

- (BinaryTree) initialize

初始化一棵树

像是这个样子：
* ROOT
|---+ A
|    |---> AA
|    +---> AB
+---+ B
    |---+ BA
|        |---> BAA
|        +---> BAB
    +---> BB


102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File '手写代码必备手册(Ruby版).rb', line 102

def initialize
    # 创建一棵树
    @root_node = ::Tree::BinaryTreeNode.new("ROOT", "Root Content")
    a_node = ::Tree::BinaryTreeNode.new("A", "A Content") 
    a_a_node = ::Tree::BinaryTreeNode.new("AA", "AA Content")
    a_b_node = ::Tree::BinaryTreeNode.new("AB", "AB Content")
    b_node = ::Tree::BinaryTreeNode.new("B", "B Content")
    b_a_node = ::Tree::BinaryTreeNode.new("BA", "BA Content")
    b_b_node = ::Tree::BinaryTreeNode.new("BB", "BB Content")
    b_a_a_node = ::Tree::BinaryTreeNode.new("BAA", "BAA Content")
    b_a_b_node = ::Tree::BinaryTreeNode.new("BAB", "BAB Content")

    # 建立A子树的节点
    a_node << a_a_node
    a_node << a_b_node
    # 建立B子树的节点
    b_a_node << b_a_a_node
    b_a_node << b_a_b_node
    b_node << b_a_node
    b_node << b_b_node
    # 建立根节点
    @root_node << a_node
    @root_node << b_node

    @root_node.print_tree
end

Instance Attribute Details

- (Object) root_node

Returns the value of attribute root_node



90
91
92
 
# File '手写代码必备手册(Ruby版).rb', line 90

def root_node
  @root_node
end

Instance Method Details

- (Object) in_order_r(root, action = ->(root){})

中序遍历，递归

bt = BinaryTree.new
bt.in_order_r(bt.root_node, ->(root){puts root.content})

Parameters:

  • root (Tree::BinaryTreeNode) —

    二叉树根节点

  • action (proc) (defaults to: ->(root){}) —

    二叉树处理方法



146
147
148
149
150
151
 
# File '手写代码必备手册(Ruby版).rb', line 146

def in_order_r(root, action = ->(root){})
    return if !root
    pre_order_r(root.left_child, action)
    action.call(root)
    pre_order_r(root.right_child, action)
end

- (Object) post_order_r(root, action = ->(root){})

后序遍历，递归

bt = BinaryTree.new
bt.post_order_r(bt.root_node, ->(root){puts root.content})

Parameters:

  • root (Tree::BinaryTreeNode) —

    二叉树根节点

  • action (proc) (defaults to: ->(root){}) —

    二叉树处理方法



158
159
160
161
162
163
 
# File '手写代码必备手册(Ruby版).rb', line 158

def post_order_r(root, action = ->(root){})
    return if !root
    pre_order_r(root.left_child, action)
    pre_order_r(root.right_child, action)
    action.call(root)
end

- (Object) pre_order_r(root, action = ->(root){})

先序遍历，递归

bt = BinaryTree.new
bt.pre_order_r(bt.root_node, ->(root){puts root.content})

Parameters:

  • root (Tree::BinaryTreeNode) —

    二叉树根节点

  • action (proc) (defaults to: ->(root){}) —

    二叉树处理方法



134
135
136
137
138
139
 
# File '手写代码必备手册(Ruby版).rb', line 134

def pre_order_r(root, action = ->(root){})
    return if !root
    action.call(root)
    pre_order_r(root.left_child, action)
    pre_order_r(root.right_child, action)
end