数据结构基础 入门——二叉树
用Go来实现链表、栈、队列、散列表、树、二叉树、堆、图
树的认识
数据结构中借用自然界的树引申的叫法。不同的是 数据结构中的树是倒过来的 树根在上向下生长!
- 节点:每个元素称为节点
- 根节点 : 树的顶点(没有父元素的节点
- 叶子节点:每个分支的末端节点(没有子元素的节点)
二叉树:最常见树结构,每个节点最多有两个子树的树结构
应用场景
- xml html 的解析器用到了树的解析
- 文件系统 树结构
- MySQL数据库索引 B+树。
- 路由协议
- 数据文件压缩
- 深度优先搜索算法 以及其他算法
- linux中进程的调度用的是红黑树
二叉树创建
package main
import "fmt"
// 定义节点属性
type Node struct {
item int
left *Node
right *Node
}
// 二叉树
type Tree struct {
root *Node
}
// 生成二叉树
func (tree *Tree) createTree(value int) {
node := &Node{item: value}
fmt.Println("增加节点", value)
if tree.root == nil {
tree.root = node
return
}else {
var queue []*Node = []*Node{tree.root}
for len(queue) != 0 {
cur := queue[0]
queue = queue[1:]
if cur.left == nil {
cur.left = node
return
}else if cur.right == nil {
cur.right = node
return
}else {
queue = append(queue, cur.left)
queue = append(queue, cur.right)
}
}
}
}
func main() {
var t Tree
t.createTree(2)
t.createTree(10)
t.createTree(3)
t.createTree(5)
}
go run xxx.go
增加节点 2
增加节点 10
增加节点 3
增加节点 5
二叉树遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次,我们把这种对所有节点的访问称为遍历(traversal)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归,广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
package main
import "fmt"
// 定义节点属性
type Node struct {
item int
left *Node
right *Node
}
// 二叉树
type Tree struct {
root *Node
}
// 生成二叉树
func (tree *Tree) createTree(value int) {
node := &Node{item: value}
fmt.Println("增加节点", value)
if tree.root == nil {
tree.root = node
return
} else {
var queue []*Node = []*Node{tree.root}
for len(queue) != 0 {
cur := queue[0]
queue = queue[1:]
if cur.left == nil {
cur.left = node
return
} else if cur.right == nil {
cur.right = node
return
} else {
queue = append(queue, cur.left)
queue = append(queue, cur.right)
}
}
}
}
// 层次遍历:即是广度优先方式搜索,使用队列方式实现
func (tree *Tree) selectTree() {
if tree.root == nil {
fmt.Println("not root")
return
}
var queue []*Node = []*Node{tree.root}
for len(queue) != 0 {
cur := queue[0]
queue = queue[1:]
fmt.Printf("%v ", cur.item)
if cur.left != nil {
queue = append(queue, cur.left)
}
if cur.right != nil {
queue = append(queue, cur.right)
}
}
}
// 先序遍历:即是深度优先方式搜索,使用递归方式实现
// 根节点 --> 左节点 --> 右节点
func (tree *Tree) selectFront(node *Node) {
if node == nil {
return
}
fmt.Printf("%v ", node.item)
tree.selectFront(node.left)
tree.selectFront(node.right)
}
// 中序遍历:即是深度优先方式搜索,使用递归方式实现
// 左节点 --> 根节点 --> 右节点
func (tree *Tree) selectMid(node *Node) {
if node == nil {
return
}
tree.selectMid(node.left)
fmt.Printf("%v ", node.item)
tree.selectMid(node.right)
}
// 后序遍历:即是深度优先方式搜索,使用递归方式实现
// 左节点 --> 右节点 --> 根节点
func (tree *Tree) selectBack(node *Node) {
if node == nil {
return
}
tree.selectBack(node.left)
tree.selectBack(node.right)
fmt.Printf("%v ", node.item)
}
func main() {
var t Tree
t.createTree(2)
t.createTree(10)
t.createTree(3)
t.createTree(5)
// 层次遍历
fmt.Println("层次遍历")
t.selectTree()
fmt.Printf("\n")
// 先序遍历
fmt.Println("先序遍历")
t.selectFront(t.root)
fmt.Printf("\n")
// 中序遍历
fmt.Println("中序遍历")
t.selectMid(t.root)
fmt.Printf("\n")
// 后序遍历
fmt.Println("后序遍历")
t.selectBack(t.root)
fmt.Printf("\n")
}
go run xxx.go
加节点 2
增加节点 10
增加节点 3
增加节点 5
层次遍历
2 10 3 5
先序遍历
2 10 5 3
中序遍历
5 10 2 3
后序遍历
5 10 3 2
参考资料:
www.jianshu.com/p/4b7a7348dbb7
laravelacademy.org/post/20971
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: