二叉搜索树(BST)是一种极重要的数据结构，它由浅及深，覆盖了数据结构与算法中的许多问题。本文出于实践Go编程的目的，用Go实现BST，这里先做一个初步的实现，暂时不考虑树的平衡性，不实现删除树节点。
首先定义BST的结构，这里体现Go优越性的地方来了。由于Go对每一个基础数据类型都定义了一个初始零值，如int型为0，指针*TreeNode为nil，我们不用写繁杂的构造函数来生成新节点。
type TreeNode struct {
Left, Right *TreeNode
Key int
}
type Tree struct {
Root *TreeNode
Num int
}
func NewTree() (t *Tree) {
t = &Tree{}
return
}
BST由于其数据组织特性，大量的方法可以天然地使用递归实现。递归实现过于直观，这里就不重复了。递归函数都可以利用迭代实现，而且递归需要占用函数调用栈，一旦递归层数过多，容易出现栈溢出，因此，对于数据量多的输入，迭代实现才是可靠的。
首先用实现插入节点，插入节点要保证BST的节点顺序，Key(left) < Key(root) < Key(Right)。首先找到一个叶子节点，然后将新建节点链接在叶子节点上。
/*iterative insert new key into tree*/
func (t *Tree) Insert(val int) {
node := &TreeNode{Key: val}
if t.Root == nil {
t.Root = node
t.Num++
return
} //create root
//find the parent node to host new one
var cur, parent *TreeNode = t.Root, nil
for cur != nil {
parent = cur
if val < cur.Key {
cur = cur.Left
} else {
cur = cur.Right
}
}
//link the new node to the tree
if parent == nil {
panic("corrupt tree") //parent = node
} else if val < parent.Key {
parent.Left = node
} else if val > parent.Key {
parent.Right = node
}
t.Num++
}
对比一下插入节点的递归实现
/*recursively insert new key into tree*/
func (t *Tree) InsertRecur(val int) {
t.Root = insert(t.Root, val)
}
func insert(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Key: val}
}
if val < root.Key {
root.Left = insert(root.Left, val)
} else if val > root.Key {
root.Right = insert(root.Right, val)
}
return root
}
然后用迭代实现BST的几种遍历方法，中序遍历，前序遍历，后序遍历和按层遍历。
中序遍历输出的是顺序的键值数组，中序遍历利用一个栈来实现，从根节点开始，从上向下，依次将左子节点压入栈，直到左子节点为空。随后弹出栈顶，首先访问的节点为最左子节点。访问完根节点后，再将右子树按同样方式访问。
/*iterative in-order traversal*/
func (t *Tree) Inorder() (out []int) {
if t.Root == nil {
return
}
var stack []*TreeNode
curr := t.Root
for true {
for curr != nil {
stack = append(stack, curr)
curr = curr.Left
}
if len(stack) > 0 {
curr = stack[len(stack)-1]
stack = stack[:len(stack)-1]
out = append(out, curr.Key)
}
curr = curr.Right
if curr == nil && len(stack) == 0 {
break
}
}
return
}
前序遍历最先访问的是根节点，然后是左子树和右子树，因此可以用队列来实现。
/*iterative pre-order traversal*/
func (t *Tree) Preorder() (out []int) {
if t.Root == nil {
return
}
queue := []*TreeNode{t.Root}
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
out = append(out, curr.Key)
if curr.Left != nil {
queue = append(queue, curr.Left)
}
if curr.Right != nil {
queue = append(queue, curr.Right)
}
}
return
}
后序遍历的递归实现比前序和中序更复杂，可以用两个栈实现。在栈1中，将节点按照根->左->右的顺序压栈，同时将根压入栈2，最后将栈2推出，即为后序遍历结果。
/*iterative post-order traversal with two stacks*/
func (t *Tree) Postorder() (out []int) {
if t.Root == nil {
return
}
var stack1, stack2 []*TreeNode
stack1 = append(stack1, t.Root)
for len(stack1) > 0 {
curr := stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
stack2 = append(stack2, curr)
if curr.Left != nil {
stack1 = append(stack1, curr.Left)
}
if curr.Right != nil {
stack1 = append(stack1, curr.Right)
}
}
for len(stack2) > 0 {
curr := stack2[len(stack2)-1]
stack2 = stack2[:len(stack2)-1]
out = append(out, curr.Key)
}
return
}
层序遍历利用的是BFS，广度优先搜索。利用队列，每次访问完一层，同时将下一层的节点入队。
/*iterative level-order traversal with BFS*/
func (t *Tree) LevelOrder() (out [][]int) {
if t.Root == nil {
return
}
queue := []*TreeNode{t.Root}
level := 0
for len(queue) > 0 {
size := len(queue)
if size > 0 {
out = append(out, []int{})
} //allocate array to store next level
for ; size > 0; size-- {
curr := queue[0]
queue = queue[1:]
out[level] = append(out[level], curr.Key) //travers node of current level
//put next level nodes into queue
if curr.Left != nil {
queue = append(queue, curr.Left)
}
if curr.Right != nil {
queue = append(queue, curr.Right)
}
}
level++ //increase level
}
return
}
本文没有实现平衡搜索树，但是BST的平衡性对搜索效率的影响很大，这里实现方法来检测树的平衡性，并且利用重构BST来平衡。
/*get the height of tree in recursively manner*/
func getHeightRecur(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 1
}
return Max(getHeightRecur(root.Left), getHeightRecur(root.Right)) + 1
}
/*check if tree is balanced in recursively manner*/
func (t *Tree) IsBalancedRecur() bool {
if t.Root == nil {
return true
}
return Abs(getHeightRecur(t.Root.Left)-getHeightRecur(t.Root.Right)) < 1
}
/*create and link tree node for a balanced tree*/
func buildBalancedTree(keys []int, start, end int) (root *TreeNode) {
if start < end {
return
}
mid := start + (end-start)/2
root = &TreeNode{Key: keys[mid]}
root.Left = buildBalancedTree(keys, start, mid-1)
root.Right = buildBalancedTree(keys, mid+1, end)
return
}
/*rebuild the tree to make it balanced*/
func (t *Tree) MakeBalancedRecur() {
keys := t.Inorder()
t.Root = buildBalancedTree(keys, 0, len(keys)-1)
}
最后添加测试用例来进行检验
func TreeTest(n int) {
nums := []int{3, 4, 6, 2, 1, 5}
tree := NewTree()
for _, n := range nums {
tree.Insert(n)
}
//visit := tree.Inorder()
fmt.Println("#", n, "TreeTest", tree.Num)
fmt.Println("pre-order", tree.Preorder())
fmt.Println("in-order", tree.Inorder())
fmt.Println("post-order", tree.Postorder())
fmt.Println("level-order", tree.LevelOrder())
}
代码清单：
https://github.com/KevinACoder/Learning/blob/master/ds_go/kit/tree.go
网友评论