Java实现二叉树前中后层遍历算法-数据结构和算法06

  最近在学习数据结构和算法，嗯，在看大话数据结构，边看边学习边总结一些东西把。记录下关键的节点
  实现二叉树前中后层排序算法，也是看到C的算法实现了，想着自己搞下java的把。

DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

看下书上实现的遍历算法：

是不是很简单。。嘿嘿。。后边的就不贴出来了。

先看结果：

1 2 4 8 9 5 3 6 7 前序遍历
8 4 9 2 5 1 6 3 7 中序遍历
8 9 4 5 2 6 7 3 1 后序遍历
1 2 3 4 5 6 7 8 9 层序遍历

package com.my.data.structure;

import java.util.LinkedList;


public class TreeSort {

    
    class TreeNode {
        TreeNode leftTree = null;
        TreeNode rightTree = null;
        int curValue;

        TreeNode(int v) {
            this.curValue = v;
        }

        public void printValue() {
            System.out.print(this.curValue + " ");
        }
    }

    
    public TreeNode createTree() {
        TreeNode[] treeNodes = new TreeNode[10];
        for (int i = 1; i < 10; i++) {
            treeNodes[i] = new TreeNode(i);
        }
        for (int i = 1; i < 5; i++) {
            int left = 2 * i;
            int right = 2 * i + 1;
            treeNodes[i].leftTree = treeNodes[left];
            treeNodes[i].rightTree = treeNodes[right];
        }
        return treeNodes[1];
    }

    
    public void preSort(TreeNode root) {
        if (root == null) return;
        root.printValue();
        preSort(root.leftTree);
        preSort(root.rightTree);
    }

    
    public void middleSort(TreeNode root) {
        if (root == null) return;
        middleSort(root.leftTree);
        root.printValue();
        middleSort(root.rightTree);
    }

    
    public void lastSort(TreeNode root) {
        if (root == null) return;
        lastSort(root.leftTree);
        lastSort(root.rightTree);
        root.printValue();
    }

    
    public void levelSort(TreeNode root) {
        if (root == null) return;
        LinkedList queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.pollFirst();
            root.printValue();
            if (root.leftTree != null) queue.add(root.leftTree);
            if (root.rightTree != null) queue.add(root.rightTree);
        }

    }

    public static void main(String[] args) {
        TreeSort treeSort = new TreeSort();
        TreeNode root = treeSort.createTree();

        treeSort.preSort(root);
        System.out.println("前序遍历");

        treeSort.middleSort(root);
        System.out.println("中序遍历");

        treeSort.lastSort(root);
        System.out.println("后序遍历");

        treeSort.levelSort(root);
        System.out.println("层序遍历");
    }
}