按照层次遍历顺序构造二叉树

构造二叉树时，默认二叉树是一颗满二叉树，数组的顺序则是满二叉树的层次遍历结果，其中’#‘代表空节点，以此来构造一颗二叉树。 

在数组中，一颗满二叉树节点对应的下标有这样的对应关系：

当根节点的数组下标是index时，则左节点对应的value是2 *index +1,右节点对应的value是2 * index +2,当创建好该根节点后，按照递归的方式依次创建对应的左子树和右子树；需注意其子节点对应的value如果超过数组下标，则表示为空节点；

举例子:

比如输入为：'A', 'B', 'E', 'C', '#', 'F', 'G', '#', 'D','#','#', '#', '#', 'I', 'H'构造的二叉树如下：

package main

import "fmt"

type BinaryTreeNode struct {
    val rune
    LeftNode *BinaryTreeNode
    RightNode *BinaryTreeNode
}


type BinaryTree struct {
    Root *BinaryTreeNode
}


// 按照指定输入构造一颗二叉树，'#'字符表示null节点
func ConstructBinaryTree(arr []rune) *BinaryTree {
    if len(arr) == 0 {
        return &BinaryTree{Root: nil}
    }
    head := createTreeDfs(arr, 0)
    return &BinaryTree{Root: head}
}

func createTreeDfs(arr []rune, rootIndex int) *BinaryTreeNode {
    if arr[rootIndex] == '#' {
        return nil
    }
    node := &BinaryTreeNode{
        val:       arr[rootIndex],
        LeftNode:  nil,
        RightNode: nil,
    }
    lIndex := 2 * rootIndex + 1
    rIndex := 2 *rootIndex + 2
    if lIndex > len(arr) -1 {
        node.LeftNode = nil
    }else {
        node.LeftNode = createTreeDfs(arr, lIndex)
    }
    if rIndex > len(arr) - 1 {
        node.RightNode = nil
    }else {
        node.RightNode = createTreeDfs(arr, rIndex)
    }
    return node
}


// 中序遍历
func middlePrint(root *BinaryTreeNode ) {
    if root == nil {
        return
    }
    middlePrint(root.LeftNode)
    fmt.Printf("%c", root.val)
    middlePrint(root.RightNode)
}


// 先序遍历
func prevPrint(root *BinaryTreeNode )  {
    if root == nil {
        return
    }
    fmt.Printf("%c", root.val)
    prevPrint(root.LeftNode)
    prevPrint(root.RightNode)
}

// 后序遍历
func postPrint(root *BinaryTreeNode )  {
    if root == nil {
        return
    }
    postPrint(root.LeftNode)
    postPrint(root.RightNode)
    fmt.Printf("%c", root.val)
}

func (tree *BinaryTree) MiddlePrint() {
    fmt.Println("it is a middle print")
    middlePrint(tree.Root)
    fmt.Println("\n")
}


func (tree *BinaryTree) PrevPrint() {
    fmt.Println("it is a prev print")
    prevPrint(tree.Root)
    fmt.Println("\n")
}

func (tree *BinaryTree) PostPrint() {
    fmt.Println("it is a post print")
    postPrint(tree.Root)
    fmt.Println("\n")
}

func (tree *BinaryTree) LevelPrint() {
    fmt.Println("it is a level print")
    root := tree.Root
    if root == nil {
        return
    }
    arr := []*BinaryTreeNode{}
    arr = append(arr, root)
    i := 0
    length := 1
    for i < length {
        node := arr[i]
        fmt.Printf("%c", node.val)
        i++
        if node.LeftNode != nil {
            arr = append(arr, node.LeftNode)
            length++
        }
        if node.RightNode != nil {
            arr = append(arr,  node.RightNode)
            length++
        }
    }
    fmt.Println("\n")
}



func main() {
    arr := []rune{'A', 'B', 'E', 'C', '#', 'F', 'G', '#', 'D','#','#', '#', '#', 'I', 'H'}
    tree := ConstructBinaryTree(arr)
    tree.PrevPrint()
    tree.MiddlePrint()
    tree.PostPrint()
    tree.LevelPrint()
    return
}

结果打印：

it is a prev print
ABCDEFGIH

it is a middle print
CDBAFEIGH

it is a post print
DCBFIHGEA

it is a level print
ABECFGDIH