数据结构：树（Tree）

树的定义

 一棵树（tree）是一些节点的集合。这个集合可以是空集；若不是空集，则树由称作根（root）的节点r以及0个或多个非空的（子）树T1，T2,.....Tk组成，这些子树中每一棵的根都被来自根r的一条有有向的边（edge）所连结。

一般的树.png 一棵树.png

树的结构体：

type TreeNode struct {
 element interface{},
 firstChild *TreeNode,    // 儿子
 nextSibling *TreeNode, // 兄弟
}

二叉树

 二叉树是一棵树，其中每个节点都不能有多于两个的儿子。

二叉树的结构体：

// BinaryNode 二叉树节点
type BinaryNode struct {
    element        int
    leftChildNode  *BinaryNode
    rightChildNode *BinaryNode
}

// BinaryTree 二叉书
type BinaryTree struct {
    root *BinaryNode
}

// inorderTraversal 中序遍历
func inorderTraversal(root *BinaryNode) {
    if root == nil {
        return
    }
    inorderTraversal(root.leftChildNode)
    fmt.Println(root.element)
    inorderTraversal(root.rightChildNode)

}

// prefixraversal 前序遍历
func prefixraversal(root *BinaryNode) {
    if root == nil {
        return
    }
    fmt.Println(root.element)
    prefixraversal(root.leftChildNode)
    prefixraversal(root.rightChildNode)

}

// prefixravel 前序遍历非递归
func prefixravel(root *BinaryNode) {
    if root == nil {
        return
    }
    p := root
    stack := new(Stack)
    stack.push(p)

    for {
        if len(stack.Elements) == 0 {
            break
        }
        p = stack.pop()
        if p.rightChildNode != nil {
            stack.push(p.rightChildNode)
        }
        if p.leftChildNode != nil {
            stack.push(p.leftChildNode)
        }
    }
}

// inordertravel 中序遍历
func inordertravel(root *BinaryNode) {
    if root == nil {
        return
    }
    p := root
    stack := new(Stack)
    for {
        for {
            if p != nil {
                stack.push(p)
                p = p.leftChildNode
            } else {
                break
            }
        }
        p = stack.pop()
        if p.rightChildNode != nil {
            p = p.rightChildNode
        } else {
            p = nil
        }
        if len(stack.Elements) == 0 {
            break
        }
    }
}

// postOrder 后序遍历
func postOrder(root *BinaryNode) {
    if root == nil {
        return
    }
    p := root
    stack := new(Stack)
    for {
        for {
            if p != nil {
                stack.push(p)
                p = p.leftChildNode
            } else {
                break
            }
        }
        p = stack.pop()
        if len(stack.Elements) == 0 {
            break
        }
        //这里需要判断一下，当前p是否为栈顶的左子树，如果是的话那么还需要先访问右子树才能访问根节点
        //如果已经是不是左子树的话，那么说明左右子书都已经访问完毕，可以访问根节点了，所以讲p复制为NULL
        //取根节点
        if p == stack.peek().leftChildNode {
            p = stack.peek().rightChildNode
        } else {
            p = nil
        }
    }
}

二叉树非递归遍历：https://blog.csdn.net/ryjflyshy/article/details/78250348