官网有一个二叉排序树的例子，在此基础上增加了查找和删除节点功能。

   代码:  

package main

//Binary Search Trees
//author: Xiong Chuan Liang
//date: 2015-2-1

import (
	"fmt"
	"math/rand"
)

func main() {

	t := New(10, 1)

	if Search(t, 6) {
		fmt.Println("Search(6) true")
	} else {
		fmt.Println("Search(6) false")
	}
	Print(t)

	if Delete(t, 6) {
		fmt.Println("Delete(6) true")
	} else {
		fmt.Println("Delete(6) false")
	}
	Print(t)

	if Delete(t, 9) {
		fmt.Println("Delete(9) true")
	} else {
		fmt.Println("Delete(9) false")
	}
	Print(t)

	min, foundMin := GetMin(t)
	if foundMin {
		fmt.Println("GetMin() =", min)
	}

	max, foundMax := GetMax(t)
	if foundMax {
		fmt.Println("GetMax() =", max)
	}

	t2 := New(100, 1)
	fmt.Println(Compare(t2, New(100, 1)), " Compare() Same Contents")
	fmt.Println(Compare(t2, New(99, 1)), " Compare() Differing Sizes")

}

type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}

func New(n, k int) *Tree {
	var t *Tree
	for _, v := range rand.Perm(n) {
		t = Insert(t, (1+v)*k)
	}
	return t
}

func Insert(t *Tree, v int) *Tree {
	if t == nil {
		return &Tree{nil, v, nil}
	}
	if v < t.Value {
		t.Left = Insert(t.Left, v)
		return t
	}
	t.Right = Insert(t.Right, v)
	return t
}

//中序遍历
func Print(t *Tree) { //Recursive
	if t == nil {
		return
	}
	Print(t.Left)
	fmt.Println("node:", t.Value)
	Print(t.Right)
}

func Search(t *Tree, v int) bool {

	if t == nil {
		return false
	}
	switch {
	case v == t.Value:
		return true
	case v < t.Value:
		return Search(t.Left, v)
	case v > t.Value:
		return Search(t.Right, v)
	}
	return false
}

func GetMin(t *Tree) (int, bool) {
	if t == nil {
		return -1, false
	}

	for {
		if t.Left != nil {
			t = t.Left
		} else {
			return t.Value, true
		}
	}
}

func GetMax(t *Tree) (int, bool) {
	if t == nil {
		return -1, false
	}
	for {
		if t.Right != nil {
			t = t.Right
		} else {
			return t.Value, true
		}
	}
}

func Delete(t *Tree, v int) bool {
	if t == nil {
		return false
	}

	parent := t
	found := false
	for {
		if t == nil {
			break
		}
		if v == t.Value {
			found = true
			break
		}

		parent = t
		if v < t.Value { //left
			t = t.Left
		} else {
			t = t.Right
		}
	}

	if found == false {
		return false
	}
	return deleteNode(parent, t)
}

func deleteNode(parent, t *Tree) bool {
	if t.Left == nil && t.Right == nil {
		fmt.Println("delete() 左右树都为空 ")
		if parent.Left == t {
			parent.Left = nil
		} else if parent.Right == t {
			parent.Right = nil
		}
		t = nil
		return true
	}

	if t.Right == nil { //右树为空
		fmt.Println("delete() 右树为空 ")
		parent.Left = t.Left.Left
		parent.Value = http://www.mamicode.com/t.Left.Value>运行效果: 
Search(6) true
node: 1
node: 2
node: 3
node: 4
node: 5
node: 6
node: 7
node: 8
node: 9
node: 10
delete() 左右树都为空
Delete(6) true
node: 1
node: 2
node: 3
node: 4
node: 5
node: 7
node: 8
node: 9
node: 10
delete() 右树为空
Delete(9) true
node: 1
node: 2
node: 3
node: 4
node: 5
node: 8
node: 10
GetMin() = 1
GetMax() = 10
true  Compare() Same Contents
false  Compare() Differing Sizes
 官网的例子中,Compare函数真是赞。

MAIL : xcl_168@aliyun.com
BLOG: http://blog.csdn.net/xcl168



Go语言实现二叉查找树(Binary Search Trees)