实现常用数据结构(二叉树)——线索化

线索化二叉树是对于遍历二叉树的进一步的改进.

通常我们遍历二叉树, 是将一个二叉树转化为线性结构. 而在我们遍历的过程中, 我们会发现经常需要回溯到父节点, 也就是走了重复的路. 因此不能像完全像线性结构一样, 而二叉树的线索化就是帮助我们找到每一个节点的前驱节点和后序节点, 这样我们就能像遍历线性结构一样遍历二叉树了.

因为深度优先遍历二叉树有三种形式, 分别为中序遍历、先序遍历、后序遍历, 所以对应的线索二叉树的方式也有三种.

中序线索化

// InThread 中序线索化二叉树
func (n *Node) InThread() {
    n.inThread(nil)
}

func (n *Node) inThread(pre *Node) {
    if n != nil {
        n.right.inThread(pre)
        if n.left == nil {
            n.left = pre
            n.lTag = true
        }
        if pre != nil && pre.right == nil {
            pre.right = n
            pre.rTag = true
        }
        n.left.inThread(n)
    }
}

前序线索化二叉树

// PreThread 前序线索化二叉树
func (n *Node) PreThread() {
    n.preThread(nil)
}

func (n *Node) preThread(pre *Node) {
    if n != nil {
        if n.left == nil {
            n.left = pre
            n.lTag = true
        }
        if pre != nil && pre.right == nil {
            pre.right = n
            pre.rTag = true
        }
        if !n.lTag {
            n.left.inThread(n)
        }
        if !n.rTag {
            n.right.inThread(n)
        }
    }
}

后序线索化二叉树

// PostThread 后序线索二叉树
func (n *Node) PostThread() {
    n.postThread(nil)
}

func (n *Node) postThread(pre *Node) {
    if n != nil {
        n.left.inThread(pre)
        n.right.inThread(pre)
        if n.left == nil {
            n.left = pre
            n.lTag = true
        }
        if pre != nil && pre.right == nil {
            pre.right = n
            pre.rTag = true
        }
    }
}