二叉树遍历

二叉树遍历非递归实现

目次
二叉树遍历非递归实现
树节点界说：
先序遍历：
中序遍历：
后序遍历：
测试代码：
先序遍历测试代码：
中序遍历测试代码：
后序遍历测试代码：

---

树节点界说：

1. public class TreeNode {
2.     int val;
3.     TreeNode left;
4.     TreeNode right;
5.     TreeNode() {}
6.     TreeNode(int val) { this.val = val; }
7.     TreeNode(int val, TreeNode left, TreeNode right) {
8.     this.val = val;
9.     this.left = left;
10.     this.right = right;
11.     }
12. }

复制代码

先序遍历：

1.     /**
2.      * 前序遍历二叉树
3.      * @param root
4.      * @return
5.      */
6.     public List<Integer> preorderTraversal(TreeNode root) {
7.         Stack<TreeNode> stack = new Stack<>();
8.         List<Integer> list = new LinkedList<>();
9.         while (root != null || !stack.isEmpty()) {
10.             if (root != null) {
11.                 // 先访问根节点
12.                 list.add(root.val);
13.                 stack.push(root);
14.                 // 然后访问左子树
15.                 root = root.left;
16.             } else {
17.                 // 如果没有左子树，访问右子树
18.                 root = stack.pop();
19.                 root = root.right;
20.             }
21.         }
22.         return list;
23.     }

复制代码

中序遍历：

1.     /**
2.      * 中序遍历二叉树
3.      * @param root
4.      * @return
5.      */
6.     public List<Integer> inorderTraversal(TreeNode root) {
7.         Stack<TreeNode> stack = new Stack<>();
8.         List<Integer> list = new LinkedList<>();
9.         while (root != null || !stack.isEmpty()) {
10.             if (root!=null){
11.                 stack.push(root);
12.                 //先访问左子树
13.                 root = root.left;
14.             }else {
15.                 root = stack.pop();
16.                 //访问根节点
17.                 list.add(root.val);
18.                 //访问右子树
19.                 root = root.right;
20.             }
21.         }
22.         return list;
23.     }

复制代码

后序遍历：

1.     /**
2.      * 后序遍历二叉树
3.      * @param root
4.      * @return
5.      */
6.     public List<Integer> postorderTraversal(TreeNode root) {
7.         Stack<TreeNode> stack = new Stack<>();
8.         List<Integer> list = new LinkedList<>();
9.         // 记录上一个访问的节点
10.         TreeNode lastVisited = null;
11.         while (root != null || !stack.isEmpty()) {
12.             if (root != null) {
13.                 stack.push(root);
14.                 // 先访问左子树
15.                 root = root.left;
16.             } else {
17.                 TreeNode peekNode = stack.peek();
18.                 // 如果右子树不存在或已经被访问过，则访问当前节点
19.                 if (peekNode.right == null || peekNode.right == lastVisited) {
20.                     list.add(peekNode.val);
21.                     // 更新上一个访问的节点
22.                     lastVisited = stack.pop();
23.                 } else {
24.                     // 否则访问右子树
25.                     root = peekNode.right;
26.                 }
27.             }
28.         }
29.         return list;
30.     }

复制代码

层序遍历：

1.     /**
2.      * 层序遍历二叉树
3.      * @param root
4.      * @return
5.      */
6.     public List<Integer> levelorderTraversal(TreeNode root) {
7.         List<Integer> list = new LinkedList<>();
8.         // 如果根节点为空，直接返回空列表
9.         if (root == null) {
10.             return list;
11.         }
12.         LinkedList<TreeNode> queue = new LinkedList<>();
13.         queue.add(root);
14.         while (!queue.isEmpty()) {
15.             TreeNode node = queue.poll();
16.             list.add(node.val);
17.             if (node.left != null) {
18.                 queue.add(node.left);
19.             }
20.             if (node.right != null) {
21.                 queue.add(node.right);
22.             }
23.         }
24.         return list;
25.     }

复制代码

测试代码：

先序遍历测试代码：

1.     /**
2.      * 测试前序遍历
3.      */
5.     @Test
6.     public void testPreorderTraversal() {
7.         TreeNode root = new TreeNode(1);
8.         root.left = new TreeNode(2);
9.         root.right = new TreeNode(3);
10.         root.left.left = new TreeNode(4);
11.         root.left.right = new TreeNode(5);
13.         BinaryTree binaryTree = new BinaryTree();
14.         List<Integer> result = binaryTree.preorderTraversal(root);
15.         // 输出: [1, 2, 4, 5, 3]
16.         System.out.println(result);
17.     }

复制代码

中序遍历测试代码：

1.     /**
2.      * 测试中序遍历
3.      */
4.     @Test
5.     public void testInorderTraversal() {
6.         TreeNode root = new TreeNode(1);
7.         root.left = new TreeNode(2);
8.         root.right = new TreeNode(3);
9.         root.left.left = new TreeNode(4);
10.         root.left.right = new TreeNode(5);
11.         BinaryTree binaryTree = new BinaryTree();
12.         List<Integer> result = binaryTree.inorderTraversal(root);
13.         // 输出: [4, 2, 5, 1, 3]
14.         System.out.println(result);
15.     }

复制代码

后序遍历测试代码：

1.     /**
2.      * 测试后序遍历
3.      */
4.     @Test
5.     public void testPostorderTraversal() {
6.         TreeNode root = new TreeNode(1);
7.         root.left = new TreeNode(2);
8.         root.right = new TreeNode(3);
9.         root.left.left = new TreeNode(4);
10.         root.left.right = new TreeNode(5);
11.         BinaryTree binaryTree = new BinaryTree();
12.         List<Integer> result = binaryTree.postorderTraversal(root);
13.         // 输出: [4, 5, 2, 3, 1]
14.         System.out.println(result);
15.     }

复制代码

层序遍历测试代码：

1.     /**
2.      * 测试层序遍历
3.      */
4.     @Test
5.     public void testLevelorderTraversal() {
6.         TreeNode root = new TreeNode(1);
7.         root.left = new TreeNode(2);
8.         root.right = new TreeNode(3);
9.         root.left.left = new TreeNode(4);
10.         root.left.right = new TreeNode(5);
11.         BinaryTree binaryTree = new BinaryTree();
12.         List<Integer> result = binaryTree.levelorderTraversal(root);
13.         // 输出: [1, 2, 3, 4, 5]
14.         System.out.println(result);
15.     }

复制代码

注：深度优先搜索计谋与广度优先搜索计谋暂不在本文探究范围。