二叉查找树的非递归遍历

佚名 5年前 (2018-12-19) 算法 1118人围观抢沙发百度已收录

　　前几天偶然看到一个经典的算法问题，是二叉树的非递归后序遍历，只允许用一个栈。

　　于是想了一想，写了一个版本，但是逻辑有误，无法完成预定目标。抓耳挠腮之际，上网百度了一下，看到有朋友用LinkedList的addFirst方法很好地解决了这个问题，给了我很好的启发从而写出了自己方法。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　二叉树的遍历，用递归是非常简单易懂，逻辑关系很明显，而非递归的方法就会更加微妙艰深一些。而后序遍历，要求我们在后序遍历了左子树和右子树之后，再考察当前结点。用非递归的思想方法是，将当前节点从栈中取出，将它的键值存入LinkedList的首位，再把当前节点的left和right依次压入栈，之后再取出，重复这个过程直到栈空。这样一来，我们先添加到list中的key反而排在了后面，这样恰好符合我们后序遍历的要求。当然，不用LinkedList也能够做到，我们维护一个与二叉树size相同的数组和一个指向下一个要填入的数组索引指针（借用概念），同样能够获得后序遍历。

　　下面贴出代码：

public List<Key> postOrderNonRecursively(){
        Stack<Node> stack = new Stack<>();　　　　//用到的栈
        LinkedList<Key> list = new LinkedList<>();
　　　　 if(root == null)   return list;   　　　　//root is the root node of this tree
        stack.push(root);　　　　　　　　　　　　　　//初始化栈
        while (!stack.empty()){　　　　　　　　　　//loop goes on as long as stack is not empty
            Node n = stack.pop();
            list.addFirst(n.key);
            if (n.left != null)     stack.push(n.left);　　　　//push left first, that means right goes out first and satisfy our requirement
            if (n.right != null)    stack.push(n.right);
        }
        return list;
    }

　　类似地，我们可以完成中序和前序的非递归方法。

public Key[] PreOrderNonrecursively(){
        Stack<Node> stack = new Stack<>();
        int point = 0;
        Key[] array =(Key[]) new Comparable[size()];
        stack.push(root);
        while (!stack.empty()){
            Node n = stack.pop();
            if (n == null)      continue;
            array[point++] = n.key;　　　　　　　　　　　　　　//each time we handle a node, its left and right children must be pushed
            if (n.right != null)    stack.push(n.right);
            if (n.left != null)     stack.push(n.left);
        }
        return array;
    }


    public List<Key> InOrderNonrecursively(){
        Stack<Node> stack = new Stack<>();
        ArrayList<Key> list = new ArrayList<>();
        stack.push(root);
        while (!stack.empty()){
            Node n = stack.peek();　　　　　　//do not pop directly because we must handle its valid left child first
            if (n == null){
                stack.pop();
                continue;
            }
            if (n.left == null || list.contains(n.left.key)) {　　//if its left is null or is already added to the list, itself should be added, and then its right
                list.add(n.key);
                stack.pop();
                stack.push(n.right);
            }else
                stack.push(n.left);

        }
        return list;
    }