二叉树前中后序算法

求下图前中后序

nodetree.png

数据模型构建

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        super();
        this.val = val;
        this.left = left;
        this.right = right;
    }

}

前中后序算法

/**
 *
 * ClassName：com.code.apache_poi.treeNode.TreePrinter <br>
 * Description：(二叉树算法)<br>
 * @author wangxiong <br>
 * date 2020/4/28 14:33<br>
 * @version v1.0 <br>
 *
 * 图片见：resources/TreeNode.webp
 */
public class TreePrinter {

    //树的结构的代码实现：
    public static void main(String[] args) {
        TreeNode g = new TreeNode(7);
        TreeNode d = new TreeNode(4,g,null);
        TreeNode e = new TreeNode(5);
        TreeNode b = new TreeNode(2,d,e);
        TreeNode h = new TreeNode(8);
        TreeNode a = new TreeNode(9);
        TreeNode f = new TreeNode(6,h,a);
        TreeNode c = new TreeNode(3,null,f);
        TreeNode root = new TreeNode(1,b,c);

        /* 测试后序 */
        printTree1 ( root );
        /* 测试中序 */
        printTree2 ( root );
        /* 测试前序 */
        printTree3 ( root );
    }


    /**
     * Title: printTree1<br>
     * Author: wangxiong<br>
     * Description: 中序：(先处理左子树，然后处理当前节点，再处理右子树。
     * 对于一颗二叉查找树，所有的信息都是有序排列的，中序遍历可以是信息有序输出，且运行时间为O（n）)<br>
     * Date:  14:21 <br>
     * @param t
     * return: void
     */
    public static void printTree1(TreeNode t){
        if(t!=null){
            printTree1(t.left);
            System.out.print("中序："+ t.val+" ");
            printTree1(t.right);
        }
    }

    /**
     * Title: printTree2<br>
     * Author: wangxiong<br>
     * Description: 后序： (先处理左右子树，然后再处理当前节点，运行时间为O（n）)<br>
     * Date:  14:19 <br>
     * @param t
     * return: void
     */
    public static void printTree2(TreeNode t){
        if(t!=null){
            printTree2(t.left);
            printTree2(t.right);
            System.out.print("后序："+t.val+" ");
        }
    }

    /**
     * Title: printTree3<br>
     * Author: wangxiong<br>
     * Description: 先序：(先处理当前节点，在处理左右子树)<br>
     * Date:  14:19 <br>
     * @param t
     * return: void
     */
    public static void printTree3(TreeNode t){
        if(t!=null){
            System.out.print("先序："+t.val+" ");
            printTree3(t.left);
            printTree3(t.right);
        }
    }

}

二叉树算法层序输出

/**
 *
 * ClassName：com.code.apache_poi.treeNode.TreePrinter1 <br>
 * Description：(二叉树算法层序输出)<br>
 * @author wangxiong <br>
 * date 2020/4/28 14:40<br>
 * @version v1.0 <br>
 */
public class TreePrinter1 {

    /**
     * Title: printTree<br>
     * Author: wangxiong<br>
     * Description: 层序：(层序遍历:所有深度为D的节点要在深度为D+1的节点之前进行处理，
     * 层序遍历与其他类型的遍历不同的地方在于它不是递归地执行的，它用到队列，而不使用递归所默示的栈。
     * 算法思想：
     * 1.定义节点 TreeNode lastNode指向当前行最有节点，TreeNode nlastNode指向下一行最右节点。
     * 2.利用队列，首先将根节点入队,再循环里出队,并将其子节点入队,定义TreeNode tmpNode节点指向当前出队列的节点，
     * 当tmpNode==lastNode时，代表当前行遍历结束，输出换行，
     * 再令lastNode=nlastNode，nlastNode在子节点入队列时指向下一行最右节点。
     * 循环直到对列为空就行)<br>
     * Date:  14:22 <br>
     * @param root
     * return: int[][]
     */
    public static int[][] printTree(TreeNode root) {
        List<List<Integer>> list = new ArrayList< List<Integer> >();
        list.add(new ArrayList<Integer> ());
        Queue<TreeNode> queue = new LinkedList<TreeNode> ();
        queue.add(root);
        TreeNode lastNode = root;    // 当前行最右节点
        TreeNode nlastNode = root;    // 下一行最右节点
        TreeNode tmpNode = null;
        int hight = 0;                // 树的高度
        while(!queue.isEmpty()){
            tmpNode = queue.poll();
            if(tmpNode!=null){
                list.get(hight).add(tmpNode.val);
            }
            if(tmpNode.left!=null){
                queue.add(tmpNode.left);
                nlastNode = tmpNode.left;
            }
            if(tmpNode.right!=null){
                queue.add(tmpNode.right);
                nlastNode = tmpNode.right;
            }
            if(tmpNode == lastNode){
                lastNode = nlastNode;
                hight++;
                list.add(new ArrayList<Integer>());
            }
        }
        int[][] data = new int[list.size()][];
        for(int i=0;i<list.size();i++){
            for(int j=0;j<list.get(i).size();j++){
                data[i][j] = list.get(i).get(j);
            }
        }

        return data;
    }
    public static void main(String[] args) {
        TreeNode e = new TreeNode(1);
        TreeNode g = new TreeNode(2);
        TreeNode h = new TreeNode(3);
        TreeNode i = new TreeNode(4);
        TreeNode d = new TreeNode(5,null,g);
        TreeNode f = new TreeNode(6,h,i);
        TreeNode b = new TreeNode(7,d,e);
        TreeNode c = new TreeNode(8,f,null);
        TreeNode root = new TreeNode(9,b,c);

        /* 测试层序 */
        int[][] data  =TreePrinter1.printTree(root);
        for(int s=0;s<data.length;s++){
            for(int j=0;j<data[s].length;j++){
                System.out.print(data[s][j]+" ");
            }
            System.out.println();
        }
    }
}