二叉树的基本运算2

「爱情、让人受尽委屈。」 2022-03-07 14:06 139阅读 0赞

这一篇是接上一篇文章[二叉树的基本运算][Link 1]

## 二叉树的遍历 ##

二叉树遍历分为三种：前序、中序、后序（**取决于根节点**）:

*  前序遍历：根结点 -> 左子树 -> 右子树
 *  中序遍历：左子树 -> 根结点 -> 右子树
 *  后序遍历：左子树 -> 右子树 -> 根结点

另外还有一种**层次遍历**，即每一层都从左向右遍历。  
譬如，对于下面的二叉树  
![14591414567288.jpg][]

前序遍历：abdefgc  
中序遍历：debgfac  
后序遍历：edgfbca  
层次遍历：abcdfeg

## 实现方法 ##

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用**栈**去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，**非递归后序遍历**实现起来相对来说要难一点

# 先序遍历（非递归） #

go实现

// 先序遍历，用栈实现
    func preOrderBinaryTree1(root *BinaryTreeNode) {
        if root == nil {
            return
        }
        stack := []*BinaryTreeNode{}
        top := -1
        stack = append(stack, root)
        top++
    
        for top >= 0 {
            item := stack[top]
            stack = stack[:top]
            top-- // 出栈
    
            fmt.Print(item.data)
            // 先放入右节点
            if item.rChild != nil {
                stack = append(stack, item.rChild)
                top++
            }
            if item.lChild != nil {
                stack = append(stack, item.lChild)
                top++
            }
        }
    }

## 中序遍历（非递归） ##

go实现

// 中序遍历，用栈实现
    func inOrderBinaryTree1(root *BinaryTreeNode) {
        if root == nil {
            return
        }
        stack := []*BinaryTreeNode{}
        top := -1
    
        for top >= 0 || root != nil {
            for root != nil {
                stack = append(stack, root)
                top++
                root = root.lChild
            }
            item := stack[top]
            stack = stack[:top]
            top-- // 出栈
    
            fmt.Print(item.data)
            if item.rChild != nil {
                root = item.rChild
            }
        }
    }

## 后序遍历 ##

// 后序遍历，用栈实现
    func postOrderBinaryTree1(root *BinaryTreeNode) {
        if root == nil {
            return
        }
        stack := []*BinaryTreeNode{}
        top := -1
        var p *BinaryTreeNode = nil
        flag := -1
    
        for root != nil {
            stack = append(stack, root)
            top++
            root = root.lChild
        }
        flag = 1
        p = nil
    
        for top != -1 && flag > 0 {
            root = stack[top] // 取栈顶元素
            if root.rChild == p {
                fmt.Print(root.data)
                stack = stack[:top]
                top-- // 出栈
                p = root
            } else {
                root = root.rChild
                flag = 0
            }
        }
    
        for top != -1 {
            for root != nil {
                stack = append(stack, root)
                top++
                root = root.lChild
            }
            flag = 1
            p = nil
    
            for top != -1 && flag > 0 {
                root = stack[top] // 取栈顶元素
                if root.rChild == p {
                    fmt.Print(root.data)
                    stack = stack[:top]
                    top-- // 出栈
                    p = root
                } else {
                    root = root.rChild
                    flag = 0
                }
            }
        }
    }

[Link 1]: https://segmentfault.com/a/1190000009957891
[14591414567288.jpg]: /images/20220307/82c4e5cd265a49329d823445ec9f0125.png