Java二叉树的四种遍历（递归与非递归）

Java二叉树的四种遍历（递归与非递归）

目录一、先序遍历与后序遍历二、中序遍历三、层序遍历

一、先序遍历与后序遍历

先序遍历根节点，再遍历左子树，再遍历右子树。

后序遍历先遍历左子树，再遍历右子树，再遍历根节点。

先序遍历递归实现：

public static void preOrderByRecursion(TreeNode root) {

// 打印节点值

System.out.println(root.value);

preOrder(root.left);

preOrder(root.right);

}

先序遍历的非递归实现：

非递归实现需要借助栈这样一个数据结构，实际上递归实现也是依靠栈，只不过是隐式的。

先将根节点压入栈中。

弹出栈中的节点，将弹出节点的右子节点压入栈中，再将弹出节点的左子树压入栈中。

重复步骤2，直到栈为空。

public static void preOrder(TreeNode root) {

if (root == null) {

return;

}

Stack stack = new Stack<>();

stack.push(root);

while (!stack.empty()) {

TreeNode node = stack.pop();

// 打印节点值

System.out.print(node.value + " ");

if (node.right != null) {

stack.push(node.right);

}

if (node.left != null) {

stack.push(node.left);

}

}

}

后序遍历递归实现：先序遍历反过来，就不赘述了。

public sthttp://atic void postOrderByRecursion(TreeNode root) {

postOrderByRecursion(root.left);

postOrderByRecursion(root.right);

System.out.println(root.value);

}

后序遍历非递归实现：后序遍历就是先序遍历反过来，所以需要两个栈，多出来的栈用来反向输出。

public static void postOrder(TreeNode root) {

if (root == null) {

return;

}

Stack s1 = new Stack<>();

Stack s2 = new Stack<>();

s1.push(root);

while (!s1.empty()) {

TreeNode node = s1.pop();

s2.push(node);

if (node.left != null) {

s1.push(node.left);

}

if (node.right != null) {

s1.push(node.right);

}

}

while (!s2.empty()) {

System.out.println(s2.pop().value);

}

}

二、中序遍历

中序遍历先遍历左子树，再遍历根节点，再遍历右子树。

递归遍历：

public static void inOrderByRecursion(TreeNode root) {

if (root == null) {

return;

}

inOrderByRecursion(root.left);

// 打印节点值

System.out.println(root.value);

inOrderByRecursion(root.right);

}

非递归遍历：

将二叉树的左侧“边”从上到下依次压入栈中。

从栈中弹出节点

对以弹出节点的右子节点为根节点的子树，重复步骤1。

重复2、3步骤，直到栈为空。

public static void inOrder(TreeNode root) {

if (root == null) {

return;

}

Stack stack = new Stack<>();

TreeNode cur = root;

while (cur != null) {

stack.push(cur);

cur = cur.left;

}

while (!stack.empty()) {

TreeNode node = stack.pop();

System.out.println(node.value);

cur = node.right;

while (cur != null) {

http://stack.push(cur);

cur = cur.left;

}

}

}

三、层序遍历

层序遍历顾名思义就是一层一层，从左到右的遍历二叉树。需要用到队列这一数据结构。

将根节点推入队列。

从队列中取出一个节点。

先将取出节点的左子节点推入队列，再将取出节点的右子节点推入队列。

重复2、3步骤直到队列中无节点可取。

public static void floorOrder(TreeNode root) {

if (root == null) {

return;

}

Queue queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

System.out.println(node.value);

if (node.left != null) {

queue.add(node.left);

}

if (node.right != null) {

queue.add(node.right);

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。