二叉树遍历算法实验报告java_Java：二叉树的遍历算法实现

水深无声 2022-11-06 10:54 180阅读 0赞

// TreeNode.java

package tree;

public class TreeNode \{

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) \{

val = x;

// TreeTest.java

package tree;

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Queue;

import java.util.Stack;

public class TreeTest \{

public static TreeNode buildTree() \{

// 创建测试用的二叉树

TreeNode t1 = new TreeNode(1);

TreeNode t2 = new TreeNode(2);

TreeNode t3 = new TreeNode(3);

TreeNode t4 = new TreeNode(4);

TreeNode t5 = new TreeNode(5);

TreeNode t6 = new TreeNode(6);

TreeNode t7 = new TreeNode(7);

TreeNode t8 = new TreeNode(8);

t1.left = t2;

t1.right = t3;

t2.left = t4;

t4.right = t7;

t3.left = t5;

t3.right = t6;

t6.left = t8;

return t1;

public static void visit(TreeNode t) \{

System.out.print(t.val + " ");

public static void preOrderRecursion(TreeNode root) \{

// 先序遍历，递归实现

if(root == null) \{

return;

visit(root);

preOrderRecursion(root.left);

preOrderRecursion(root.right);

public static void midOrderRecursion(TreeNode root) \{

// 中序遍历，递归实现

if(root == null) \{

return;

midOrderRecursion(root.left);

visit(root);

midOrderRecursion(root.right);

public static void postOrderRecursion(TreeNode root) \{

// 后序遍历，递归实现

if(root == null) \{

return;

postOrderRecursion(root.left);

postOrderRecursion(root.right);

visit(root);

public static List preOrderStack(TreeNode root) \{

// 先序遍历，非递归实现

List res = new ArrayList<>();

Stack treeStack = new Stack<>();

if(root == null) \{

return res;

treeStack.push(root);

while(!treeStack.isEmpty()) \{

TreeNode tempNode = treeStack.pop();

res.add(tempNode.val);

if(tempNode.right != null) \{

// 右子树结点先压栈，保证了根，左，右的出栈顺序

treeStack.push(tempNode.right);

if(tempNode.left != null) \{

treeStack.push(tempNode.left);

return res;

public static List midOrderStack(TreeNode root) \{

// 中序遍历，非递归实现

List res = new ArrayList<>();

Stack s = new Stack<>();

if(root == null) \{

return res;

TreeNode cur = root;

while(cur != null || !s.isEmpty()) \{

while(cur != null) \{

s.push(cur);

cur = cur.left;

cur = s.pop();

res.add(cur.val);

cur = cur.right;

return res;

public static List postOrderStack1(TreeNode root) \{

// 后序遍历，非递归实现

List res = new ArrayList<>();

Stack s = new Stack<>();

Map m = new HashMap<>();

if(root == null) \{

return res;

s.push(root);

while(!s.isEmpty()) \{

TreeNode temp = s.peek();

if(temp.left == null && temp.right == null) \{

res.add(temp.val);

m.put(temp, true);

s.pop();

continue;

\} else if(!((temp.left != null && m.get(temp.left) == null) ||

(temp.right != null && m.get(temp.right) == null))) \{

res.add(temp.val);

m.put(temp, true);

s.pop();

continue;

if(temp.left != null) \{

while(temp.left != null && m.get(temp.left) == null) \{

s.push(temp.left);

temp = temp.left;

if(temp.right != null) \{

s.push(temp.right);

temp = temp.right;

return res;

public static List postOrderStack2(TreeNode root) \{

List res = new ArrayList<>();

Stack s = new Stack<>();

if(root == null) \{

return res;

s.push(root);

while(!s.isEmpty()) \{

TreeNode temp = s.pop();

res.add(temp.val);

if(temp.left != null) \{

s.push(temp.left);

if(temp.right != null) \{

s.push(temp.right);

Collections.reverse(res);

return res;

public static List levelOrder(TreeNode root) \{

// 层次遍历

List res = new ArrayList<>();

Queue q = new LinkedList<>();

if(root == null) \{

return res;

q.add(root);

while(!q.isEmpty()) \{

TreeNode temp = q.remove();

res.add(temp.val);

if(temp.left != null) \{

q.add(temp.left);

if(temp.right != null) \{

q.add(temp.right);

return res;

public static void main(String\[\] args) \{

TreeNode root = TreeTest.buildTree();

TreeTest.preOrderRecursion(root);

System.out.println();

TreeTest.midOrderRecursion(root);

System.out.println();

TreeTest.postOrderRecursion(root);

System.out.println();

List res = TreeTest.preOrderStack(root);