java 二叉树的先序，中序，后序遍历
一、前序遍历
访问顺序：先根节点，再左子树，最后右子树；上图的访问结果为：GDAFEMHZ。
1）递归实现
public void preOrderTraverse1(TreeNode root) {
if (root != null) {
System.out.print(root.val + "->");
preOrderTraverse1(root.left);
preOrderTraverse1(root.right);
}
}
2）非递归实现
public void preOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.empty()) {
if (node != null) {
System.out.print(node.val + "->");
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
node = tem.right;
}
}
}
二、中序遍历
访问顺序：先左子树，再根节点，最后右子树；上图的访问结果为：ADEFGHMZ。
1）递归实现
public void inOrderTraverse(TreeNode root) {
if (root != null) {
inOrderTraverse(root.left);
System.out.print(root.val + "->");
inOrderTraverse(root.right);
}
}
2）非递归实现
public void inOrderTraverse(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
TreeNode tem = stack.pop();
System.out.print(tem.val + "->");
node = tem.right;
}
}
}
三、后序遍历
访问顺序：先左子树，再右子树，最后根节点，上图的访问结果为：AEFDHZMG。
1）递归实现
public void postOrderTraverse(TreeNode root) {
if (root != null) {
postOrderTraverse(root.left);
postOrderTraverse(root.right);
System.out.print(root.val + "->");
}
}
2）非递归实现
方法1
public void postOrderTraverse(TreeNode root) {
TreeNode cur, pre = null;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
cur = stack.peek();
if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
System.out.print(cur.val + "->");
stack.pop();
pre = cur;
} else {
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
}
}
方法2
public void thePostOrderTraversal_Stack(Node root) { //后序遍历
Stack<Node> stack = new Stack<Node>();
Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后序遍历的结果
Node node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
output.push(node);
stack.push(node);
node = node.getRightNode();
} else {
node = stack.pop();
node = node.getLeftNode();
}
}
while (output.size() > 0) {
printNode(output.pop());
}
}
方法3
import java.util.*;
public class Solution {
public int[] postorderTraversal (TreeNode root) {
//添加遍历结果的数组
List<Integer> list = new ArrayList();
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode pre = null;
while(root != null || !s.isEmpty()){
//每次先找到最左边的节点
while(root != null){
s.push(root);
root = root.left;
}
//弹出栈顶
TreeNode node = s.pop();
//如果该元素的右边没有或是已经访问过
if(node.right == null || node.right == pre){
//访问中间的节点
list.add(node.val);
//且记录为访问过了
pre = node;
}else{
//该节点入栈
s.push(node);
//先访问右边
root = node.right;
}
}
//返回的结果
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++)
res[i] = list.get(i);
return res;
}
}
四、层次遍历
访问结果：GDMAFHZE。
public void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + "->");
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
三种遍历方式都分为递归与非递归的方式。三种遍历方式的递归思想相同。后序遍历非递归方法分为两种，具体见代码。
构造方式：
1 #include<iostream>
2 #include<stack>
3 using namespace std;
4
5 typedef struct BiTNode{
6 char data;
7 int lvisited,rvisited;//左、右孩子是否访问过，1表示已访问（此项只在后序非递归2算法中需要）
8 struct BiTNode *lchild,*rchild;
9 }BiTNode,*BiTree;
10
11 void InitBiTree(BiTree &T)//构造空二叉树
12 {
13 T=NULL;
14 }
15 void CreateBiTree(BiTree &T)//生成二叉树
16 {
17 char ch;
18 cin>>ch;
19 if(ch=='0')//0代表空
20 T=NULL;
21 else
22 {
23 T=(BiTree)malloc(sizeof(BiTNode));//生成根结点
24 if(!T)
25 {
26 cout<<"生成结点错误！"<<endl;
27 return;
28 }
29 T->data=ch;
30 T->lvisited=0;
31 T->rvisited=0;
32 CreateBiTree(T->lchild);
33 CreateBiTree(T->rchild);
34 }
35 }
三种遍历方式代码：
1 void PreOrder(BiTree T)//先序递归遍历
2 {
3 if(T!=NULL)
4 {
5 cout<<T->data<<" ";
6 PreOrder(T->lchild);
7 PreOrder(T->rchild);
8 }
9 }
10 void SqlPreOrder(BiTree T)//先序非递归遍历
11 {
12 stack<BiTree> s;
13 BiTree p=T;
14 while(p || !s.empty())
15 {
16 if(p)
17 {
18 cout<<p->data<<" ";
19 s.push(p);
20 p=p->lchild;
21 }
22 else
23 {
24 p=s.top();
25 p=p->rchild;
26 s.pop();
27 }
28 }
29 }
30
31
32
33 void InOrder(BiTree T)//中序递归遍历
34 {
35 if(T!=NULL)
36 {
37 InOrder(T->lchild);
38 cout<<T->data<<" ";
39 InOrder(T->rchild);
40 }
41 }
42 void SqInOrder(BiTree T)//中序非递归遍历
43 {
44 stack<BiTree> s;
45 BiTree p=T;
46 while(p || !s.empty())
47 if(p)
48 {
49 s.push(p);
50 p=p->lchild;
51 }
52 else
53 {
54 p=s.top();
55 cout<<p->data<<" ";
56 s.pop();
57 p=p->rchild;
58 }
59 }
60
61
62
63 void PostOrder(BiTree T)//后序递归遍历
64 {
65 if(T!=NULL)
66 {
67 PostOrder(T->lchild);
68 PostOrder(T->rchild);
69 cout<<T->data<<" ";
70 }
71 }
72
73 //后序非递归遍历1思路：因为后序非递归遍历二叉树的顺序是先访问左子树，再访问后子树，最后
74 //访问根结点。当用堆栈来存储结点，必须分清返回根结点时，是从左子树返回的，还是从右子树
75 //返回的。所以，使用辅助指针r，其指向最近访问过的结点。
76 void SqlPostOrder1(BiTree T)//后序非递归遍历1
77 {
78 stack<BiTree> s;
79 BiTree p=T,r;
80 while(p || !s.empty())
81 {
82 if(p) //走到最左边
83 {
84 s.push(p);
85 p=p->lchild;
86 }
87 else //向右
88 {
89 p=s.top();//取栈顶结点
90 if(p->rchild && p->rchild!=r)//如果右子树存在，且未被访问过
91 {
92 p=p->rchild;
93 s.push(p);
94 p=p->lchild; //再走到最左
95 }
96 else //否则，访问栈顶结点并弹出
97 {
98 cout<<p->data<<" ";
99 r=p; //记录该结点
100 s.pop();
101 p=NULL; //结点访问完后，重置p指针
102 }
103 }
104 }
105 }
106 //思路2：在结点中增加标志域，记录是否已被访问。
107 void SqlPostOrder2(BiTree T)//后序非递归遍历2
108 {
109 stack<BiTree> s;
110 BiTree p=T;
111 while(p || !s.empty())
112 {
113 if(p && p->lvisited==0) //左走，且左子树未被访问
114 {
115 p->lvisited=1;
116 s.push(p);
117 p=p->lchild;
118 }
119 else
120 {
121 p=s.top();
122 if(p->rchild!=NULL && p->rvisited==0)//右子树未被访问，右走一步
123 {
124 p->rvisited=1;
125 p=p->rchild;
126 }
127 else //访问栈顶元素并弹栈
128 {
129 cout<<p->data<<" ";
130 s.pop();
131 if(!s.empty())
132 p=s.top();
133 else //当最后一个元素弹栈出去后，结束
134 return ;
135 }
136 }
137 }
138 }
