扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 宝典简介

    • 数据结构和算法(Golang实现)
    • 前言
  • 简单入门Golang

  • 基础知识

  • 常见数据结构

    • 常见数据结构及算法
    • 链表
    • 可变长数组
    • 栈和队列
    • 列表
    • 字典
    • 树
  • 排序算法

  • 查找算法

  • 参考

扫码订阅《 》或入驻星球,即可阅读文章!

树


hunterhug

树是一种比较高级的基础数据结构,由 n 个有限节点组成的具有层次关系的集合。

树的定义:

  1. 有节点间的层次关系,分为父节点和子节点。
  2. 有唯一一个根节点,该根节点没有父节点。
  3. 除了根节点,每个节点有且只有一个父节点。
  4. 每一个节点本身以及它的后代也是一棵树,是一个递归的结构。
  5. 没有后代的节点称为叶子节点,没有节点的树称为空树。

二叉树:每个节点最多只有两个儿子节点的树。

满二叉树:叶子节点与叶子节点之间的高度差为 0 的二叉树,即整棵树是满的,树呈满三角形结构。在国外的定义,非叶子节点儿子都是满的树就是满二叉树。我们以国内为准。

完全二叉树:完全二叉树是由满二叉树而引出来的,设二叉树的深度为 k,除第 k 层外,其他各层的节点数都达到最大值,且第 k 层所有的节点都连续集中在最左边。

树根据儿子节点的多寡,有二叉树,三叉树,四叉树等,我们这里主要介绍二叉树。

# 一、二叉树的数学特征

  1. 高度为 h≥0 的二叉树至少有 h+1 个结点,比如最不平衡的二叉树就是退化的线性链表结构,所有的节点都只有左儿子节点,或者所有的节点都只有右儿子节点。
  2. 高度为 h≥0 的二叉树至多有 2^h+1 个节点,比如这棵树是满二叉树。
  3. 含有 n≥1 个结点的二叉树的高度至多为 n-1,由 1 退化的线性链表可以反推。
  4. 含有 n≥1 个结点的二叉树的高度至少为 logn,由 2 满二叉树可以反推。
  5. 在二叉树的第 i 层,至多有 2^(i-1) 个节点,比如该层是满的。

# 二、二叉树的实现

二叉树可以使用链表来实现。如下:

// 二叉树
type TreeNode struct {
	Data  string    // 节点用来存放数据
	Left  *TreeNode // 左子树
	Right *TreeNode // 右字树
}
1
2
3
4
5
6

当然,数组也可以用来表示二叉树,一般用来表示完全二叉树。

对于一棵有 n 个节点的完全二叉树,从上到下,从左到右进行序号编号,对于任一个节点,编号 i=0 表示树根节点,编号 i 的节点的左右儿子节点编号分别为:2i+1,2i+2,父亲节点编号为:i/2,整除操作去掉小数。

如图是一棵完全二叉树,数组的表示:

我们一般使用二叉树来实现查找的功能,所以树节点结构体里存放数据的 Data 字段。

# 三、遍历二叉树

构建一棵树后,我们希望遍历它,有四种遍历方法:

  1. 先序遍历:先访问根节点,再访问左子树,最后访问右子树。
  2. 后序遍历:先访问左子树,再访问右子树,最后访问根节点。
  3. 中序遍历:先访问左子树,再访问根节点,最后访问右子树。
  4. 层次遍历:每一层从左到右访问每一个节点。

先序,后序和中序遍历较简单,代码如下:

package main

import (
	"fmt"
)

// 二叉树
type TreeNode struct {
	Data  string    // 节点用来存放数据
	Left  *TreeNode // 左子树
	Right *TreeNode // 右字树
}

// 先序遍历
func PreOrder(tree *TreeNode) {
	if tree == nil {
		return
	}

	// 先打印根节点
	fmt.Print(tree.Data, " ")
	// 再打印左子树
	PreOrder(tree.Left)
	// 再打印右字树
	PreOrder(tree.Right)
}

// 中序遍历
func MidOrder(tree *TreeNode) {
	if tree == nil {
		return
	}

	// 先打印左子树
	MidOrder(tree.Left)
	// 再打印根节点
	fmt.Print(tree.Data, " ")
	// 再打印右字树
	MidOrder(tree.Right)
}

// 后序遍历
func PostOrder(tree *TreeNode) {
	if tree == nil {
		return
	}

	// 先打印左子树
	PostOrder(tree.Left)
	// 再打印右字树
	PostOrder(tree.Right)
	// 再打印根节点
	fmt.Print(tree.Data, " ")
}

func main() {
	t := &TreeNode{Data: "A"}
	t.Left = &TreeNode{Data: "B"}
	t.Right = &TreeNode{Data: "C"}
	t.Left.Left = &TreeNode{Data: "D"}
	t.Left.Right = &TreeNode{Data: "E"}
	t.Right.Left = &TreeNode{Data: "F"}

	fmt.Println("先序排序:")
	PreOrder(t)
	fmt.Println("\n中序排序:")
	MidOrder(t)
	fmt.Println("\n后序排序")
	PostOrder(t)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

表示将以下结构的树进行遍历:

结果如下:

先序排序:
A B D E C F 
中序排序:
D B E A F C 
后序排序
D E B F C A 
1
2
3
4
5
6

层次遍历较复杂,用到一种名叫广度遍历的方法,需要使用辅助的先进先出的队列。

  1. 先将树的根节点放入队列。
  2. 从队列里面 remove 出节点,先打印节点值,如果该节点有左子树节点,左子树入栈,如果有右子树节点,右子树入栈。
  3. 重复2,直到队列里面没有元素。

核心逻辑如下:

func LayerOrder(treeNode *TreeNode) {
	if treeNode == nil {
		return
	}

	// 新建队列
	queue := new(LinkQueue)
	// 根节点先入队
	queue.Add(treeNode)
	for queue.size > 0 {
		// 不断出队列
		element := queue.Remove()

		// 先打印节点值
		fmt.Print(element.Data, " ")

		// 左子树非空,入队列
		if element.Left != nil {
			queue.Add(element.Left)
		}

		// 右子树非空,入队列
		if element.Right != nil {
			queue.Add(element.Right)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

完整代码:

package main

import (
	"fmt"
	"sync"
)

// 二叉树
type TreeNode struct {
	Data  string    // 节点用来存放数据
	Left  *TreeNode // 左子树
	Right *TreeNode // 右字树
}

func LayerOrder(treeNode *TreeNode) {
	if treeNode == nil {
		return
	}

	// 新建队列
	queue := new(LinkQueue)

	// 根节点先入队
	queue.Add(treeNode)
	for queue.size > 0 {
		// 不断出队列
		element := queue.Remove()

		// 先打印节点值
		fmt.Print(element.Data, " ")

		// 左子树非空,入队列
		if element.Left != nil {
			queue.Add(element.Left)
		}

		// 右子树非空,入队列
		if element.Right != nil {
			queue.Add(element.Right)
		}
	}
}

// 链表节点
type LinkNode struct {
	Next  *LinkNode
	Value *TreeNode
}

// 链表队列,先进先出
type LinkQueue struct {
	root *LinkNode  // 链表起点
	size int        // 队列的元素数量
	lock sync.Mutex // 为了并发安全使用的锁
}

// 入队
func (queue *LinkQueue) Add(v *TreeNode) {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 如果栈顶为空,那么增加节点
	if queue.root == nil {
		queue.root = new(LinkNode)
		queue.root.Value = v
	} else {
		// 否则新元素插入链表的末尾
		// 新节点
		newNode := new(LinkNode)
		newNode.Value = v

		// 一直遍历到链表尾部
		nowNode := queue.root
		for nowNode.Next != nil {
			nowNode = nowNode.Next
		}

		// 新节点放在链表尾部
		nowNode.Next = newNode
	}

	// 队中元素数量+1
	queue.size = queue.size + 1
}

// 出队
func (queue *LinkQueue) Remove() *TreeNode {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 队中元素已空
	if queue.size == 0 {
		panic("over limit")
	}

	// 顶部元素要出队
	topNode := queue.root
	v := topNode.Value

	// 将顶部元素的后继链接链上
	queue.root = topNode.Next

	// 队中元素数量-1
	queue.size = queue.size - 1

	return v
}

// 队列中元素数量
func (queue *LinkQueue) Size() int {
	return queue.size
}

func main() {
	t := &TreeNode{Data: "A"}
	t.Left = &TreeNode{Data: "B"}
	t.Right = &TreeNode{Data: "C"}
	t.Left.Left = &TreeNode{Data: "D"}
	t.Left.Right = &TreeNode{Data: "E"}
	t.Right.Left = &TreeNode{Data: "F"}

	fmt.Println("\n层次排序")
	LayerOrder(t)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

输出:

层次排序
A B C D E F
1
2

赞赏支持

如果你觉得文章不错,请打个赏吧!

  • 一、二叉树的数学特征
  • 二、二叉树的实现
  • 三、遍历二叉树