# 数据结构——二叉树（递归与非递归遍历）

xiaoxiao2021-02-28  5

## 二叉树的递归遍历

class Node { private Object data; private Node left; private Node right; public Node(Object data) { this.data = data; } public Object getData() { return data; } public Object setData(Object data) { return this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }

### 先序遍历

// 先序遍历 public void preOrder(Node root) { if (root != null) { System.out.print(root.getData() + ","); preOrder(root.getLeft()); preOrder(root.getRight()); } }

### 中序遍历

// 中序遍历 public void inOrder(Node root) { if (root != null) { inOrder(root.getLeft()); System.out.print(root.getData() + ","); inOrder(root.getRight()); } }

### 后序遍历

// 后序遍历 public void postOrder(Node root) { if (root != null) { postOrder(root.getLeft()); postOrder(root.getRight()); System.out.print(root.getData() + ","); } }

## 二叉树的非递归遍历

### 非递归先序遍历

// 非递归先序遍历 public void preOrder2(Node root) { Stack<Object> stack = new Stack<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { Node T = (Node) stack.pop(); System.out.print(T.getData() + ","); while (T != null) { if (T.getLeft() != null) { System.out.print(T.getLeft().getData() + ","); } if (T.getRight() != null) { stack.push(T.getRight()); } // 遍历左子树 T = T.getLeft(); } } }

### 非递归中序遍历

// 非递归中序遍历 public void midOrder2(Node root) { Node T = root; Stack<Node> stack = new Stack<>(); if (T != null) { stack.push(T); while (!stack.isEmpty()) { while (stack.peek() != null) {// 用于判断是否被访问过 stack.push(stack.peek().getLeft()); } stack.pop();// null出栈 if (!stack.isEmpty()) { T = stack.pop(); System.out.print(T.getData()+","); //放入右子树 stack.push(T.getRight()); } } } }

### 非递归后序遍历

//非递归后序遍历 public void postOrder2(Node root){ Node T = root; if (T!=null) { Stack<Node> stack = new Stack<>(); stack.push(T); boolean flag = false;//false未访问，true访问 Node P = null;//指向刚访问过的节点 while(!stack.isEmpty()){ while (stack.peek()!=null) {//循环遍历左子树 stack.push(stack.peek().getLeft()); } stack.pop();//null出栈 while(!stack.isEmpty()){ T = stack.peek(); if (T.getRight()==null||T.getRight()==P) {//当右子树为空或者访问过，输出 System.out.print(T.getData()+","); stack.pop(); flag = true; P = T; }else {//右子树入栈，循环遍历 stack.push(T.getRight()); flag = false; } if (!flag) { break;//未访问节点，跳出循环，去访问左右子树 } } } } }

### 完整代码

import java.util.Stack; class Node { private Object data; private Node left; private Node right; public Node(Object data) { this.data = data; } public Object getData() { return data; } public Object setData(Object data) { return this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } } public class Tree { public static void main(String[] args) { Node node = new Node("A"); Node node2 = new Node("B"); node.setLeft(node2); node2.setLeft(new Node("D")); node.setRight(new Node("C")); Tree tree = new Tree(); System.out.println("先序遍历"); tree.preOrder(node); System.out.println("\n中序遍历"); tree.inOrder(node); System.out.println("\n后序遍历"); tree.postOrder(node); System.out.println("\n非递归先序遍历"); tree.preOrder2(node); System.out.println("\n非递归中序遍历"); tree.midOrder2(node); System.out.println("\n非递归后序遍历"); tree.postOrder2(node); } // 先序遍历 public void preOrder(Node root) { if (root != null) { System.out.print(root.getData() + ","); preOrder(root.getLeft()); preOrder(root.getRight()); } } // 中序遍历 public void inOrder(Node root) { if (root != null) { inOrder(root.getLeft()); System.out.print(root.getData() + ","); inOrder(root.getRight()); } } // 后序遍历 public void postOrder(Node root) { if (root != null) { postOrder(root.getLeft()); postOrder(root.getRight()); System.out.print(root.getData() + ","); } } /*********************** 非递归算法 ********************************/ // 非递归先序遍历 public void preOrder2(Node root) { Stack<Object> stack = new Stack<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { Node T = (Node) stack.pop(); System.out.print(T.getData() + ","); while (T != null) { if (T.getLeft() != null) { System.out.print(T.getLeft().getData() + ","); } if (T.getRight() != null) { stack.push(T.getRight()); } // 遍历左子树 T = T.getLeft(); } } } // 非递归中序遍历 public void midOrder2(Node root) { Node T = root; Stack<Node> stack = new Stack<>(); if (T != null) { stack.push(T); while (!stack.isEmpty()) { while (stack.peek() != null) {// 用于判断是否被访问过 stack.push(stack.peek().getLeft()); } stack.pop();// null出栈 if (!stack.isEmpty()) { T = stack.pop(); System.out.print(T.getData()+","); //放入右子树 stack.push(T.getRight()); } } } } //非递归后序遍历 public void postOrder2(Node root){ Node T = root; if (T!=null) { Stack<Node> stack = new Stack<>(); stack.push(T); boolean flag = false;//false未访问，true访问 Node P = null;//指向刚访问过的节点 while(!stack.isEmpty()){ while (stack.peek()!=null) {//循环遍历左子树 stack.push(stack.peek().getLeft()); } stack.pop();//null出栈 while(!stack.isEmpty()){ T = stack.peek(); if (T.getRight()==null||T.getRight()==P) {//当右子树为空或者访问过，输出 System.out.print(T.getData()+","); stack.pop(); flag = true; P = T; }else {//右子树入栈，循环遍历 stack.push(T.getRight()); flag = false; } if (!flag) { break;//未访问节点，跳出循环，去访问左右子树 } } } } } }