go语言实现二叉树

二叉树基本概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

二叉树创建

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)
}

二叉树遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

package main

import "fmt"

// 定义节点属性
type Node struct {
    item  int
    left *Node
    right *Node
} 

// 二叉树
type Tree struct {
    root *Node
}

// 层次遍历：即是广度优先方式搜索，使用队列方式实现
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")
}