Skip to main content
 首页 » 编程设计

Golang数据结构: 二叉搜索树

2022年07月19日137kevingrace

Golang数据结构: 二叉搜索树

树用于表示层次结构，比较好理解的类比是家族关系树。和哈希表或图结构一样，属于非连续数据结构。

二叉树是每个节点最多只有两个子节点。二叉搜索树的特性是左节点的值小于右节点，它是非常有用的数据结构，用于有效地存储和索引数据，以及数据检索。

1. 功能描述

1.1 术语

根节点：树的第顶级(零级)节点
子节点：树中除了根节点的节点
内部节点：每个节点至少有一个子节点
叶子节点：没有子节点的节点
子树：以某个节点作为根的节点集

1.2 方法说明

二叉树结构一般需要以下方法：

  • Insert(t) 在树中插入原始
  • Search(t) 如果树中存在该元素则返回true
  • InOrderTraverse() 按照中序方式遍历所有
  • PreOrderTraverse() 按照前序方式遍历所有
  • PostOrderTraverse() 按照后序方式遍历所有
  • Min() 返回树中最小元素
  • Max() 返回树中最大元素
  • String() 在命令行下渲染树

我们将创建ItemBinarySearchTree泛型，并发安全的数据结构。可以使用genny生成具体类型树实现，其中封装包括特定值数据结构。

首先定义节点结构体：

type Node struct { 
    key   int 
    value Item 
    left  *Node //left 
    right *Node //right 
}

key对应值可以是任意数据类型Item类型，key类型这里使用int类型，实际可以是任何能进行比较的数据类型。

在树中插入元素需要使用递归，因为需要为其找到合适的位置。规则是如果节点的key小于当前节点，如果其没有左子节点则作为其左子节点，否则使用其左子节点作为当前节点重新计算。又子节点规则一样。

遍历是遍历树所有节点的过程，提供三种方法实现。以这棵二叉搜索树为例:

  • 中序：查找最小节点，即最左边叶子节点，然后访问该节点。然后继续至链接至当前节点的下一个最小节点。遍历顺序为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11

  • 前序：访问子节点之前，首先访问当前节点：8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 11

  • 后续节点：查找最小节点，即最左边叶子节点，然后处理兄弟节点，再是父节点。接着至下一个子树并向上遍历父节点：1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8

String方法，用于测试，通过打印节点信息让用户通过可视化方式检查。

------------------------------------------------ 
                     ---[ 1 
              ---[ 2 
                     ---[ 3 
       ---[ 4 
                     ---[ 5 
              ---[ 6 
                     ---[ 7 
---[ 8 
              ---[ 9 
       ---[ 10 
              ---[ 11 
------------------------------------------------

2. 实现

这里主要说下删除逻辑，给定键删除对应节点。

如果待删除key小于当前节点key，则设当前节点为其左节点并递归调用自身。如果大于当前节点，则设当前节点为其右节点并递归调用自身。

直到两者key相等，则找到对应要删除的节点。如果找不到则直接返回nil。

删除节点有分几种情况。

  1. 没有子节点
    直接设置该节点为nil，返回该节点。
  2. 有一个子节点
    如果左节点为nil，则让该节点为其右节点。如果右节点为nil，让该节点为其左节点。然后返回该节点。
  3. 有两个子节点
    最复杂的是这种情况。
    因为可能节点还有其子节点。我们找到有子子树中的最小节点作为当前节点，然后删右边最小节点，最后返回该节点。
package tree 
 
import ( 
	"fmt" 
	"github.com/cheekybits/genny/generic" 
	"sync" 
) 
 
// 定义泛型 
type Item generic.Type 
 
// 树节点结构体 
type Node struct { 
	key   int 
	value Item 
	left  *Node //left 
	right *Node //right 
} 
 
// 二叉搜索树结构体 
type ItemBinarySearchTree struct { 
	root *Node 
	lock sync.RWMutex 
} 
 
// 插入元素 
func (bst *ItemBinarySearchTree) Insert(key int, value Item) { 
	bst.lock.Lock() 
	defer bst.lock.Unlock() 
	n := &Node{key, value, nil, nil} 
	if bst.root == nil { 
		bst.root = n 
	} else { 
		insertNode(bst.root, n) 
	} 
} 
 
// 从node开始查找位置并插入新节点 
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) 
		} 
	} 
} 
 
// 中序遍历 
func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) { 
	bst.lock.RLock() 
	defer bst.lock.RUnlock() 
	inOrderTraverse(bst.root, f) 
} 
 
// internal recursive function to traverse in order 
func inOrderTraverse(n *Node, f func(Item)) { 
	if n != nil { 
		inOrderTraverse(n.left, f) 
		f(n.value) 
		inOrderTraverse(n.right, f) 
	} 
} 
 
// 前序遍历 
func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) { 
	bst.lock.Lock() 
	defer bst.lock.Unlock() 
	preOrderTraverse(bst.root, f) 
} 
 
// internal recursive function to traverse pre order 
func preOrderTraverse(n *Node, f func(Item)) { 
	if n != nil { 
		f(n.value) 
		preOrderTraverse(n.left, f) 
		preOrderTraverse(n.right, f) 
	} 
} 
 
// 后续遍历 
func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) { 
	bst.lock.Lock() 
	defer bst.lock.Unlock() 
	postOrderTraverse(bst.root, f) 
} 
 
// internal recursive function to traverse post order 
func postOrderTraverse(n *Node, f func(Item)) { 
	if n != nil { 
		postOrderTraverse(n.left, f) 
		postOrderTraverse(n.right, f) 
		f(n.value) 
	} 
} 
 
// 查找最小元素节点 
func (bst *ItemBinarySearchTree) Min() *Item { 
	bst.lock.RLock() 
	defer bst.lock.RUnlock() 
	n := bst.root 
	if n == nil { 
		return nil 
	} 
	for { 
		if n.left == nil { 
			return &n.value 
		} 
		n = n.left 
	} 
} 
 
// 查找最大元素节点 
func (bst *ItemBinarySearchTree) Max() *Item { 
	bst.lock.RLock() 
	defer bst.lock.RUnlock() 
	n := bst.root 
	if n == nil { 
		return nil 
	} 
	for { 
		if n.right == nil { 
			return &n.value 
		} 
		n = n.right 
	} 
} 
 
// 搜索指定key的节点 
func (bst *ItemBinarySearchTree) Search(key int) bool { 
	bst.lock.RLock() 
	defer bst.lock.RUnlock() 
	return search(bst.root, key) 
} 
 
// internal recursive function to search an item in the tree 
func search(n *Node, key int) bool { 
	if n == nil { 
		return false 
	} 
	if key < n.key { 
		return search(n.left, key) 
	} 
	if key > n.key { 
		return search(n.right, key) 
	} 
	return true 
} 
 
// 删除指定key的节点 
func (bst *ItemBinarySearchTree) Remove(key int) { 
	bst.lock.Lock() 
	defer bst.lock.Unlock() 
	remove(bst.root, key) 
} 
 
// internal recursive function to remove an item 
func remove(node *Node, key int) *Node { 
	if node == nil { 
		return nil 
	} 
	if key < node.key { 
		node.left = remove(node.left, key) 
		return node 
	} 
	if key > node.key { 
		node.right = remove(node.right, key) 
		return node 
	} 
	// key == node.key 
	if node.left == nil && node.right == nil { 
		node = nil 
		return nil 
	} 
	if node.left == nil { 
		node = node.right 
		return node 
	} 
	if node.right == nil { 
		node = node.left 
		return node 
	} 
	minRightNode := node.right 
	for  minRightNode.left != nil { 
		//find smallest value on the right side 
		minRightNode = minRightNode.left 
	} 
	node.key, node.value = minRightNode.key, minRightNode.value 
	node.right = remove(node.right, node.key) 
 
	return node 
} 
 
// 以字符串方式打印树 
func (bst *ItemBinarySearchTree) String() { 
	bst.lock.Lock() 
	defer bst.lock.Unlock() 
	fmt.Println("------------------------------------------------") 
	stringify(bst.root, 0) 
	fmt.Println("------------------------------------------------") 
} 
 
// internal recursive function to print a tree 
func stringify(n *Node, level int) { 
	if n != nil { 
		format := "" 
		for i := 0; i < level; i++ { 
			format += "       " 
		} 
		format += "---[ " 
		level++ 
		stringify(n.right, level) 
		fmt.Printf(format+"%d\n", n.key) 
		stringify(n.left, level) 
	} 
}

3. 测试

package tree 
 
import ( 
	"fmt" 
	"testing" 
) 
 
var bst ItemBinarySearchTree 
 
func fillTree(bst *ItemBinarySearchTree) { 
	bst.Insert(8, "8") 
	bst.Insert(4, "4") 
	bst.Insert(10, "10") 
	bst.Insert(2, "2") 
	bst.Insert(6, "6") 
	bst.Insert(1, "1") 
	bst.Insert(3, "3") 
	bst.Insert(5, "5") 
	bst.Insert(7, "7") 
	bst.Insert(9, "9") 
} 
 
func TestInsert(t *testing.T) { 
	fillTree(&bst) 
	bst.String() 
 
	bst.Insert(11, "11") 
	bst.String() 
} 
 
func TestRemove(t *testing.T) { 
	fillTree(&bst) 
	bst.String() 
 
	bst.Remove(4) 
	bst.String() 
}

当然我们可以利用genny生成具体类型。

genny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int"

4. 总结

本文实现了Golang版本的二叉搜索树。删除操作相对复杂，这里只实现了右侧最小节点，读者还可以尝试左边最大节点。


本文参考链接：https://blog.csdn.net/neweastsun/article/details/107747361
  文章来源：
  https://www.itguest.com/post/aeag2b1.html
阅读延展