Go 中 BST 的实现方式

本篇文章为A Binary Search Tree的核心内容翻译,仅做个人学习之用。

原文在文章开头花了不少篇幅介绍查找、二叉树相关内容,本译文假定你具备一定的计算机基础,就不做过多介绍了。

Import and globals

在构建BST的结构时候,需要导入以下包,作用都很简单分别是提示Error,打印以及Log相关内容:

package main

import (
	"errors"
	"fmt"
	"log"
)

A Tree Node

按照之前的定义,一个树节点需要包含节点数值、左孩子节点、右孩子节点。树就是一种递归的数据结构,孩子节点也同样具备上述特性。在这个小实例中,每个树节点还包含一个简单的string值域。所以Node节点的定义如下所示:

type Node struct {
	Value string
	Data  string
	Left  *Node
	Right *Node
}

Insert

插入操作。首先要考虑树是否为nil,无法向nil树中插入数据。如果树不是nil,则由于二叉查找树的特性,即节点根据节点内的数值,是存在顺序的。所以新插入的节点,需要找到合适的位置。新插入的节点的值,需要跟树中节点的数值进行比较。

func (n *Node) Insert(value, data string) error {
	// 如果树为nil,则抛出异常
	if n == nil {
		return errors.New("Cannot insert a value into a nil tree")
	}

	switch {
      // 如果插入的数值在树中早已存在,返回
      case value == n.Value:
		return nil
      // 若插入的数值小于当前的value
      case value < n.Value:
		if n.Left == nil {
			n.Left = &Node{Value: value, Data: data}
			return nil
		}
		return n.Left.Insert(value, data)
      // 若插入的数值大于当前的value
      case value > n.Value:
		if n.Right == nil {
			n.Right = &Node{Value: value, Data: data}
			return nil
		}
		return n.Right.Insert(value, data)
	}
	return nil
}

如上代码所示,在与当前节点的value进行比较之后,分为以下情况:1:若新插入的节点值小于当前节点,按照BST的特性,应该往当前节点的左子树插入,此时要考虑当前节点的左孩子节点是否为nil,如果为nil,则直接将插入节点放置到当前节点的左孩子节点位置,如果当前节点的左孩子节点不是nil,则需要递归插入。2:若新插入的节点值大于当前节点,也是重复上述过程,道理是一样的。

Find

查找操作首先也要判断树是不是为nil,如果为nil就不必要进行后续的操作了。如果树不是nil,则接着比较,需要查找的value与当前的节点value值域进行比较。也是按照大于、小于、等于划分不同情况,根据需要决定是否进行递归查询。

func (n *Node) Find(s string) (string, bool) {
	if n == nil {
		return "", false
	}
	switch {
      case s == n.Value:
		return n.Data, true
      case s < n.Value:
		return n.Left.Find(s)
      default:
		return n.Right.Find(s)
	}
}
      

findMax

查找最大值。这个操作本身是有点麻烦,但是由于BST的特性,即数值的排列是有序递归的,所以最大值肯定是在右子树中,本质上也是一个递归查询的过程。递归的终止节点就是遇到了叶子节点。

func (n *Node) findMax(parent *Node) (*Node, *Node) {
	if n.Right == nil {
		return n, parent
	}
	return n.Right.findMax(n)
}

replaceNode

replaceNode用来替换,本身由parent指向n节点的指针,使得parent指向replacement节点。该种需求情况下,要求parent不能为nil节点。如果parent的左指针指向n,则将其改变成指向replacement节点即可,如果不是这种情况就用parent的右指针指向replacement节点。

func (n *Node) replaceNode(parent, replacement *Node) error {
	if n == nil {
		return errors.New("replaceNode() not allowed on a nil node")
	}

	if n == parent.Left {
		parent.Left = replacement
		return nil
	}
	parent.Right = replacement
	return nil
}

Delete

节点的删除操作。同样要求树不能为nil,即n节点不能为nil。删除操作同样是递归操作,要与当前节点比较。一旦匹配到要删除的节点,则需要考虑当前节点是存在左右孩子节点、只左孩子节点还是只存在右孩子节点。并且,需要知道当前要删除节点的父母节点。因为节点的删除,并不是简单的删除操作,还要去再次将树的节点给链接起来。

func (n *Node) Delete(s string, parent *Node) error {
  // 如果树为nil,抛出异常
	if n == nil {
		return errors.New("Value to be deleted does not exist in the tree")
	}
  switch {
    // value小于当前节点的数值
	case s < n.Value:
		return n.Left.Delete(s, n)
    // value大于当前节点的数值
	case s > n.Value:
		return n.Right.Delete(s, n)
    // value与当前节点的数值相等
	default:
        // 如果要删除的节点是叶子节点
    	if n.Left == nil && n.Right == nil {
			n.replaceNode(parent, nil)
			return nil
		}
        // 如果要删除的节点左孩子节点为nil
   	    if n.Left == nil {
			n.replaceNode(parent, n.Right)
			return nil
		}
         // 如果要删除的节点右孩子节点为nil
		if n.Right == nil {
			n.replaceNode(parent, n.Left)
			return nil
		}
         // 如果有两个孩子节点,在左子树中找出最大的值
    	replacement, replParent := n.Left.findMax(n)
        // 用replacement的数值替代n节点的值域
    	n.Value = replacement.Value
		n.Data = replacement.Data
        // 删除这个替代节点
    	return replacement.Delete(replacement.Value, replParent)
	}
}

Traverse

树的遍历操作。基本的遍历操作,从左至右,也就是传统的中序遍历。

func (t *Tree) Traverse(n *Node, f func(*Node)) {
	if n == nil {
		return
	}
	t.Traverse(n.Left, f)
    // 核心操作
	f(n)
	t.Traverse(n.Right, f)
}

如何去应用这个遍历方法呢?看下面的代码:

fmt.Print("Sorted values: | ")
// 匿名函数简化操作
tree.Traverse(tree.Root, func(n *Node) { fmt.Print(n.Value, ": ", n.Data, " | ") })
fmt.Println()

类似于上面这种调用还是很有意思的,代码量不多,简单清晰。

ok,以上内容就是Go中二叉查找树的实现方式!!!

欢迎添加我的微信与我交流