文章目录
1. 什么是二叉树?
2. 二叉树如何遍历?
3. 二叉树如何应用?
前言: 自己理论开发中用到的二叉树的场景很少,但为啥还是要学习二叉树呢?
答:自己开发教训只有几年工夫,教训不是很丰盛,没怎么在理论场景用过二叉树的开发,更多的是在刷 leecode 时,会频繁遇到二叉树的题目。但我晓得,随着一直的深刻学习,当前接触到一些底层原理时,必定离不开数据结构和算法,学习二叉树也是为了当前本人能迈向更高的台阶做铺垫。这里我用 go 语言作为例子解说(目前我只把握了 php 和 go,php 实现没那么不便,所以用 go),其余语言的的实现也相似, 只是根本的数据相似不同而已。
PS:有时候也能刚好用数据结构和算法去更好的了解一些货色. 比方 php 的 sort 函数的排序,点进去看其实底层的 c 代码是通过疾速排序和插入排序相互联合, 去给传入的数组进行排序的。当数组元素超过 16 个时应用疾速排序(工夫复杂度是 n *logN 的排序),小于等于 16 个时应用插入排序(工夫复杂度是 n2 的排序), 去实现最快的效率进行排序。还有 mysql 的索引是多路均衡树结构实现的,对树结构有基本概念,了解 mysql 索引时也能更加深刻。
好了废话少说间接进入正题。
1. 什么是二叉树?
二叉树(binary tree)是指树中节点的度不大于 2 的有序树,它是一种最简略且最重要的树。
间接上图就好了解了
就相似上图构造的一种数据后果,就是二叉树, 用代码实现就是
二叉树节点构造
// 定义二叉树节点
type Node struct {
data int //data 构造体的字段名 类型是 int 能够这样拜访 Node.data = 2
left *Node // left 构造体的字段名 类型是 Node 指针
right *Node // right 构造体的字段名 类型是 Node 指针
}
例子:
package main
func main() {
// 初始化
node1 := Node{1, nil, nil}
node2 := Node{2, nil, nil}
node3 := Node{3, nil, nil}
node1.left = &node2
node1.right = &node3
//node1 就是根结点,节点值是 1,node2 就是左结点, 节点值是 2,node3 就是右结点, 节点值是 3,}
2. 二叉树如何遍历?
有先序遍历(先遍历头节点,再遍历左节点,再遍历右节点, 艰深来说程序就是:头左右),中序遍历(程序:左头右),后序遍历(程序:左右头).
举例下图这么一颗二叉树
则程序为
代码实现为:
package main
import "fmt"
func main() {
// 初始化
node1 := Node{1, nil,nil}
node2 := Node{2, nil,nil}
node3 := Node{3, nil,nil}
node4 := Node{4, nil,nil}
node5 := Node{5, nil,nil}
node6 := Node{6, nil,nil}
node7 := Node{7, nil,nil}
node1.left = &node2
node1.right = &node3
node2.left = &node4
node2.right = &node5
node3.left = &node6
node3.right = &node7
Order(&node1)
}
// 定义二叉树节点
type Node struct {
data int
left *Node
right *Node
}
// 递归形式
func Order(head *Node) {
if head == nil {return}
//fmt.Println(head.data) 先序遍历 1245367
Order(head.left)
//fmt.Println(head.data) // 中序遍历 4251637
Order(head.right)
fmt.Println(head.data) // 后序遍历 4526731
}
3. 二叉树有什么类型呢?
有 4 种类型
1. 搜寻二叉树
2. 齐全二叉树
3. 满二叉树
4. 均衡二叉树
// 篇幅太长不好,留着下一篇文章解说。
心愿能对大家学习二叉树有一点帮忙。