package main
import "fmt"
type Node struct {
Key int
Left * Node
Right * Node
}
func (n *Node) Insert(key int) {
if key < n.Key{
if n.Left == nil{
n.Left = &Node{Key:key}
}
n.Left.Insert(key)
}else if key > n.Key{
if n.Right == nil{
n.Right = &Node{Key:key}
}
n.Right.Insert(key)
}
}
//中序打印
func (n * Node)print() {
if n == nil{
return
}
n.Left.print()
fmt.Println(n.Key)
n.Right.print()
}
//前序打印
func (n * Node)printpre() {
if n == nil{
return
}
fmt.Println(n.Key)
n.Left.printpre()
n.Right.printpre()
}
//后序打印
func (n * Node)printend() {
if n == nil{
return
}
n.Left.printend()
n.Right.printend()
fmt.Println(n.Key)
}
//查询
func (n * Node)Search(key int) bool {
if n == nil{
return false
}
if n.Key < key{
n.Right.Search(key)
}else if n.Key > key{
return n.Left.Search(key)
}
return true
}
//删除
func (n * Node)Delete(key int) *Node {
if n == nil{
return nil
}
if n.Key < key{
n.Right = n.Right.Delete(key)
}else if n.Key > key{
n.Left = n.Left.Delete(key)
}else {
if n.Left == nil{
return n.Right
}else if n.Right == nil{
return n.Left
}else {
min := n.Right.Min()
n.Key = min
n.Right = n.Right.Delete(min)
}
}
return n
}
//求最小值
func (n *Node)Min() int {
if n.Left==nil{
return n.Key
}
return n.Left.Min()
}
func main() {
root := &Node{Key:8}
root.Insert(3)
root.Insert(10)
root.Insert(1)
root.Insert(6)
root.Insert(14)
root.Insert(4)
root.Insert(7)
root.Insert(13)
fmt.Println("=====================中序打印==================================")
root.print()
fmt.Println("======================前序打印================================")
root.printpre()
fmt.Println("=======================后序打印================================")
root.printend()
if root.Search(10){
fmt.Println("found")
}else {
fmt.Println("not found")
}
if root.Search(100){
fmt.Println("found")
}else {
fmt.Println("not found")
}
if root.Search(0){
fmt.Println("found")
}else {
fmt.Println("not found")
}
root.Delete(6)
root.Delete(3)
root.print()
}