go语言实现--二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1（百度百科）。

二叉树有多种：

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树，深度为k且有2k -1个节点。它是完全二叉树的一种。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

一般二叉树性质：
(1) 在非空二叉树中，第i层的结点总数不超过2i-1 (i>=1)；
(2) 深度为h的二叉树最多有2h -1个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；完全二叉树性质:
1. 具有n个节点的完全二叉树的高度k为[log2n]+1
2. 对于具有n个节点的完全二叉树,如果按照从上(根节点)到下(叶节点)和从左到右的顺序对二叉树中的所有节点从0开始到n-1进行编号,则对于任意的下标为k的节点，有：
• 如果k=0,则它是根节点，它没有父节点；如果k>0,则它的父节点的下标为[(i-1)/2];
• 如果2k+1 <= n-1,则下标为k的节点的左子结点的下标为2k+1;否则,下标为k的节点没有左子结点.
• 如果2k+2 <= n-1,则下标为k的节点的右子节点的下标为2k+2;否则,下标为k的节点没有右子节点

满二叉树性质:
在满二叉树中，叶节点的个数比分支节点的个数多1

二叉树遍历

1、前序遍历（与树的前序遍历一样）
基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。
图中前序遍历结果是：1，2，4，5，7，8，3，6
2、中序遍历
基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。
图中中序遍历结果是：4，2，7，8，5，1，3，6
3、后序遍历
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
图中后序遍历结果是：4，8，7，5，2，6，3，1
4、层次遍历（与树的层次遍历一样）
基本思想：从第一层开始，依此遍历每层，直到结束。
图中层次遍历结果是：1，2，3，4，5，6，7，8

例子：

对上图的二叉树做一个go语言实现，代码如下：

package main

import (
    "fmt"
)

//结点
type Node struct {
    Value       int
    Left, Right *Node
}

//打印结点值
func (node *Node) Print() {
    fmt.Print(node.Value, " ")
}

//设置结点值
func (node *Node) SetValue(value int) {
    if node == nil {
        fmt.Println("setting value to nil " +
            "node.Ignored.")
        return
    }
    node.Value = value
}

//前序遍历
func (node *Node) preOrder() {
    if node == nil {
        return
    }
    node.Print()
    node.Left.preOrder()
    node.Right.preOrder()
}

//中序遍历
func (node *Node) middleOrder() {
    if node == nil {
        return
    }
    node.Left.middleOrder()
    node.Print()
    node.Right.middleOrder()
}

//后序遍历
func (node *Node) postOrder() {
    if node == nil {
        return
    }
    node.Left.postOrder()
    node.Right.postOrder()
    node.Print()
}

//创建结点
func CreateNode(value int) *Node {
    return &Node{Value: value}
}

func main() {
    root := Node{Value: 3}
    root.Left = &Node{}
    root.Right = &Node{5, nil, nil}
    root.Right.Left = new(Node)
    root.Right.Left.SetValue(4)
    root.Left.Right = CreateNode(2)

    fmt.Print("前序遍历: ")
    root.preOrder()
    fmt.Println()
    fmt.Print("中序遍历: ")
    root.middleOrder()
    fmt.Println()
    fmt.Print("后序遍历: ")
    root.postOrder()
}

运行结果：