二叉树

发表于

在计算机科学中，二叉树是每个结点最多有两个子树的树结构

遍历

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历
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
package main
import (
    "fmt"
    "local/datastructure/base"
)
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func main() {
    fmt.Print("前序遍历:")
    preorder(generateTree())
    fmt.Println()
    fmt.Print("中序遍历:")
    midorder(generateTree())
    fmt.Println()
    fmt.Print("后序遍历:")
    tailorder(generateTree())
    fmt.Println()
    fmt.Print("层序遍历:")
    levelorder(generateTree())
}
//前序遍历(中间元素在前 中左右)
func preorder(node *TreeNode) {
    if node == nil {
        return
    }
    fmt.Printf("%d", node.Val)
    preorder(node.Left)
    preorder(node.Right)
}
//中序遍历
func midorder(node *TreeNode) {
    if node == nil {
        return
    }
    preorder(node.Left)
    fmt.Printf("%d", node.Val)
    preorder(node.Right)
}
//后序遍历
func tailorder(node *TreeNode) {
    if node == nil {
        return
    }
    preorder(node.Left)
    preorder(node.Right)
    fmt.Printf("%d", node.Val)
}
//层序遍历 (借助队列)
func levelorder(node *TreeNode) {
    queue := base.NewQueue()
    queue.Push(node)
    for !queue.IsEmpty() {
        item, err := queue.Pop()
        if err != nil {
            fmt.Println(err)
        }
        fmt.Print(item.(*TreeNode).Val)
        if item.(*TreeNode).Left != nil {
            queue.Push(item.(*TreeNode).Left)
        }
        if item.(*TreeNode).Right != nil {
            queue.Push(item.(*TreeNode).Right)
        }
    }
}
//构造tree
func generateTree() *TreeNode {
    n1 := &TreeNode{Val: 1, Right: nil, Left: nil}
    n2 := &TreeNode{Val: 2, Right: nil, Left: nil}
    n3 := &TreeNode{Val: 3, Right: nil, Left: nil}
    n1.Left = n2
    n1.Right = n3
    return n1
}