Go语言实现二叉搜索树

2018-04-26 本文已影响62人佛系博主

整理：张帅博客 : one8.one

基本概念介绍

树(tree) : 一种分层的数据结构，类比家谱
二叉搜索树（binary tree）： 左节点的值均小于有节点的二叉树
深度（depth）：从 root根结点到当前节点唯一路径的长度
高度（height）：从当前节点到一片树叶最长的路径的长度
根（root）：深度为0的树节点
内部节点（internal node）：至少有一个字节点的节点
树叶节点（leaf）：无字节点的节点
兄弟节点（sibling）：拥有相同父节点的字节点波、

1-1

应用

文件系统和数据库系统一般都采用树（特别是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 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） 8->4->2->1->3->6->5->7 >10->9- >11 （LRD）

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

1-2

String() 可视化树结构

1-3

代码实现

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中情况：

image

代码实现


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
    }

    mostLeftMode := node.right
// 要删除的节点有2个字节点，找到右子树的最左节点，替换当前节点 
    for {
    
    //一直遍历找到最左节点
        if mostLeftMode != nil && mostLeftMode.left != nil {
            mostLeftMode = mostLeftMode.left
        } else {
            break
        }

    }

// 使用右子树的最左节点替换当前的节点，即删除当前节点
    node.key, node.value = mostLeftMode.key,mostLeftMode.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，避开死循环。

Go语言实现二叉搜索树

基本概念介绍

应用

二叉树的常用操作

插入操作与遍历

代码实现

删除节点的流程

代码实现

总结

猜你喜欢

热点阅读