（二）用go实现二叉查找树
2024-09-08 18:18:40
本篇，我们用go简单的实现二叉查找树。
1.节点定义
type BSNode struct{
data int
left, right, parent *BSNode
}
2.前序遍历
func (p *BSNode) PreTraverse() error{
if p.data == 0 {
return errors.New("Error: no data!")
}
fmt.Printf("%d ", p.data)
if p.left != nil {
p.left.PreTraverse()
}
if p.right != nil {
p.right.PreTraverse()
}
return nil
}
3.中序遍历
func (p *BSNode) InTraverse() error{
if p.data == 0 {
return errors.New("Error: no data!")
}
if p.left != nil {
p.left.InTraverse()
}
fmt.Printf("%d ", p.data)
if p.right != nil {
p.right.InTraverse()
}
return nil
}
4.后序遍历
func (p *BSNode) PostTraverse() error{
if p.data == 0 {
return errors.New("Error: no data!")
}
if p.left != nil {
p.left.PostTraverse()
}
if p.right != nil {
p.right.PostTraverse()
}
fmt.Printf("%d ", p.data)
return nil
}
5.添加节点
func (p *BSNode) Add(data int) error {
if data == 0 {
return errors.New("Error: not support 0 value!")
}
if p.data == 0 {
p.data = data
return nil
}
if p.data == data {
return errors.New("Error: add repeated data!")
} else if data < p.data {
if p.left == nil {
p.left = new(BSNode)
p.left.data = data
p.left.parent = p
return nil
}
p.left.Add(data)
} else {
if p.right == nil {
p.right = new(BSNode)
p.right.data = data
p.right.parent = p
return nil
}
p.right.Add(data)
}
return nil
}
6.删除节点
func (p *BSNode) Delete(data int) {
bsnode := p.Find(data)
if bsnode == nil {
return
}
if bsnode.left != nil {
var tmp *BSNode
for bsnode.left != nil {
bsnode.data = bsnode.left.data
tmp = bsnode
bsnode = bsnode.left
}
tmp.left = nil
return
}
if bsnode.right != nil {
var tmp *BSNode
for bsnode.right != nil {
bsnode.data = bsnode.right.data
tmp = bsnode
bsnode = bsnode.right
}
tmp.right = nil
return
}
if bsnode.parent != nil {
if bsnode.parent.left == bsnode {
bsnode.parent.left = nil
} else {
bsnode.parent.right = nil
}
}
}
7.查询节点
func (p *BSNode) Find(data int) *BSNode {
if p.data == data {
return p
} else if data < p.data {
if p.left != nil {
return p.left.Find(data)
}
return nil
} else {
if p.right != nil {
return p.right.Find(data)
}
return nil
}
}
8.测试代码
func main() {
num := []int{50, 20, 60, 40, 80, 10, 55, 52, 56}
var root *BSNode = new(BSNode)
for _, v := range num {
root.Add(v)
}
fmt.Println("前序遍历：")
root.PreTraverse()
fmt.Printf("\n")
fmt.Println("中序遍历：")
root.InTraverse()
fmt.Printf("\n")
fmt.Println("后序遍历：")
root.PostTraverse()
fmt.Printf("\n")
bsnode := root.Find(60)
if bsnode != nil {
fmt.Println("查询结果：")
fmt.Printf("节点：%d 父节点：%d 左子节点：%d 右子节点：%d\n", bsnode.data, bsnode.parent.data, bsnode.left.data, bsnode.right.data)
}
root.Delete(50)
fmt.Println("删除后前序遍历：")
root.PreTraverse()
fmt.Printf("\n")
}
9.完整代码
package main
import (
"fmt"
"errors"
)
type BSNode struct{
data int
left, right, parent *BSNode
}
// 前序遍历
func (p *BSNode) PreTraverse() error{
if p.data == 0 {
return errors.New("Error: no data!")
}
fmt.Printf("%d ", p.data)
if p.left != nil {
p.left.PreTraverse()
}
if p.right != nil {
p.right.PreTraverse()
}
return nil
}
// 中序遍历
func (p *BSNode) InTraverse() error{
if p.data == 0 {
return errors.New("Error: no data!")
}
if p.left != nil {
p.left.InTraverse()
}
fmt.Printf("%d ", p.data)
if p.right != nil {
p.right.InTraverse()
}
return nil
}
// 后序遍历
func (p *BSNode) PostTraverse() error{
if p.data == 0 {
return errors.New("Error: no data!")
}
if p.left != nil {
p.left.PostTraverse()
}
if p.right != nil {
p.right.PostTraverse()
}
fmt.Printf("%d ", p.data)
return nil
}
// 添加节点
func (p *BSNode) Add(data int) error {
if data == 0 {
return errors.New("Error: not support 0 value!")
}
if p.data == 0 {
p.data = data
return nil
}
if p.data == data {
return errors.New("Error: add repeated data!")
} else if data < p.data {
if p.left == nil {
p.left = new(BSNode)
p.left.data = data
p.left.parent = p
return nil
}
p.left.Add(data)
} else {
if p.right == nil {
p.right = new(BSNode)
p.right.data = data
p.right.parent = p
return nil
}
p.right.Add(data)
}
return nil
}
// 删除节点
func (p *BSNode) Delete(data int) {
bsnode := p.Find(data)
if bsnode == nil {
return
}
if bsnode.left != nil {
var tmp *BSNode
for bsnode.left != nil {
bsnode.data = bsnode.left.data
tmp = bsnode
bsnode = bsnode.left
}
tmp.left = nil
return
}
if bsnode.right != nil {
var tmp *BSNode
for bsnode.right != nil {
bsnode.data = bsnode.right.data
tmp = bsnode
bsnode = bsnode.right
}
tmp.right = nil
return
}
if bsnode.parent != nil {
if bsnode.parent.left == bsnode {
bsnode.parent.left = nil
} else {
bsnode.parent.right = nil
}
}
}
// 查询节点
func (p *BSNode) Find(data int) *BSNode {
if p.data == data {
return p
} else if data < p.data {
if p.left != nil {
return p.left.Find(data)
}
return nil
} else {
if p.right != nil {
return p.right.Find(data)
}
return nil
}
}
func main() {
num := []int{50, 20, 60, 40, 80, 10, 55, 52, 56}
var root *BSNode = new(BSNode)
for _, v := range num {
root.Add(v)
}
fmt.Println("前序遍历：")
root.PreTraverse()
fmt.Printf("\n")
fmt.Println("中序遍历：")
root.InTraverse()
fmt.Printf("\n")
fmt.Println("后序遍历：")
root.PostTraverse()
fmt.Printf("\n")
bsnode := root.Find(60)
if bsnode != nil {
fmt.Println("查询结果：")
fmt.Printf("节点：%d 父节点：%d 左子节点：%d 右子节点：%d\n", bsnode.data, bsnode.parent.data, bsnode.left.data, bsnode.right.data)
}
root.Delete(50)
fmt.Println("删除后前序遍历：")
root.PreTraverse()
fmt.Printf("\n")
}
最新文章
- UVALive 4329 Ping pong
- html总集
- Inside The C++ Object Model - 03
- HDU 1176免费馅饼 DP数塔问题转化
- 01.base-v1.js
- 从java到php
- TCP11种状态分析和测试
- operator[] 和 insert
- 手把手带你做一个超炫酷loading成功动画view Android自定义view
- 使用layer的弹窗时，出现layer引入成功，触发成功，控制台无报错，但是页面无变化或者仅出现遮罩层的问题的解决思路
- XML Linq 学习笔记
- vim 中文乱码怎么解决
- struts转发和重定向action
- 详述socket编程之select()和poll()函数
- python爬虫-基础
- 关于电机驱动扩展板 L293D 马达板Arduino
- DAVINCI开发原理
- ES6，先知道这些必会的才行
- VirtualBox如何增加CentOS根目录容量
- Wildcard Matching - LeetCode