Go -- 实现二叉搜索树
2024-08-26 01:51:42
树: https://suanfa.herokuapp.com/3%E6%A0%91/binarytree/
数据结构
首先我们定义需要的数据结构。注意，TreeNode的左右节点都是*TreeNode type的，而树只有一个Root数据域，为*TreeNode type
type TreeNode struct {
Value int
Left *TreeNode
Right *TreeNode
}
type BinarySearchTree struct {
Root *TreeNode
}
Insert
向二叉搜索树中插入元素，首先要找到插入的位置，然后再插入。这里注意我们的实现方法为给TreeNode和BinarySearchTree这两个type添加方法。需要注意给type添加方法的方式，同时还要注意，如果你要改变方法调用者，则需要使用指针
func (tree BinarySearchTree) Insert (v int) {
tree.Root.Insert(v)
}
func (node *TreeNode) Insert (v int){
if v < node.Value {
if node.Left != nil{
node.Left.Insert(v)
}else{
node.Left = &TreeNode{v, nil, nil}
}
}else {
if node.Right != nil{
node.Right.Insert(v)
}else{
node.Right = &TreeNode{v, nil, nil}
}
}
}
遍历
树的遍历有前序，后序，中序等等。这里以中序为例。注意slice与slice指针的不同
func (tree BinarySearchTree) InOrder() []int{
var res []int
tree.Root.InOrder(&res)
return res
}
func (node *TreeNode) InOrder(result *[]int) {
if node.Left != nil{
node.Left.InOrder(result)
}
*result = append(*result, node.Value)
if node.Right != nil{
node.Right.InOrder(result)
}
}
最大最小值
func (tree BinarySearchTree) FindMin() int {
node := tree.Root
for {
if node.Left != nil {
node = node.Left
}else{
return node.Value
}
}
}
func (tree BinarySearchTree) FindMax() int {
node := tree.Root
for {
if node.Right != nil {
node = node.Right
}else{
return node.Value
}
}
}
查找
func (tree BinarySearchTree) Contains(v int) bool {
node := tree.Root
for {
if node == nil{
return false
}else if (node.Value == v) {
return true
}else if (node.Value > v){
node = node.Left
}else{
node = node.Right
}
}
}
最新文章
- nagios检测http
- linux自用命令
- easyui-window 关闭事件，只要关闭窗口就会触发
- Form onsubmit 事件 阻止表单提交（） 必须选中同意选项才可以提交
- 知识积累:CA详解
- 点击页面任何位置隐藏div
- 大理石在哪？（Where is the Marble？，UVa 10474）
- ANTLR3完全参考指南读书笔记[01]
- java爬虫实战
- UVA1292-----Strategic game-----树形DP解决树上的最小点覆盖问题
- sql server数据库查询同义词
- wpf的无边框窗体透明
- django-restframework之缓存系统
- oracle跨库连接查询
- 本地上传文件至服务器的技巧(linux文件压缩及解压文件)
- Scala学习(四)---映射和元组
- Day10 Python网络编程 Socket编程
- Java使用JDBC连接随意类型数据库（mysql oracle。。）
- vue项目修改favicon
- Tomcat7 调优及 JVM 参数优化