이진 트리란 트리의 차수(degree)가 2 이거나 그보다 낮은 트리를 말한다.
이진 트리 중에 특별한 이름을 붙여준 것들이 있는데, Full Binary Tree / Complete Binary Tree / Skewed Binary Tree 가 있다. 설명은 생략(이름만 봐도 기억해야 함)
이진 트리 순회 방법은 전위 순회 / 중위 순회 / 후위 순회가 있고 각각 DLR / LDR / LRD 순서대로 순회하는 것이다. 참고할 사항은, 수식을 트리로 만들면 이진 트리 순회 방법에 따라 전위 / 중위 / 후위 표기법을 구할 수 있다.
이진 트리는 일차원 배열로 만들 수 있고 링크드 리스트로 만들 수도 있다. 배열로 만들 경우 부모, 자식들의 인덱스 구하는 공식이 있는데 아 귀찮아 제끼고, 링크드 리스트로 만들었다.
결과>
이진 트리 중에 특별한 이름을 붙여준 것들이 있는데, Full Binary Tree / Complete Binary Tree / Skewed Binary Tree 가 있다. 설명은 생략(이름만 봐도 기억해야 함)
이진 트리 순회 방법은 전위 순회 / 중위 순회 / 후위 순회가 있고 각각 DLR / LDR / LRD 순서대로 순회하는 것이다. 참고할 사항은, 수식을 트리로 만들면 이진 트리 순회 방법에 따라 전위 / 중위 / 후위 표기법을 구할 수 있다.
이진 트리는 일차원 배열로 만들 수 있고 링크드 리스트로 만들 수도 있다. 배열로 만들 경우 부모, 자식들의 인덱스 구하는 공식이 있는데 아 귀찮아 제끼고, 링크드 리스트로 만들었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
# Binary-Tree Implementation
# Jungtaek Lim(Heart), 2009-03-04
class BinaryTreeNode
attr_accessor :left_child, :right_child, :parent, :data
def initialize
@left_child = nil
@right_child = nil
@parent = nil
@data = nil
end
end
class BinaryTree
def initialize
@root = nil
end
def insert_node(parent_node, data, is_left)
node = BinaryTreeNode.new
node.data = data
if parent_node == nil
@root = node
else
node.parent = parent_node
if true == is_left
if nil != parent_node.left_child
left_child_node = parent_node.left_child
delete_node(left_child_node)
end
parent_node.left_child = node
else
if nil != parent_node.right_child
right_child_node = parent_node.right_child
delete_node(right_child_node)
end
parent_node.right_child = node
end
end
return node
end
def delete_node(node)
if @root == node # node.parent must nil!!
@root = nil
return
end
node.parent.left_child = nil if (node.parent.left_child == node)
node.parent.right_child = nil if (node.parent.right_child == node)
clean_subtree(node)
end
def preorder_traversal
travel_list = []
preorder_traversal_recursive(travel_list, @root) unless @root == nil
return travel_list
end
def inorder_traversal
travel_list = []
inorder_traversal_recursive(travel_list, @root) unless @root == nil
return travel_list
end
def postorder_traversal
travel_list = []
postorder_traversal_recursive(travel_list, @root) unless @root == nil
return travel_list
end
private
def preorder_traversal_recursive(travel_list, node)
return if node == nil
travel_list.push(node)
preorder_traversal_recursive(travel_list, node.left_child)
preorder_traversal_recursive(travel_list, node.right_child)
end
def inorder_traversal_recursive(travel_list, node)
return if node == nil
inorder_traversal_recursive(travel_list, node.left_child)
travel_list.push(node)
inorder_traversal_recursive(travel_list, node.right_child)
end
def postorder_traversal_recursive(travel_list, node)
return if node == nil
postorder_traversal_recursive(travel_list, node.left_child)
postorder_traversal_recursive(travel_list, node.right_child)
travel_list.push(node)
end
def clean_subtree(root_node)
# 서브트리 순회하면서 레퍼런스 다 끊음(GC 대상으로 만듬)
subtree_node_list = []
preorder_traversal_recursive(subtree_node_list, root_node)
subtree_node_list.each do |node|
node.left_child = nil
node.right_child = nil
node.parent = nil
end
end
end
def print_travel_node_list(travel_list)
print '[ '
travel_list.each do |node|
print node.data
print " "
end
puts ']'
end
binary_tree = BinaryTree.new
node = binary_tree.insert_node(nil, '-', true)
node2 = binary_tree.insert_node(node, '*', true)
node3 = binary_tree.insert_node(node, '/', false)
binary_tree.insert_node(node2, 'A', true)
binary_tree.insert_node(node2, 'B', false)
binary_tree.insert_node(node3, 'C', true)
binary_tree.insert_node(node3, 'D', false)
print_travel_node_list binary_tree.preorder_traversal
print_travel_node_list binary_tree.inorder_traversal
print_travel_node_list binary_tree.postorder_traversal
binary_tree.delete_node(node2)
print_travel_node_list binary_tree.preorder_traversal
node4 = binary_tree.insert_node(node, '*', false)
binary_tree.insert_node(node4, 'A', true)
binary_tree.insert_node(node4, 'B', false)
print_travel_node_list binary_tree.preorder_traversal
|
결과>
[ - * A B / C D ]
[ A * B - C / D ]
[ A B * C D / - ]
[ - / C D ]
[ - * A B ]
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Heap - in Ruby (0) | 2009/03/05 |
|---|---|
| Binary Search Tree - in Ruby (0) | 2009/03/04 |
| Binary Tree - in Ruby (0) | 2009/03/04 |
| Deck(Deque, Double-ended Queue) - in Ruby (0) | 2009/03/04 |
| Circular Queue - in Ruby (0) | 2009/03/04 |
| Queue - in Ruby (4) | 2009/03/04 |
