ツリー非再帰ループアルゴリズム

16897 ワード

ツリー非再帰ループアルゴリズム
1.前段遍歴
    /**
     *               
     */
    @Override
    public void preOrderByStack() {
        System.out.print("       :");
        if (root==null){
            System.out.println("     !!!");
        }else {
            LinkedList<BinaryNode> list = new LinkedList<BinaryNode>();
            Queue<BinaryNode> stack = new LinkedList<>();
            BinaryNode current = root;
            while (current!=null || !stack.isEmpty()){
                while (current!=null){
                    list.add(current);
                    ((LinkedList<BinaryNode>) stack).push(current);
                    current = current.left;
                }
                if(!stack.isEmpty()){
                    current =((LinkedList<BinaryNode>) stack).pop();
                    current =current.right;
                }
            }

            for(BinaryNode binaryNode : list){
                System.out.print(binaryNode.value+" ");
            }
            System.out.println();
        }
    }

2.中順遍歴
    /**
     *         (   )      
     */
    @Override
    public void inOrderByStack() {
        System.out.print("       :");
        //   
        Deque<BinaryNode> stack = new LinkedList<BinaryNode>();
        BinaryNode current =root;
        while (current!=null || !stack.isEmpty()){
            while (current!=null){
                stack.push(current);
                current=current.left;
            }
            if(!stack.isEmpty()){
                current=stack.pop();
                System.out.print(current.value+" ");
                current=current.right;
            }
        }
        System.out.println();
    }

3.後段遍歴
    /**
     *                 
     */
    @Override
    public void postOrderByStack() {
        System.out.print("       :");
        ArrayList<BinaryNode> list = new ArrayList<BinaryNode>();
        if(root!=null){
            Deque<BinaryNode> stack = new LinkedList<>();
            stack.push(root);
            while (!stack.isEmpty()){
                BinaryNode current = stack.pop();
                list.add(0,current);
                if(current.left!=null){
                    stack.push(current.left);
                }
                if(current.right!=null){
                    stack.push(current.right);
                }
            }
            Iterator<BinaryNode> iterator  = list.iterator();
            while (iterator.hasNext()){
                System.out.print(iterator.next().value+" ");
            }
            System.out.println();
        }
    }