【java】代码实现：二叉树的先序遍历、中序遍历、后序遍历、层序遍历

一、节点类

public class Node {
    public Node left = null;
    public Node right = null;
    public int i;
    
    public Node(int i) {
        this.i = i;
    }
}

二、创建对象

public class NodeUtils {
	public static Node newNode(){
        Node node = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        Node n8 = new Node(8);
        Node n9 = new Node(9);
        Node n10 = new Node(10);
        node.left = n2;
        node.right = n3;
        n2.right = n4;
        n3.left = n5;
        n3.right = n6;
        n4.left = n7;
        n5.right = n8;
        n6.left = n9;
        n9.right= n10;
        return node;
	}
}

三、先序遍历（递归）

遍历规则：中左右
结果应该是：1、2、4、7、3、5、8、6、9、10

public class Main {
	public static void main(String[] args){
		List<Interger> list = new ArrayList<>();	// 存储结果
		Node node = NodeUtils.newNode();	// 获取 node 对象
		fun(node, list);	// 执行
        for (Integer i : list)
            System.out.println(i);	// 输出验证
	}

	public static void fun(Node node, List<Integer> list){
		list.add(node.i);
		if(node.left != null) fun(node.left, list);
		if(node.right != null) fun(node.right, list);
	}
}

四、中序遍历（递归）

遍历规则：左中右
结果应该是：2、7、4、1、5、8、3、9、10、6

public class Main {
	public static void main(String[] args){
		List<Interger> list = new ArrayList<>();	// 存储结果
		Node node = NodeUtils.newNode();	// 获取 node 对象
		fun(node, list);	// 执行
        for (Integer i : list)
            System.out.println(i);	// 输出验证
	}

	public static void fun(Node node, List<Integer> list){
		if(node.left != null) fun(node.left, list);
		list.add(node.i);
		if(node.right != null) fun(node.right, list);
	}
}

五、后序遍历（递归）

遍历规则：左右中
结果应该是：7、4、2、8、5、10、9、6、3、1

public class Main {
	public static void main(String[] args){
		List<Interger> list = new ArrayList<>();	// 存储结果
		Node node = NodeUtils.newNode();	// 获取 node 对象
		fun(node, list);	// 执行
        for (Integer i : list)
            System.out.println(i);	// 输出验证
	}

	public static void fun(Node node, List<Integer> list){
		if(node.left != null) fun(node.left, list);
		if(node.right != null) fun(node.right, list);
		list.add(node.i);
	}
}

六、层序遍历（队列）

遍历规则：一层一层
结果应该是：1、2、3、4、5、6、7、8、9、10

java:

public class Main {
	public static void main(String[] args) {
		Node node = NodeUtils.newNode();	// 获取 node 对象
		List<Interger> list = fun(node);	// 执行
        for (Integer i : list) {
            System.out.println(i);	// 输出验证
        }
	}

	public static List<Integer> fun(Node node){
		List<Integer> list = new ArrayList<>();
		if (node != null) {
		    Queue<Node> queue = new LinkedList<>();
			queue.add(node);
			do {
				Node first = queue.remove();
				list.add(first .i);
				if(first.left != null) queue.add(first.left);
				if(first.right != null) queue.add(first.right);
			} while(!queue.isEmpty());
		}
		return list;
	}
}

kotlin:

object Main {
  @JvmStatic
  fun main(arg: Array<String>) {
    val node = NodeUtils.newNode()
    process(node).forEach { println(it) }
  }

  fun process(node: Node?): List<Int> {
    node ?: return emptyList()
    val list = mutableListOf<Int>()
    val queue = LinkedList<>().apply { add(node) }
    do {
      queue.remove().apply {
        list.add(i)
        left?.let { queue.add(it) }
        right?.let { queue.add(it) }
      }
    } while(queue.isNotEmpty())
  }
}