Java二叉树的遍历

利用递归和非递归实现二叉树的先序,中序,后序遍历以及使用队列实现二叉树的层次遍历

节点图.jpg

package swiftlc.com.btreetraverse;

import java.util.Deque;
import java.util.LinkedList;

public class BTreeTraverseTest {

    public static void main(String[] args) {
        BTreeNode node_d = new BTreeNode('d');
        BTreeNode node_e = new BTreeNode('e');
        BTreeNode node_b = new BTreeNode('b',node_d,node_e);
        BTreeNode node_f = new BTreeNode('f');
        BTreeNode node_c = new BTreeNode('c',node_f,null);
        BTreeNode node_a = new BTreeNode('a',node_b,node_c);

        //递归遍历
        System.out.println("递归遍历");
        pre_traserve_res(node_a);
        System.out.println();
        in_traserve_res(node_a);
        System.out.println();
        beh_traserve_res(node_a);
        System.out.println();
        
        
        //非递归遍历
        System.out.println("非递归遍历");
        pre_traserve(node_a);
        System.out.println();
        in_traserve(node_a);
        System.out.println();
        beh_traserve(node_a);
        System.out.println();
        

        //二叉树的层次遍历,借助队列来实现  A  B  C  D  E  F
        System.out.println("二叉树的层次遍历");
        level_traverse(node_a);
    }

    private static void level_traverse(BTreeNode node_a) {
        if (node_a == null)return;
        Deque<BTreeNode> queue = new LinkedList<BTreeNode>();
        BTreeNode pCur;
        queue.offer(node_a);
        while(!queue.isEmpty()) {
            pCur = queue.poll();
            System.out.print(pCur);
            if (pCur.pChildLeft!=null)
                queue.offer(pCur.pChildLeft);
            if (pCur.pChildRight!=null)
                queue.offer(pCur.pChildRight);
        }
    }

    private static void beh_traserve(BTreeNode node_a) {
        if (node_a==null)return;
        Deque<BTreeNode> stack = new LinkedList<BTreeNode>();
        BTreeNode pPre = null;
        BTreeNode pTop;
        stack.push(node_a);
        while(!stack.isEmpty()) {
            pTop = stack.peek();
            if (pTop.pChildLeft==null && pTop.pChildRight==null || (pPre!=null && (pPre==pTop.pChildLeft||pPre==pTop.pChildRight))) {
                System.out.print(pTop);
                pPre = pTop;
                stack.pop();
            }else {
                if (pTop.pChildRight!=null)
                    stack.push(pTop.pChildRight);
                if (pTop.pChildLeft!=null)
                    stack.push(pTop.pChildLeft);
            }
        }
    }

    private static void in_traserve(BTreeNode node_a) {
        BTreeNode pCur = node_a;
        Deque<BTreeNode> stack = new LinkedList<BTreeNode>();
        while (pCur !=null ||!stack.isEmpty()) {
            if (pCur!=null) {
                stack.push(pCur);
                pCur = pCur.pChildLeft;
            }
            while(pCur==null && !stack.isEmpty()) {
                BTreeNode pTop = stack.pop();
                System.out.print(pTop);
                pCur = pTop.pChildRight;
            }
        }
    }

    private static void pre_traserve(BTreeNode node_a) {
        BTreeNode pCur = node_a;
        Deque<BTreeNode> stack = new LinkedList<BTreeNode>();
        while(pCur!=null || !stack.isEmpty()) {
            if (pCur!=null) {
                System.out.print(pCur);
                stack.push(pCur);
                pCur =  pCur.pChildLeft;
            }
            while (pCur==null && !stack.isEmpty()) {
                BTreeNode pTop = stack.pop();
                pCur = pTop.pChildRight;
            }
        }
    }

    private static void beh_traserve_res(BTreeNode node_a) {
        if (node_a!=null) {
            beh_traserve_res(node_a.pChildLeft);
            beh_traserve_res(node_a.pChildRight);
            System.out.print(node_a);
        }
    }

    private static void in_traserve_res(BTreeNode node_a) {
        if (node_a!=null) {
            in_traserve_res(node_a.pChildLeft);
            System.out.print(node_a);
            in_traserve_res(node_a.pChildRight);
        }
    }

    private static void pre_traserve_res(BTreeNode node_a) {
        if (node_a!=null) {
            System.out.print(node_a);
            pre_traserve_res(node_a.pChildLeft);
            pre_traserve_res(node_a.pChildRight);
        }
    }

}


class BTreeNode
{
    char value;
    BTreeNode pChildLeft;
    BTreeNode pChildRight;
    public BTreeNode(char value) {
        super();
        this.value = value;
    }
    public BTreeNode(char value, BTreeNode pChildLeft, BTreeNode pChildRight) {
        super();
        this.value = value;
        this.pChildLeft = pChildLeft;
        this.pChildRight = pChildRight;
    }
    @Override
    public String toString() {
        return value + " ";
    }
}