golang实现二叉查找树

骑猪看日落 2022-05-31 01:30 216阅读 0赞

二叉树：每个节点至多有两个子节点  
  
二叉查找树的特点：对于每一个节点X,左子树中所有项的值小于X中的值，而它的右子树种所有项的值大于X中的值。

二叉查找树是特殊的二叉树

以下用代码实现

type binarySearchTree struct {
    	value       int
    	left,right *binarySearchTree
    }
    
    
    //初始化并添加根节点的值
    func NewBinarySearchTree(rootValue int) *binarySearchTree {
    	return &binarySearchTree{value:rootValue}
    }
    
    
    //添加元素
    func (t *binarySearchTree) Insert(value int) *binarySearchTree {
    	if t == nil {
    		t = NewBinarySearchTree(value)
    		return t
    	}
    	if value < t.value {
    		t.left = t.left.Insert(value)
    	}else {
    		t.right = t.right.Insert(value)
    	}
    	return t
    }
    
    //是否包含某一个元素
    func (t *binarySearchTree)Contains(value int)  bool{
    	if t == nil {
    		return false
    	}
    	v :=  t.compareTo(value)
    
    	if v < 0 {
    		return t.left.Contains(value)
    	}else if v > 0 {
    		return t.right.Contains(value)
    	}else {
    		return true
    	}
    }
    
    func  (t *binarySearchTree)compareTo(value int)  int {
    	return value-t.value
    }
    
    //移除元素
    func (t *binarySearchTree) Remove(value int) *binarySearchTree {
    	if t == nil {
    		return t
    	}
    	compareResult := t.compareTo(value)
    	if compareResult <0 {
    		t.left = t.left.Remove(value)
    	}else if compareResult > 0 {
    		t.right = t.right.Remove(value)
    	}else if t.left != nil && t.right != nil {
    		t.value = t.right.FindMin()
    		t.right = t.right.Remove(t.value)
    	}else if t.left != nil {
    		t = t.left
    	}else {
    		t  = t.right
    	}
    	return t
    }
    
    //查找最大值
    func (t *binarySearchTree) FindMax() int {
    	if t ==  nil {
    		fmt.Println("tree is empty")
    		return -1
    	}
    	if t.right == nil {
    		return t.value
    	}else {
    		return t.right.FindMax()
    	}
    	//也可以用下面的方法
    	//return t.FindMaxNode().value
    }
    
    //查找最大的节点
    func (t *binarySearchTree) FindMaxNode() *binarySearchTree {
    	if  t != nil {
    		for t.right != nil {
    			t = t.right
    		}
    	}
    	return t
    }
    
    //查找最小值
    func (t *binarySearchTree) FindMin() int {
    	if t ==  nil {
    		fmt.Println("tree is empty")
    		return -1
    	}
    	if t.left == nil {
    		return t.value
    	}else {
    		return t.left.FindMin()
    	}
    	//也可以直接用下面的方法
    	//return t.FindMinNode().value
    }
    
    //查找最小的节点
    func (t *binarySearchTree) FindMinNode() *binarySearchTree {
    	if t != nil {
    		for t.left != nil {
    			t = t.left
    		}
    	}
    
    	return t
    }
    
    
    //获取树种所有的元素值（并按从小到大排序）
    func (t *binarySearchTree) GetAll() []int {
    	values := []int{}
    	return appendValues(values,t)
    }
    
    
    func appendValues(values []int, t *binarySearchTree) []int {
    	if t != nil {
    		values = appendValues(values,t.left)
    		values = append(values,t.value)
    		values = appendValues(values,t.right)
    	}
    	return values
    }
    
    
    
    func main() {
    	binaryTree := NewBinarySearchTree(50)
    	binaryTree.Insert(20)
    	binaryTree.Insert(10)
    	binaryTree.Insert(100)
    	binaryTree.Insert(60)
    	binaryTree.Insert(70)
    	binaryTree.Insert(5)
    	binaryTree.Insert(35)
    	binaryTree.Insert(40)
    	fmt.Println(binaryTree.GetAll())
    
    	fmt.Println(binaryTree.Contains(30))
    	fmt.Println(binaryTree.Contains(20))
    
    	fmt.Println(binaryTree.FindMin())
    	fmt.Println(binaryTree.FindMinNode().value)
    
    	fmt.Println(binaryTree.FindMax())
    	fmt.Println(binaryTree.FindMaxNode().value)
    
    	binaryTree.Remove(20)
    	fmt.Println(binaryTree.GetAll())
    
    }