どのノードにおいても、左の子ノード＜親ノード＜右の子ノードとなるような木。
ex.
5
/ \
3 8
/ \ / \
1 4 6 9
それぞれのノード探索順はwww.momoyama-usagi.com - うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法に記載されている方法が覚えやすいのでそちらのリンクを記載する。
ルートノードから走査を開始し、左部分木、右部分木の順で再帰的に走査する。
rootがpre（事前）なので根→左→右と覚えておく良い。（根の位置だけ覚えておけば良い。左、右は必ず左が先になる。）
木を一筆書きで括ったときに、ノードの左側を通った順がpreorder。
5
/ \
3 8
/ \ / \
1 4 6 9
5 -> 3 -> 1 -> 4 -> 8 -> 6 -> 9
左部分木から再帰的に走査し、ルートノード、右部分木の順に走査する。
rootがin（間）なので左→根→右と覚えておく良い。（根の位置だけ覚えておけば良い。左、右は必ず左が先になる。）
木を一筆書きで括ったときに、ノードの下側を通った順がinorder。
5
/ \
3 8
/ \ / \
1 4 6 9
1 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9
左部分木から再帰的に走査し、右部分木、ルートノードの順で走査する。
rootがpost（事後）なので左→右→根と覚えておく良い。（根の位置だけ覚えておけば良い。左、右は必ず左が先になる。）
余談だが、逆ポーランド記法はスタックで解くこともできるが、二分木をpostorderでも解くことができる。
木を一筆書きで括ったときに、ノードの右側を通った順がpostorder。
5
/ \
3 8
/ \ / \
1 4 6 9
1 -> 4 -> 3 -> 6 -> 9 -> 8 -> 5
深さごとに走査する。
5
/ \
3 8
/ \ / \
1 4 6 9
5 -> 3 -> 8 -> 1 -> 4 -> 6 -> 9
ソースコードはbinary_search_treeにある。
package main
import "fmt"
// a binary search tree.
type tree struct {
root *node
}
// a node for binary search tree.
type node struct {
val string
l *node
r *node
}
// insert a value to tree.
func (t *tree) insert(v string) {
t.root = t.root.insertNode(v)
}
// insert a node to tree.
func (n *node) insertNode(v string) *node {
if n == nil {
return &node{val: v}
}
if v < n.val {
n.l = n.l.insertNode(v)
} else if v > n.val {
n.r = n.r.insertNode(v)
}
return n
}
// search a value from tree.
func (t *tree) search(v string) bool {
return t.root.searchNode(v)
}
// search a node from tree.
func (n *node) searchNode(v string) bool {
if n == nil {
return false
}
if v == n.val {
return true
} else if v < n.val {
return n.l.searchNode(v)
} else {
return n.r.searchNode(v)
}
}
// remove a value from tree.
func (t *tree) remove(v string) {
t.root = t.root.removeNode(v)
}
// remove a node from tree.
func (n *node) removeNode(v string) *node {
if n == nil {
return nil
}
if v < n.val {
n.l = n.l.removeNode(v)
return n
} else if v > n.val {
n.r = n.r.removeNode(v)
return n
} else {
// node has no children
if n.l == nil && n.r == nil {
return nil
}
// node has only right child
if n.l == nil {
return n.r
}
// node has only left child
if n.r == nil {
return n.l
}
// node has both children
leftmostrightside := n.r
for leftmostrightside.l != nil {
leftmostrightside = leftmostrightside.l
}
n.val = leftmostrightside.val
n.r = n.r.removeNode(n.val)
return n
}
}
// breadth first search - preorder
//
// 5
// / \
// 3 8
// / \ / \
// 1 4 6 9
//
// 5 -> 3 -> 1 -> 4 -> 8 -> 6 -> 9
func (t *tree) preorder(n *node, f func(string)) {
if n != nil {
// root → left → right
f(n.val)
t.preorder(n.l, f)
t.preorder(n.r, f)
}
}
// breadth first search - inorder
//
// 5
// / \
// 3 8
// / \ / \
// 1 4 6 9
//
// 1 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9
func (t *tree) inorder(n *node, f func(string)) {
if n != nil {
// left → root → right
t.inorder(n.l, f)
f(n.val)
t.inorder(n.r, f)
}
}
// breadth first search - postorder
//
// 5
// / \
// 3 8
// / \ / \
// 1 4 6 9
//
// 1 -> 4 -> 3 -> 6 -> 9 -> 8 -> 5
func (t *tree) postorder(n *node, f func(string)) {
if n != nil {
// left → right → root
t.postorder(n.l, f)
t.postorder(n.r, f)
f(n.val)
}
}
// depth first search
//
// 5
// / \
// 3 8
// / \ / \
// 1 4 6 9
//
// 5 -> 3 -> 8 -> 1 -> 4 -> 6 -> 9
func (t *tree) dfs(n *node, f func(string)) {
if n != nil {
s := []*node{n}
for len(s) > 0 {
crtn := s[0]
f(crtn.val)
s = s[1:]
if crtn.l != nil {
s = append(s, crtn.l)
}
if crtn.r != nil {
s = append(s, crtn.r)
}
}
}
}
func main() {
t := &tree{}
t.insert("5")
t.insert("3")
t.insert("8")
t.insert("1")
t.insert("4")
t.insert("6")
t.insert("9")
t.insert("11")
fmt.Println(t.search("11")) // true
t.remove("11")
fmt.Println(t.search("11")) // false
f := func(v string) {
fmt.Println(v)
}
t.preorder(t.root, f) // 5314869
fmt.Println("-----")
t.inorder(t.root, f) // 1345689
fmt.Println("-----")
t.postorder(t.root, f) // 1436985
fmt.Println("-----")
t.dfs(t.root, f) // 5381469
}
幅優先探索は、根の探索開始位置（preorderなら根→左→右）だけ覚えておけば再帰処理はそれに従って書ける。
深さ優先探索は少し面倒。後は二分探索木に限らずノードの削除処理はもっと面倒...。
探索パターンはとりあえずこうやって覚えておけば頭には留められそう。