97 lines
1.9 KiB
Go
97 lines
1.9 KiB
Go
package main
|
||
|
||
import "fmt"
|
||
|
||
type BinaryNode2 struct {
|
||
Key int
|
||
Left *BinaryNode2
|
||
Right *BinaryNode2
|
||
}
|
||
|
||
func (n *BinaryNode2) Insert(key int) {
|
||
// если входной ключ больше, то идем вправо
|
||
if n.Key < key {
|
||
if n.Right == nil {
|
||
n.Right = &BinaryNode2{Key: key}
|
||
} else {
|
||
n.Right.Insert(key)
|
||
}
|
||
} else if n.Key > key {
|
||
// иначе идем влево
|
||
if n.Left == nil {
|
||
n.Left = &BinaryNode2{Key: key}
|
||
} else {
|
||
n.Left.Insert(key)
|
||
}
|
||
}
|
||
}
|
||
|
||
func (n *BinaryNode2) MinNode() *BinaryNode2 {
|
||
current := n
|
||
|
||
// цикл, ищущий самый левый лист
|
||
for current.Left != nil {
|
||
current = current.Left
|
||
}
|
||
return current
|
||
}
|
||
|
||
func (n *BinaryNode2) Delete(key int) *BinaryNode2 {
|
||
if n == nil {
|
||
return nil
|
||
}
|
||
|
||
// если входной ключ меньше, то находится в левом поддереве
|
||
if key < n.Key {
|
||
n.Left = n.Left.Delete(key)
|
||
} else if key > n.Key {
|
||
n.Right = n.Right.Delete(key)
|
||
} else {
|
||
// узел с одним ребенком или без ребенка
|
||
if n.Left == nil {
|
||
return n.Right
|
||
} else if n.Right == nil {
|
||
return n.Left
|
||
}
|
||
|
||
// узел с двумя детьми: получить минимальный узел в правом поддереве
|
||
minRight := n.Right.MinNode()
|
||
n.Key = minRight.Key
|
||
n.Right = n.Right.Delete(minRight.Key)
|
||
}
|
||
|
||
return n
|
||
}
|
||
|
||
func (n *BinaryNode2) InOrderPrint() {
|
||
if n != nil {
|
||
n.Left.InOrderPrint()
|
||
fmt.Print(n.Key, " ")
|
||
n.Right.InOrderPrint()
|
||
}
|
||
}
|
||
|
||
type BinaryTree2 struct {
|
||
Root *BinaryNode2
|
||
}
|
||
|
||
func (t *BinaryTree2) Insert(key int) *BinaryTree2 {
|
||
if t.Root == nil {
|
||
t.Root = &BinaryNode2{Key: key}
|
||
} else {
|
||
t.Root.Insert(key)
|
||
}
|
||
return t
|
||
}
|
||
|
||
func (t *BinaryTree2) Delete(key int) *BinaryTree2 {
|
||
if t.Root != nil {
|
||
t.Root = t.Root.Delete(key)
|
||
}
|
||
return t
|
||
}
|
||
|
||
func (t *BinaryTree2) InOrderPrint() {
|
||
t.Root.InOrderPrint()
|
||
}
|