二叉树的递归遍历
首先定义我们的二叉树的节点结构，节点包括数据，左节点，右节点。
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();
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;
Node P
= null;
while(
!stack.isEmpty()){
while (
stack.peek()
!=null) {
stack.push(
stack.peek()
.getLeft());
}
stack.pop();
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();
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;
Node P =
null;
while(!stack.isEmpty()){
while (stack.peek()!=
null) {
stack.push(stack.peek().getLeft());
}
stack.pop();
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;
}
}
}
}
}
}
输出结果
先序遍历
A,B,
D,
C,
中序遍历
D,B,A,
C,
后序遍历
D,B,
C,A,
非递归先序遍历
A,B,
D,
C,
非递归中序遍历
D,B,A,
C,
非递归后序遍历
D,B,
C,A,
