二叉树的非递归遍历三(后序/JAVA)

综合编程 简书

思路

二叉树的后序非递归遍历相对来说比前序和中序要难一点,那么原因何在呢?根据“左右根”的原则,众所周知,遍历的起点应该在最左端,然而并不一定是左子树的尽头,他还可能在最左端结点的右子树的最左端。所以我们的目标是想方设法到达这个遍历的起点。但与其这样去考虑,不如思考什么时候结点可以访问。所以一般有如下两种思路:

  1. 考虑结点右子树和左子树都不存在的情况下可以直接访问;右孩子为空左孩子刚被访问可以直接访问;右孩子不为空,右孩子刚被访问可以直接访问。其他情况依次将右孩子和左孩子圧入栈中(非空)。
  2. 另一种思路是直接法,先沿左子树向下搜索,并做入栈操作,当到达最左端时。取栈顶元素(非出栈)进行判断,若其右孩子不为空并且未被访问,则将其右孩子圧入栈中,沿其右孩子左子树继续向下搜索。当右孩子为空或者已经被访问,此时具有访问的资格了,出栈访问,并且做好记录,方便下次判断。

代码

第一种思路(条件法)

//从什么时候该访问的角度考虑
    public static void NotReCuPostOrder(BiTree T) {
        //栈初始化
        Stack S = new Stack();
        S.top = -1;
        S.nodes = new BiTree[100];
        BiTree p = T;
        if(p == null)
            return;
        BiTree r = null;//记录前一个被访问的结点
        S.nodes[++S.top] = p;
        while(S.top != -1) {
            p = S.nodes[S.top];//取栈顶元素作是否应该访问的判断
            if((p.lchild == null && p.rchild == null) || (p.rchild == null && p.lchild == r) || 
                    (p.rchild != null && p.rchild == r)) {
                p = S.nodes[S.top--];//出栈
                System.out.print(p.data+" ");//访问
                r = p;//记录
            } else {
                if(p.rchild != null) {
                    S.nodes[++S.top] = p.rchild;//右孩子入栈
                }
                if(p.lchild != null) {
                    S.nodes[++S.top] = p.lchild;//左孩子入栈
                }
            }
        }
    }

第二种思路(直接法)

//非递归后序遍历(直接法)
    public static void NotReCuPostOrder(BiTree T) {
        //栈初始化
        Stack S = new Stack();
        S.top = -1;
        S.nodes = new BiTree[100];
        BiTree p = T;
        BiTree r = null;//记录前一个被访问的结点
        //遍历
        while(p != null || S.top != -1) {
            if(p != null) {
                S.nodes[++S.top] = p;//入栈
                p = p.lchild;//沿左子树向下
            } else {
                p = S.nodes[S.top];//取栈顶元素而非出栈
                //若其右子树存在且没有访问过,则需继续压入栈中直到到达该结点右子树的最左端再判断
                if(p.rchild != null && p.rchild != r) {
                    p = p.rchild;
                    S.nodes[++S.top] = p;//入栈
                    p = p.lchild;//继续沿左子树搜索
                } else {
                    //右子树为空或者已经访问过,此时可以出栈访问
                    p = S.nodes[S.top--];//出栈
                    System.out.print(p.data+" ");//访问
                    r = p;//记录
                    p = null;//避免重复遍历
                }
            } 
        }
    }
简书稿源:简书 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合编程 » 二叉树的非递归遍历三(后序/JAVA)

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录