代码实现

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
package main

import "fmt"

type BNode struct {
    data  int64
    left  *BNode
    right *BNode
}

type BTree interface {
    Insert(data int64)
    Delete(data int64)
    Find(data interface{}) *BNode
}

type Tree struct {
    root *BNode
}

func (t *Tree) Insert(data int64) *Tree {
    node := &BNode{data: data}
    if t.root == nil {
        t.root = node
        return t
    }
    current := t.root
    for {
        if data < current.data {
            if current.left == nil {
                current.left = node
                break
            }
            current = current.left
        }
        if data > current.data {
            if current.right == nil {
                current.right = node
                break
            }
            current = current.right
        }
    }
    return t
}

func (t *Tree) Delete(data int64) bool {
    if t.root == nil {
        return false
    }
    var parent *BNode
    current := t.root
    for {
        // 当前节点是要删除的节点
        if data == current.data {
            // 1. 当前节点没有子节点
            if current.left == nil && current.right == nil {
                // 1.1 当前节点是根节点
                if parent == nil {
                    t.root = nil
                    return true
                }
                // 1.1 当前节点不是根节点
                if parent.left == current {
                    parent.left = nil
                } else {
                    parent.right = nil
                }
                return true
            }
            // 2. 当前节点有一个子节点
            // 2.1 当前节点只有左子节点，没有右子节点
            if current.left != nil && current.right == nil {
                // 父节点为空，说明当前节点是根节点
                if parent == nil {
                    parent = current.left
                    return true
                }
                // 父节点不为空，说明当前节点不是根节点，把当前节点的左子节点挂到父节点（左子节点/右子节点）上
                // 如果父节点的左子节点是当前节点，把当前节点的左子节点挂到父节点的左子节点上，反之把当前节点的左子节点挂到父节点的右子节点上
                if parent.left == current {
                    parent.left = current.left
                } else {
                    parent.right = current.left
                }
            }
            // 2.2 当前节点只有右子节点，没有左子节点
            if current.left == nil && current.right != nil {
                if parent == nil {
                    parent = current.right
                    return true
                }
                // 父节点不为空，说明当前节点不是根节点，把当前节点的右子节点挂到父节点（左子节点/右子节点）上
                // 如果父节点的左子节点是当前节点，把当前节点的右子节点挂到父节点的左子节点上，反之把当前节点的右子节点挂到父节点的右子节点上
                if parent.left == current {
                    parent.left = current.right
                } else {
                    parent.right = current.right
                }
            }
            // 3. 当前节点有两个子节点
            if current.left != nil && current.right != nil {
                // 3.1 找到当前节的右子节点的最小节点
                minNode := current.right
                minNodeParent := current
                for minNode.left != nil {
                    minNodeParent = minNode
                    minNode = minNode.left
                }
                // 3.2 把右子树的最小节点的值赋值给当前节点
                current.data = minNode.data
                // 3.3 删除最小节点
                // 3.3.1 这种情况是删除的节点只有两个子节点，且两个子节点都没有左子节点，这种情况是$minNode节点就是当前节点的右子节点
                if current.right == minNode {
                    current.right = minNode.right
                } else {
                    // 3.3.2 这中情况是删除的节点有两个子节点，且找到了中序后继节点，因为中序后继节点需要替换到被删除的节点位置
                    // 所以中序后继节点的父节点的左子节点需要设置为中序后继节点的右子节点，因为中序后继节点的左子节点一定是null
                    minNodeParent.left = minNode.right
                }
                return true
            }
        } else if data < current.data {
            if current.left == nil {
                return false
            }
            parent = current
            current = current.left
        } else if data > current.data {
            if current.right == nil {
                return false
            }
            parent = current
            current = current.right
        }
    }

}

func (t *Tree) Find(value int64) *BNode {
    if t.root == nil {
        return nil
    }
    current := t.root
    for {
        if value == current.data {
            break
        }
        if value < current.data {
            current = current.left
        }
        if value > current.data {
            current = current.right
        }
    }
    return current
}

示例

1
2
3
4
5
6
7
8
9
10
func main() {
    tree := Tree{root: nil}
    fmt.Printf("tree的值：%v\n", tree)
    tree.Insert(50).Insert(38).Insert(60).Insert(20).Insert(40).Insert(52).Insert(62).Insert(53).Insert(48).Insert(54).Insert(63)
    fmt.Printf("插入后tree：%+v\n", tree)
    node := tree.Find(40)
    fmt.Printf("node的值：%+v\n", *node)
    tree.Delete(60)
    fmt.Printf("删除后tree的值：%+v\n", *tree.root.left)
}