MyException - 我的异常网
当前位置:我的异常网» Go » Go 数据结构-二分查找树

Go 数据结构-二分查找树

www.MyException.Cn  网友分享于:2013-09-28  浏览:0次
Go 数据结构--二分查找树

Go 数据结构--二分查找树

今天开始一个Go实现常见数据结构的系列吧。有时间会更新其他数据结构。

一些概念

二叉树:二叉树是每个节点最多有两个子树的树结构。

完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树

满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

平衡二叉树:平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉查找树:它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树

二叉搜索树原理

二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树存储结构中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,O(log(n)).

实现

上述基本是百度百科的概念,现在来直接上实现代码:

/*
作者:陆恒
邮箱:luheng@chuchujie.com
时间:2017/8/24
功能:二叉树
*/

package main

import (
    "fmt"
    "sync"
)

//二叉树节点结构
type Node struct {
    data  int
    left  *Node
    right *Node
}

//二叉查找树结构
type BST struct {
    root *Node
    lock sync.RWMutex
}

//插入方法(判断位置 中序遍历)
func insertNode(node *Node, addNode *Node) {
    if addNode.data < node.data {
        if node.left == nil {
            node.left = addNode
        } else {
            insertNode(node.left, addNode)
        }
    } else {
        if node.right == nil {
            node.right = addNode
        } else {
            insertNode(node.right, addNode)
        }
    }
}

//插入操作
func (t *BST) Insert(data int) {
    t.lock.Lock()
    defer t.lock.Unlock()
    node := &Node{
        data:  data,
        left:  nil,
        right: nil,
    }
    if t.root == nil {
        t.root = node
    } else {
        insertNode(t.root, node)
    }
}

//先序遍历
func PreOrderTraverse(bst *Node) {
    if bst != nil {
        fmt.Printf("%d  ", bst.data)
        PreOrderTraverse(bst.left)
        PreOrderTraverse(bst.right)
    }
}

//中序遍历
func InOrderTraverse(bst *Node) {
    if bst != nil {
        InOrderTraverse(bst.left)
        fmt.Printf("%d  ", bst.data)
        InOrderTraverse(bst.right)
    }
}

//后序遍历
func PostOrderTraverse(bst *Node) {
    if bst != nil {
        PostOrderTraverse(bst.left)
        PostOrderTraverse(bst.right)
        fmt.Printf("%d  ", bst.data)
    }
}

//查找
func SearchBST(node *Node, key int) bool {
    if node == nil {
        return false
    }
    if key == node.data {
        return true
    }
    if key < node.data {
        return SearchBST(node.left, key)
    } else {
        return SearchBST(node.right, key)
    }
}

//删除执行函数
func remove(node *Node, key int) *Node {
    if node == nil {
        return nil
    }
    if key == node.data {
        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
        }
        rightside := node.right
        for {
            if rightside != nil && rightside.left != nil {
                rightside = rightside.left
            } else {
                break
            }
        }
        node.data = rightside.data
        node.right = remove(node.right, node.data)
        return node
    }
    if key < node.data {
        node.left = remove(node.left, key)
        return node
    } else {
        node.right = remove(node.right, key)
        return node
    }
}

//删除操作
func (t *BST) Remove(key int) {
    t.lock.Lock()
    defer t.lock.Unlock()
    remove(t.root, key)
}

func main() {
    var t BST
    t.Insert(2)
    t.Insert(6)
    t.Insert(5)
    t.Insert(1)
    t.Insert(10)
    t.Insert(8)

    fmt.Println("PREORDER...")
    PreOrderTraverse(t.root)
    fmt.Println("\nINORDER...")
    InOrderTraverse(t.root)
    fmt.Println("\nPOSTORDER...")
    PostOrderTraverse(t.root)
    fmt.Printf("\n")
    fmt.Println("Search...")
    fmt.Println(SearchBST(t.root, 6))
    fmt.Println("Remove...")
    t.Remove(6)
    fmt.Println("PREORDER...")
    PreOrderTraverse(t.root)
    fmt.Println("\nINORDER...")
    InOrderTraverse(t.root)
    fmt.Println("\nPOSTORDER...")
    PostOrderTraverse(t.root)
    fmt.Printf("\n")
    fmt.Println("Search...")
    fmt.Println(SearchBST(t.root, 6))
}

执行结果

PREORDER...
2   1   6   5   10  8   
INORDER...
1   2   5   6   8   10  
POSTORDER...
1   5   8   10  6   2   
Search...
true
Remove...
PREORDER...
2   1   8   5   10  
INORDER...
1   2   5   8   10  
POSTORDER...
1   5   10  8   2   
Search...
false

总结

照例得总结一波,其实每什么好总结的,大家都熟悉的数据结构。在增删查的复杂度比较均衡。拿来练手非常不错。

文章评论

10个调试和排错的小建议
10个调试和排错的小建议
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
每天工作4小时的程序员
每天工作4小时的程序员
我的丈夫是个程序员
我的丈夫是个程序员
那些争议最大的编程观点
那些争议最大的编程观点
如何成为一名黑客
如何成为一名黑客
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
老程序员的下场
老程序员的下场
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
编程语言是女人
编程语言是女人
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
Java程序员必看电影
Java程序员必看电影
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员必看的十大电影
程序员必看的十大电影
程序员应该关注的一些事儿
程序员应该关注的一些事儿
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我是如何打败拖延症的
我是如何打败拖延症的
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
鲜为人知的编程真相
鲜为人知的编程真相
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
 程序员的样子
程序员的样子
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
代码女神横空出世
代码女神横空出世
中美印日四国程序员比较
中美印日四国程序员比较
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有