在数据结构中,树的定义如下:
树(tree)是n(n≥0)个节点的有限集。当n=0时,称为空树。在任意一个非空树中,有如下特点:
1. 有且仅有一个特定的称为根的节点。
2. 当n>1时,其余节点可分为m(m>0)个互不相交的有限集,每一个集合本身又是一个树,并称为根的子树。
树的最大层级数,被称为书的高度或深度。
注意2个1个没有
二叉树的两个孩子节点,一个被称为左孩子,一个被称为右孩子。两个孩子节点的顺序是固定的,不能颠倒或混淆。
2.1 满二叉树
特点:
一个二叉树的所有非叶子节点都存在左右孩子。并且所有叶子节点都在同一层级上,那么这个树就是满二叉树。
深度【层级】n与节点数量的关系:且有2^n-1个结点。
2.2 完全二叉树
对于一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n。如果这个树的所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树。
换句话说:完全二叉树是比满二叉树少了一些叶子节点,且节点的位置完全与满二叉树节点的位置完全相同。
3.1 深度优先遍历
根节点
3.1.1 前序遍历
一
3.1.2 中序遍历
二
3.1.3 后序遍历
三
3.1.4 三种遍历的代码实现
基于链表的递归方式实现:
package main
import "fmt"
type Node struct {
Data int
Left *Node
Right *Node
}
//前序遍历
func PreOrder(node *Node) {
if node != nil {
fmt.Print(" ",node.Data)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
//中序遍历
func InOrder(node *Node) {
if node != nil {
InOrder(node.Left)
fmt.Print(" ",node.Data)
InOrder(node.Right)
}
}
//后序遍历
func PostOrder(node *Node) {
if node != nil {
PostOrder(node.Left)
PostOrder(node.Right)
fmt.Print(" ",node.Data)
}
}
func CreateTreeNode()*Node {//p80
node9 := &Node{
Data: 9,
Left: nil,
Right: nil,
}
node10 := &Node{
Data: 10,
Left: nil,
Right: nil,
}
node4:= &Node{
Data: 4,
Left: nil,
Right: nil,
}
node2 := &Node{
Data: 2,
Left: node9,
Right: node10,
}
node8 := &Node{
Data: 8,
Left: nil,
Right: node4,
}
node3 := &Node {
Data: 3,
Left: node2,
Right: node8,
}
return node3
}
func main() {
rootNode := CreateTreeNode()
PreOrder(rootNode)
fmt.Println()
InOrder(rootNode)
fmt.Println()
PostOrder(rootNode)
}
3.1.5 三种遍历的时间/空间复杂度
时间复杂度为O(n),同样空间复杂度也为O(n),n为结点数。
3.2 广度优先遍历【层序遍历】
3.2.1 层序遍历
是从根节点开始到叶子节点,一层一层从左到右遍历各个节点。一层遍历完再遍历下一层。
因为每一层各个节点直接没有直接的关联,所以需要借助队列来实现层序遍历。
步骤:
1、根节点先进入队列,然后根节点出队,在根节点出队后,若根节点有左孩子节点和右孩子结点,再将根节点的根节点有左孩子节点和右孩子结点放入队列。
2、重复循环1,知道左孩子节点和右孩子节点没有孩子节点位置。
3.2.2 代码实现
package main
import "fmt"
type Node struct {
Data int
Left *Node
Right *Node
}
//前序遍历
func PreOrder(node *Node) {
if node != nil {
fmt.Print(" ", node.Data)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
//中序遍历
func InOrder(node *Node) {
if node != nil {
InOrder(node.Left)
fmt.Print(" ", node.Data)
InOrder(node.Right)
}
}
//后序遍历
func PostOrder(node *Node) {
if node != nil {
PostOrder(node.Left)
PostOrder(node.Right)
fmt.Print(" ", node.Data)
}
}
//层序遍历
func LevelOrder(root *Node) [][]int {
var res [][]int
if root == nil {
return nil
}
queue := []*Node{root}
for len(queue) > 0 {
length := len(queue)
var layer []int //每层的输出结果
for i := 0; i < length; i++ {
if queue[0].Left != nil {
queue = append(queue, queue[0].Left)//相当于入队操作
}
if queue[0].Right != nil {
queue = append(queue, queue[0].Right)//相当于入队操作
}
layer = append(layer, queue[0].Data)
queue = queue[1:]//相当于出队操作,当把该节点的左右孩子放入队列中后就重新生成一个没有该节点的新切片,达到出队的目的
}
res = append(res, layer)
}
return res
}
func CreateTreeNode() *Node { //p80
node9 := &Node{
Data: 9,
Left: nil,
Right: nil,
}
node10 := &Node{
Data: 10,
Left: nil,
Right: nil,
}
node4 := &Node{
Data: 4,
Left: nil,
Right: nil,
}
node2 := &Node{
Data: 2,
Left: node9,
Right: node10,
}
node8 := &Node{
Data: 8,
Left: nil,
Right: node4,
}
node3 := &Node{
Data: 3,
Left: node2,
Right: node8,
}
return node3
}
func main() {
rootNode := CreateTreeNode()
//PreOrder(rootNode)
//fmt.Println()
//InOrder(rootNode)
//fmt.Println()
//PostOrder(rootNode)
//fmt.Println()
res := LevelOrder(rootNode)
for i := 0; i < len(res); i++ {
for j := 0; j < len(res[i]); j++ {
fmt.Print(" ", res[i][j])
}
}
}
3.2.3 层序遍历的时间/空间复杂度
时间复杂度:O(n)。