数据结构基础 入门——二叉树

用Go来实现链表、栈、队列、散列表、树、二叉树、堆、图

树的认识

数据结构中借用自然界的树引申的叫法。不同的是 数据结构中的树是倒过来的 树根在上向下生长!

  • 节点:每个元素称为节点
  • 根节点 : 树的顶点(没有父元素的节点
  • 叶子节点:每个分支的末端节点(没有子元素的节点)

数据结构基础 入门——树

二叉树:最常见树结构,每个节点最多有两个子树的树结构

应用场景

  1. xml html 的解析器用到了树的解析
  2. 文件系统 树结构
  3. MySQL数据库索引 B+树。
  4. 路由协议
  5. 数据文件压缩
  6. 深度优先搜索算法 以及其他算法
  7. 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 协议》,转载必须注明作者和本文链接
滴水穿石,石破天惊----晓疯子
zhaocrazy
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!