Golang数据结构-树

二叉树

二叉树是n(n>=0)个节点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成

基本概念

• 度：节点拥有的子树数称为节点的度
• 叶子节点|终端节点：度为0的节点称为叶子节点或者终端节点
• 分支节点|非终端节点：度不为0的节点称为分支节点或者非终端节点，除根节点外，也称为内部节点
• 树的度：是树内各节点的度的最大值
• 孩子节点：节点的子树称为该节点的孩子节点
• 双亲节点：节点的子树的根称为双亲节点
• 兄弟节点：同一个双亲节点的孩子之间互称为兄弟节点
• 祖先：节点的祖先是从根到该节点所经分支上的所有节点
• 子孙：以某节点为根的子树中的任一节点都称为该节点的子孙
• 节点的层：根为第一层，根的孩子为第二层，若某节点在第i层，则其子树的节点就在第i+1层。
• 树的深度|高度：树中节点的最大层次称为树的深度或者高度。
• 有序树：如果将树中节点的各子树看成从左至右是右次序的。不能互换的，则称为树为有序树，反之为无序树
• 森林：是m棵互不相交的树的集合，对树中的每个节点而言，其子树的集合即为森林。

特点

• 每个节点最多有两棵子树。所以二叉树中不存在度大于3的节点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

形态

• 空二叉树
• 只有一个根节点的二叉树
• 根节点只有左子树
• 根节点只有右子树
• 根节点既有左子树又有右子树
• 斜树：所有节点都只有左子树的二叉树叫左斜树，只有右子树的称右斜树，统称斜树
• 满二叉树：在一棵二叉树中，所有分支节点都存在左、右子树，并且所有叶子都在同一层，称为满二叉树
• 完全二叉树：对一棵具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，称为完全二叉树。

存储

• 顺序存储结构：二叉树的顺序存储结构就是用一维数组存储二叉树中的节点。并且节点的存储位置也就是数组的下标要能体现节点之间的逻辑关系。一般只用于完全二叉树
• 二叉链表：二叉树每个节点最多有两个孩子，所有为它设计一个数据域和两个指针域。

type BinaryTree struct {
    Data        interface{}
    Left, Right *BinaryTree
}

遍历

• 前序遍历：规则是若二叉树为空，则返回空。否则先访问根节点，然后前序遍历左子树，在前序遍历右子树。（也可理解为每个节点的遍历：根-左-右）

    //递归-前序遍历
func (binaryTree *BinaryTree) PreOrderRecursion() []interface{} {
    result, tmpLeft, tmpRight := make([]interface{}, 0), make([]interface{}, 0), make([]interface{}, 0)
    if binaryTree == nil {
        return result
    }
    result = append(result, binaryTree.Data)
    if binaryTree.Left != nil {
        tmpLeft = binaryTree.Left.PreOrderRecursion()
        result = append(result, tmpLeft...)
    }
    if binaryTree.Right != nil {
        tmpRight = binaryTree.Right.PreOrderRecursion()
        result = append(result, tmpRight...)
    }
    return result
}

//非递归-前序遍历(根->左->右)
func (binaryTree *BinaryTree) PreOrder() []interface{} {
    btSlice := make([]*BinaryTree, 0)
    result := make([]interface{}, 0)
    if binaryTree == nil {
        return result
    }
    btSlice = append(btSlice, binaryTree)
    for len(btSlice) > 0 {
        curTreeNode := btSlice[len(btSlice)-1]
        btSlice = btSlice[:len(btSlice)-1]
        result = append(result, curTreeNode.Data)
        if curTreeNode.Right != nil {
            btSlice = append(btSlice, curTreeNode.Right)
        }
        if curTreeNode.Left != nil {
            btSlice = append(btSlice, curTreeNode.Left)
        }
    }
    return result
}
//返回结果：[1 2 4 5 3 6 7]

• 中序遍历:规则是若树为空，则返回空，否则从根节点开始（并不是先访问根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。（也可理解为每个节点的遍历：左-根-右）

//递归-中序遍历
func (binaryTree *BinaryTree) MiddleOrderRecursion() []interface{} {
    result, tmpLeft, tmpRight := make([]interface{}, 0), make([]interface{}, 0), make([]interface{}, 0)
    if binaryTree == nil {
        return result
    }
    if binaryTree.Left != nil {
        tmpLeft = binaryTree.Left.MiddleOrderRecursion()
        result = append(result, tmpLeft...)
    }
    result = append(result, binaryTree.Data)
    if binaryTree.Right != nil {
        tmpRight = binaryTree.Right.MiddleOrderRecursion()
        result = append(result, tmpRight...)
    }
    return result
}

//非递归-中序遍历(左-根-右)
func (binaryTree *BinaryTree) MiddleOrder() []interface{} {
    btSlice := make([]*BinaryTree, 0)
    result := make([]interface{}, 0)
    if binaryTree == nil {
        return result
    }
    curTreeNode := binaryTree
    for len(btSlice) > 0 || curTreeNode != nil {
        if curTreeNode != nil {
            btSlice = append(btSlice, curTreeNode)
            curTreeNode = curTreeNode.Left
        } else {
            tmp := btSlice[len(btSlice)-1]
            result = append(result, tmp.Data)
            btSlice = btSlice[:len(btSlice)-1]
            curTreeNode = tmp.Right
        }
    }
    return result
}
//返回结果：[4 2 5 1 6 3 7]

• 后序遍历:规则是若树为空，则返回空，否则从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。（也可理解每个节点的遍历：左-右-根）

//递归-后序遍历:
func (binaryTree *BinaryTree) AfterOrderRecursion() []interface{} {
    result, tmpLeft, tmpRight := make([]interface{}, 0), make([]interface{}, 0), make([]interface{}, 0)
    if binaryTree == nil {
        return result
    }
    if binaryTree.Left != nil {
        tmpLeft = binaryTree.Left.AfterOrderRecursion()
        result = append(result, tmpLeft...)
    }
    if binaryTree.Right != nil {
        tmpRight = binaryTree.Right.AfterOrderRecursion()
        result = append(result, tmpRight...)
    }
    result = append(result, binaryTree.Data)
    return result
}

//非递归-后序遍历
func (binaryTree *BinaryTree) AfterOrder() []interface{} {
    btSlice := make([]*BinaryTree, 0)
    tmpSlice := make([]*BinaryTree, 0)
    result := make([]interface{}, 0)

    if binaryTree == nil {
        return result
    }
    btSlice = append(btSlice, binaryTree)
    for len(btSlice) > 0 {
        curTreeNode := btSlice[len(btSlice)-1]
        btSlice = btSlice[:len(btSlice)-1]
        tmpSlice = append(tmpSlice, curTreeNode)
        if curTreeNode.Left != nil {
            btSlice = append(btSlice, curTreeNode.Left)
        }
        if curTreeNode.Right != nil {
            btSlice = append(btSlice, curTreeNode.Right)
        }
    }
    for len(tmpSlice) > 0 {
        curTmpSlice := tmpSlice[len(tmpSlice)-1]
        tmpSlice = tmpSlice[:len(tmpSlice)-1]
        result = append(result, curTmpSlice.Data)
    }
    return result
}

//返回结果：[4 5 2 6 7 3 1]

• 层序遍历:规则是若树为空，则返回空，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对节点逐个访问。

func (binaryTree *BinaryTree) LayersOrder() [][]interface{} {
    result := make([][]interface{}, 0)
    btSlice := make([]*BinaryTree, 0)
    if binaryTree == nil {
        return result
    }
    btSlice = append(btSlice, binaryTree)
    for len(btSlice) > 0 {
        currLevel := make([]interface{}, 0)
        allTreeNode := btSlice[:]
        btSlice = []*BinaryTree{}
        for _, node := range allTreeNode {
            currLevel = append(currLevel, node.Data)
            if node.Left != nil {
                btSlice = append(btSlice, node.Left)
            }
            if node.Right != nil {
                btSlice = append(btSlice, node.Right)
            }
        }
        result = append(result, currLevel)
    }
    return result;
}
//返回结果：[[1] [2 3] [4 5 6 7]]