树与二叉树

树的基础概念

树的定义

树是 n (n≥0)个结点的有限集。当 n=0 时，称为空树。在任意一棵非空树中应满足:

有且仅有一个特定的称为根的结点.
当 n>1 时，其余结点可分为 m (m>0)个互不相交的有限集, 其中每个集合本身又是一棵树, 并且称为根的子树
.

树的性质

树具有如下最基本的性质:

树中的结点数等于所有结点的度数之和加 1
度为 m 的树中第 i 层上至多有 m-1 个结点(i≥1)
高度为 h 的 m 叉树至多有(m^h-1)/(m-1)个结点”
具有 n 个结点的 m 叉树的最小高度为[ log(n(m-1)+1)]

二叉树

二叉树的定义

二叉树是另一种树形结构, 其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点)，并且二又
树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是 n (n≥0)个结点的有限集合:

或者为空二叉树，即 n=0。
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树的存储结构

顺序存储

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素, 即将完
全二叉树上编号为 i 的结点元素存储在一维数组下标为 i-1 的分量中

依据二叉树的性质, 完全二叉树和满二叉树采用顺序存储比较合适, 树中结点的序号可以唯一地反映结点之间的逻
辑关系, 这样既能最大可能地节省存储空间, 又能利用数组元素的下标值确定结点在二叉树中的位置, 以及结点之
间的关系.

链式存储

由于顺序存储的空间利用率较低, 因此二叉树一般都采用链式存储结构, 用链表结点来存储二叉树中的每个结点.
在二叉树中, 结点结构通常包括若干数据域和若干指针域, 二叉链表至少包含 3 个域: 数据域 data、左指针域
lchild 和右指针域 rchild.

代码实现

二叉树基础, 就是实现二叉树的创建, 然后能够实现中序遍历、前序遍历、后序遍历的递归形式和迭代形式, 以及
层序遍历二叉树的方式.

type Node struct {
    data  interface{}
    left  *Node
    right *Node
}

// InitTree 创建一个二叉树节点
func InitTree() *Node {
    return &Node{}
}


// PreOrder 前序递归遍历二叉树
func (n *Node) PreOrder() {
    if n != nil {
        fmt.Print(n.data, " ")
        n.left.PreOrder()
        n.right.PreOrder()
    }
}

// InOrder 中序递归遍历二叉树
func (n *Node) InOrder() {
    if n != nil {
        n.left.InOrder()
        fmt.Print(n.data, " ")
        n.right.InOrder()
    }
}

// PostOrder 后序递归遍历二叉树
func (n *Node) PostOrder() {
    if n != nil {
        n.left.PostOrder()
        n.right.PostOrder()
        fmt.Print(n.data, " ")
    }
}

// ItPreOrder 非递归形式前序遍历
func (n *Node) ItPreOrder() []int {
    res := []int{}
    if n == nil {
        return res
    }
    var stack []*Node
    for cur := n; cur != nil || len(stack) != 0; {
        if cur != nil {
            res = append(res, cur.data.(int))
            stack = append(stack, cur)
            cur = cur.left
        } else {
            cur = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            cur = cur.right
        }
    }
    return res
}

// ItInOrder 非递归形式中序遍历
func (n *Node) ItInOrder() []int {
    res := []int{}
    if n == nil {
        return res
    }
    var stack []*Node
    for cur := n; cur != nil || len(stack) != 0; {
        if cur != nil {
            stack = append(stack, cur)
            cur = cur.left
        } else {
            cur = stack[len(stack)-1]
            res = append(res, cur.data.(int))
            stack = stack[:len(stack)-1]
            cur = cur.right
        }
    }
    return res
}

// ItPostOrder 非递归形式后序遍历
func (n *Node) ItPostOrder() []int {
    res := []int{}
    if n == nil {
        return res
    }
    stack := []*Node{}
    pre := &Node{}
    stack = append(stack, n)
    for len(stack) != 0 {
        cur := stack[len(stack)-1]
        if (cur.left == nil && cur.right == nil) || (pre != nil && (pre == cur.left || pre == cur.right)) {
            res = append(res, cur.data.(int))
            pre = cur
            stack = stack[:len(stack)-1]
        } else {
            if cur.right != nil {
                stack = append(stack, cur.right)
            }
            if cur.left != nil {
                stack = append(stack, cur.left)
            }
        }
    }
    return res
}

// 层序遍历二叉树
func (n *Node) LevelOrder() {
    queue := []*Node{n}
    for len(queue) != 0 {
        item := queue[0]
        fmt.Print(item.data, " ")
        queue = queue[1:]
        if item.left != nil {
            queue = append(queue, item.left)
        }
        if item.right != nil {
            queue = append(queue, item.right)
        }
    }
}

实现常用数据结构(二叉树)——二叉树基础