go语言实现二叉搜索树

整理:张帅 博客 : zhangshuai.ren

基本概念介绍

  • 树(tree) : 一种分层的数据结构,类比家谱

  • 二叉搜索树(binary tree): 左节点的值均小于右节点的二叉树

  • 深度(depth):root根结点到当前节点唯一路径的长度

  • 高度(height):从当前节点到一片树叶最长的路径的长度

  • 根(root):深度为0的树节点

  • 内部节点(internal node):至少有一个子节点的节点

  • 树叶节点(leaf):无子节点的节点

  • 兄弟节点(sibling):拥有相同父节点的子节点

应用

文件系统和数据库系统一般都采用树(特别是B树)的数据结构数据,主要为排序和检索的效率。二叉树是一种最基本最典型的排序树,对于学习和研究树的特性,但是本身很少在实际中进行应用。就像冒泡排序一样,二叉树因为效率问题并不实用。

二叉树的常用操作

  • Insert(v) //向二叉树的合适位置插入节点
  • Remove(v). // 移除树中所有值为v的节点
  • Search(v) //检查值为v的元素是否在树中
  • Min(). //获取二叉树中最小的值
  • Max() //获取二叉树中最大的值
  • InOrderTraverse() //中序遍历树
  • PreOrderTraverse() //先序遍历树
  • PostOrderTraverse() //后序遍历树
  • String() //在命令行格式化打印出二叉树

同样适用genny提供代码的复用性,树类型命名为:ItemBinarySearchTree,树节点的结构体定义如下:

在命令端使用 
go get "github.com/cheekybits/genny/generic" 
命令获取这个包

import (
    "fmt"
    "sync"

    "github.com/cheekybits/genny/generic"  
)


type Item generic.Type   //generic.Type 为"github.com/cheekybits/genny/generic"这个包下面的一个空接口类型,type为generic.Type起别名为Item


// 二叉树结构体
type ItemBinarySearchTree struct {
	root *Node  // 根节点
	lock sync.RWMutex  //读写锁
}


type Node struct{
    key        int    //中序遍历的节点序号
    value      Item   //节点存储的值
    left       *Node  //左节点
    right      *Node   //右面节点
}

插入操作与遍历

插入操作需要使用到递归,插入操作需要从上到下的查找新节点在树中合适的位置,新节点的值小于任意节点,则向左子树继续寻找,同理向右子树寻找,直到树叶节点再插入。

遍历操作有三种方式:

  • 中序遍历(in-order):左子树(L)–>根节点(D)–>右树(R)1->2->3->4->5->6->7->8->9->10- >11 (LDR)

  • 先序遍历(pre-order):根节点(D)–>左子树(L)–>右树(R) 8->4->2->1->3->6->5->7 >10->9- >11(DLR)

  • 后序遍历(pre-order):左子树(L)–>右子树(R)–>根节点(D) 1->3->2->5->7->6->4->9>11->10- >8 (LRD)

根据根节点的位置来看是什么序列遍历

String() 可视化树结构

代码实现

Insert

//向二叉树合适的位置插入节点
func (tree *ItemBinarySearchTree) Insert(key int, value Item) {

//为了确保操作二叉树的数据安全,对数据操作进行读写上锁
	tree.lock.Lock()
	defer tree.lock.Unlock()
	newNode := &Node{key, value, nil, nil}
//如果当前的树为空,那么插入的节点作为根节点
	if tree.root == nil {
		tree.root = newNode
	} else {
	//调用下面的插入函数,另起一个方法👇
		insertNode(tree.root, newNode)
	}

}

//找到合适的位置
func insertNode(node, newNode *Node) {

//当新节点的值小于节点的值的时候,应该插入到节点的左侧
	if newNode.key < node.key {
	//如果旧节点左侧没有节点,那么旧节点直接赋值新节点
		if node.left == nil {
			node.left = newNode
		} else {
		//否则将左节点作为老节点,继续寻找左节点的左节点
			insertNode(node.left, newNode)
		}
	} else {
	//与上面同理
		if node.right == nil {
			node.right = newNode
		} else {
			insertNode(node.right, newNode)
		}
	}

}

Search

//检查key的元素是否存在
func (tree *ItemBinarySearchTree) Search(key int) bool {

	tree.lock.Lock()
	defer tree.lock.Unlock()
	return search(tree.root, key)

}
func search(node *Node, key int) bool {

	if node == nil {
		return false
	}
  //如果key的值小于节点的值,那么应该插入到左子树
	if key < node.key {
	//将左子树作为新节点,继续查询
		return search(node.left, key)
	}
	
	// 如果key的值大于节点的值,那么应该插入右子树
	if key > node.key {
	//将右子树作为新节点,继续查询
		return search(node.right, key)
	}

//如果当前key的值==node.key 返回true
	return true

}


Remove

删除节点的流程

先递归查找,再删除节点。但是在删除时需要根据节点拥有子节点的数量,分如下3中情况:

代码实现


func (tree *ItemBinarySearchTree) remove(key int) {

	tree.lock.Lock()
	defer tree.lock.Unlock()
	remove(tree.root, key)
	
}

func remove(node *Node, key int) *Node {
	if node == nil {
		return nil
	}
	
   // 如果key< node.key 则向左寻找
	
	if key < node.key {
	
		// 将左节点作为新节点递归继续寻找
		
		node.left = remove(node.left, key)
		return node
	}

	// 如果key> node.key 则向右寻找

	if key > node.key {
	
	// 将右节点作为新节点递归继续寻找
	
		node.right = remove(node.right, key)
		return node
	}

//如果key==node.key 判断node有没有左右子树,如果没有,则直接删除
	if node.left == nil && node.right == nil {

		node = nil
		return node
	}
//如果key==node.key 判断node有没有左右子树,如果有右子树,则将右子树直接赋值给当前节点,完成覆盖删除
	if node.left == nil {
		node = node.right
		return node
	}
	
	//如果key==node.key 判断node有没有左右子树,如果有右子树,则将右子树直接赋值给当前节点,完成覆盖删除
	
	if node.right == nil {
		node = node.left
		return node
	}

	mostLeftNode := node.right
// 要删除的节点有2个字节点,找到右子树的最左节点,替换当前节点􏱚􏱐􏲝􏰈􏰖􏰗􏰛 
	for {
	
	//一直遍历找到最左节点
		if mostLeftNode != nil && mostLeftNode.left != nil {
			mostLeftNode = mostLeftNode.left
		} else {
			break
		}

	}

// 使用右子树的最左节点替换当前的节点,即删除当前节点
	node.key, node.value = mostLeftNode.key,mostLeftNode.value

	node.right = remove(node.right, node.key)

	return node

}


Max

//获取最大节点即为二叉树最右节点,根据二叉树的性质

func (tree *ItemBinarySearchTree) Max() *Item {

	tree.lock.Lock()
	defer tree.lock.Unlock()
	node := tree.root
	if node == nil {
		return nil
	}
	for {

		if node.right == nil {
			return &node.value
		}

		node = node.right
	}

}

Min


// 根据二叉树的性质,获取最大节点即为二叉树最右节点

func (tree *ItemBinarySearchTree) Min() *Item {

	tree.lock.Lock()
	defer tree.lock.Unlock()

	node := tree.root

	if node == nil {
		return nil
	}

	for {
		if node.left == nil {
			return &node.value
		} else {
			node = node.left
		}

	}

}

Traverse


// 先序遍历:根节点 -> 左子树 ->右子树
func (tree *ItemBinarySearchTree) PreOrderTraverse(printFunc func(Item)) {

	tree.lock.Lock()
	defer tree.lock.Unlock()
	
	preOrderTraverse(tree.root, printFunc)

}

func preOrderTraverse(node *Node, printFunc func(Item)) {

	if node != nil {
	//先打印根节点
		printFunc(node.value)
		
		//然后递归调用自己,将左节点作为新节点,打印
		preOrderTraverse(node.left, printFunc)
		//然后递归调用自己,将右节点作为新节点,打印
		preOrderTraverse(node.right, printFunc)

	}

}

// 中序遍历: 左子树 ->根节点 ->右子树
func (tree *ItemBinarySearchTree) PostOrderTraverse(printFunc func(Item)) {

	tree.lock.Lock()
	defer tree.lock.Unlock()

	postOrderTraverse(tree.root, printFunc)

}

func postOrderTraverse(node *Node, printFunc func(Item)) {

	if node != nil {
    //递归调用自己,将左节点作为新节点,打印
		preOrderTraverse(node.left, printFunc)
		//打印根节点
		printFunc(node.value)
		//递归调用自己,将右节点作为新节点,打印
		preOrderTraverse(node.right, printFunc)

	}

}


// 后序遍历: 左子树  ->右子树->根节点

func (tree *ItemBinarySearchTree) InOrderTraverse(printFunc func(Item)) {

	tree.lock.Lock()
	defer tree.lock.Unlock()

	inOrderTraverse(tree.root, printFunc)

}

func inOrderTraverse(node *Node, printFunc func(Item)) {

	if node != nil {
     //递归调用自己,将左节点作为新节点,打印
		preOrderTraverse(node.left, printFunc)
		//递归调用自己,将右节点作为新节点,打印
		preOrderTraverse(node.right, printFunc)
		//打印根节点
		printFunc(node.value)

	}

}

String


//后序遍历打印树的结构
func (tree *ItemBinarySearchTree) String() {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	if tree.root == nil {
		println("Tree is empty")
		return
	}
	stringify(tree.root, 0)
	println("----------------------------")
}
func stringify(node *Node, level int) {
	if node == nil {
		return
	}
	format := ""
	for i := 0; i < level; i++ {
		format += "\t" //根据节点的深度决定缩进长度

	}
	format += "----[ "
	level++
	//先递归打印左子树􏱈􏱉􏱊􏱋􏱌􏰟􏰜􏰀 
	stringify(node.left, level)
	//打印值
	fmt.Printf(format+"%d\n", node.key) 
	//再递归打印右子树
	 stringify(node.right, level)
}

总结

对于二叉树的操作,增删查都与递归相关,所以实现的时候一定要分析清楚递归的终止条件,在正确的条件下return,避开死循环。

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦