go实现和遍历二叉树

二叉树的实现：用来interface{}泛型

type TreeNode struct {
    Val   interface{}
    Left  *TreeNode
    Right *TreeNode
}

// 生成一颗二叉树，返回根节点的指针
func generateTree(order []interface{}) *TreeNode {
    // 假设是按照前序遍历来的
    if len(order) >= 2 {
        left_tree := generateTree(order[1 : len(order)/2+1])
        right_tree := generateTree(order[len(order)/2+1:])
        root := TreeNode{order[0], left_tree, right_tree}
        return &root
    } else {
        if len(order) == 0 {
            return nil
        }
        return &TreeNode{order[0], nil, nil}
    }
}


// 包括 nil 的前序遍历
// 生成一颗二叉树，返回根节点的指针
func generateTree(order []interface{}) *TreeNode {
    // 假设是按照前序遍历来的 包括 nil
    var build func() *TreeNode
    build = func() *TreeNode {
        if len(order) == 0 || order[0] == nil {
            order = order[1:]
            return nil
        }
        val := order[0]
        order = order[1:]
        return &TreeNode{val, build(), build()}
    }
    return build()
}

二叉树打印

var stringOfTree [][]string

func printTree(root *TreeNode) {
    getTreeString(root)
    for key, str := range stringOfTree {
        if key != len(stringOfTree)-1 {
            fmt.Print(" ")
        }
        for _, char := range str {
            fmt.Print(char)
            fmt.Print("\t")
        }
        fmt.Println()
    }
}

func getTreeString(root *TreeNode) [][]string {
    if root == nil {
        return nil
    }
    h := getHeight(root)
    w := pow(2, h) - 1
    stringOfTree = make([][]string, h)
    for k := range stringOfTree {
        s := make([]string, w)
        for key := range s {
            s[key] = ""
        }
        stringOfTree[k] = s
    }
    helper(root, 0, 0, w)
    return stringOfTree
}
func helper(root *TreeNode, level, l, r int) {
    if root != nil {
        mid := l + (r-l)/2
        // stringOfTree[level][mid] = strconv.Itoa(root.Val)
        stringOfTree[level][mid] = Strval(root.Val)
        helper(root.Left, level+1, l, mid-1)
        helper(root.Right, level+1, mid+1, r)
    }
}

func getHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    l := getHeight(root.Left)
    r := getHeight(root.Right)
    if l > r {
        return l + 1
    }
    return r + 1
}
func pow(x, y int) int {
    ret := x
    for i := 1; i < y; i++ {
        ret *= x
    }
    return ret
}

遍历

func traverse(node *TreeNode) {
    if node == nil {
        return
    }

    traverse(node.Left)
    traverse(node.Right)

    fmt.Printf("%v ", node.Val)
}

func iter_pre_order_traverse(node *TreeNode) {
    stack := list.New()
    var tmpNode *TreeNode
    tmpNode = node

    for tmpNode != nil || stack.Len() != 0 {
        for tmpNode != nil { // 不断将左节点入栈
            fmt.Printf("%v ", tmpNode.Val) // 访问当前tmpnode
            stack.PushBack(tmpNode)
            tmpNode = tmpNode.Left
        }
        if stack.Len() != 0 { // 没有左节点了 弹出栈顶 访问它的右节点
            tmpNode = stack.Remove(stack.Back()).(*TreeNode)
            tmpNode = tmpNode.Right
        }
    }
    fmt.Println()
}

func iter_in_order_traverse(node *TreeNode) {
    stack := list.New()
    var tmpNode *TreeNode
    tmpNode = node

    for tmpNode != nil || stack.Len() != 0 {
        for tmpNode != nil { // 不断将左节点入栈
            stack.PushBack(tmpNode)
            tmpNode = tmpNode.Left
        }
        if stack.Len() != 0 { // 没有左节点了 弹出栈顶 访问它的右节点
            tmpNode = stack.Remove(stack.Back()).(*TreeNode)
            fmt.Printf("%v ", tmpNode.Val) // 访问当前tmpnode
            tmpNode = tmpNode.Right
        }
    }
    fmt.Println()
}

func level_order_traverse(node *TreeNode) {
    stack := list.New()
    stack.PushBack(node)
    for stack.Len() != 0 {
        tmpNode := stack.Remove(stack.Front()).(*TreeNode)
        if tmpNode != nil {
            fmt.Printf("%v ", tmpNode.Val) // 访问当前tmpnode
            stack.PushBack(tmpNode.Left)
            stack.PushBack(tmpNode.Right)
        }
    }
    fmt.Println()
}

// 层序遍历生成二叉树
func generateTree(order []interface{}) *TreeNode {
    stack := list.New()
    res := TreeNode{order[0], nil, nil}
    stack.PushBack(&res)
    order = order[1:]
    for stack.Len() != 0 {
        root := stack.Remove(stack.Front()).(*TreeNode)
        if len(order) > 0 {
            if order[0] != nil {
                root.Left = &TreeNode{order[0], nil, nil}
                stack.PushBack(root.Left)
            }
            order = order[1:]
        }
        if len(order) > 0 {
            if order[0] != nil {
                root.Right = &TreeNode{order[0], nil, nil}
                stack.PushBack(root.Right)
            }
            order = order[1:]
        }
    }
    return &res
}