class TreeNode {
public:
V val;
TreeNode *lchild;
TreeNode *rchild;
};
2、二叉树的先序、中序、后序遍历概念
-
先序：任何子树的处理顺序都是，先根节点、再左子树、然后右子树
-
中序：任何子树的处理顺序都是，先左子树、再根节点、然后右子树
-
后序：任何子树的处理顺序都是，先左子树、再右子树、然后根节点
void f(TreeNode *root) {
if (root == nullptr) return ;
//1
f(root->lchild);
//2
f(root->rchild);
//3
}
如果打印行为放在 1 处，则是先序遍历；如果打印行为放在 2 处，则是中序遍历；如果打印行为放在 3 处，则是后序遍历。
为什么三种遍历都能由同一份代码该出来呢？因为它们都有一个最本质的东西，那就是 递归序。
3.1 理解递归序对于如下的二叉树：
它的递归访问顺序：
递归序保证每个节点都会到达三次，通过递归序可以加工出先序、中序、后序遍历的顺序。
-
第一次到达节点的时候打印，二三次到达的时候不做任何事，就是先序；（a，b，d，e，c，f，g）
-
第二次到达节点的时候打印，一三次到达的时候不做任何事，就是中序；（d，b，e，a，f，c，g）
-
第三次到达节点的时候打印，一二次到达的时候不做任何事，就是后序。（d，e，b，f，g，c，a）
#includeJava 版using namespace std; class TreeNode { public: int val; TreeNode *lchild; TreeNode *rchild; TreeNode(int v) : val(v) { } }; //先序遍历 void pre(TreeNode *root) { if (root == nullptr) return ; cout << root->val << " "; pre(root->lchild); pre(root->rchild); } //中序遍历 void in(TreeNode *root) { if (root == nullptr) return ; in(root->lchild); cout << root->val << " "; in(root->rchild); } //后序遍历 void post(TreeNode *root) { if (root == nullptr) return ; post(root->lchild); post(root->rchild); cout << root->val << " "; } int main() { TreeNode *root = new TreeNode(1); root->lchild = new TreeNode(2); root->rchild = new TreeNode(3); root->lchild->lchild = new TreeNode(4); root->lchild->rchild = new TreeNode(5); root->rchild->lchild = new TreeNode(6); root->rchild->rchild = new TreeNode(7); cout << "pre-order:"; pre(root); cout << endl; cout << "============" << endl; cout << "in-order:"; in(root); cout << endl; cout << "============" << endl; cout << "post-order:"; post(root); cout << endl; cout << "============" << endl; return 0; }
public class RecursiveTraversalBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
public static void f(Node head) {
if (head == null) {
return;
}
// 1
f(head.left);
// 2
f(head.right);
// 3
}
// 先序打印所有节点
public static void pre(Node head) {
if (head == null) {
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
public static void in(Node head) {
if (head == null) {
return;
}
in(head.left);
System.out.println(head.value);
in(head.right);
}
public static void pos(Node head) {
if (head == null) {
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
pre(head);
System.out.println("========");
in(head);
System.out.println("========");
pos(head);
System.out.println("========");
}
}
4、非递归方式实现二叉树的先序、中序、后序遍历
1）任何递归函数都可以改成非递归
2）自己设计压栈来实现
4.1 先序遍历流程1）根节点入栈
2）栈顶元素出栈，记为 cur
3）如果cur 有右孩子，则右孩子入栈；如果有左孩子，则左孩子入栈；即先右后左
4）重复步骤 2) ~ 4)
//先序遍历：根 左 右
void pre(TreeNode *root) {
cout << "pre-order:";
if (root == nullptr) return ;
stack sta;
sta.push(root); //根节点入栈
while (!sta.empty()) {
root = sta.top(); // 复用root
sta.pop(); //弹出栈顶
cout << root->val << " ";
if (root->rchild != nullptr) { //右孩子入栈
sta.push(root->rchild);
}
if (root->lchild != nullptr) { //左孩子入栈
sta.push(root->lchild);
}
}
cout << endl;
}
4.2 后序遍历流程
根据先序遍历的流程，可以加工出 “根-右-左” 的遍历顺序，无非就是先左孩子入栈，然后右孩子入栈。要是再准备一个栈，弹出的节点不立即打印，而是放入该栈中，最后所有节点都放入该栈后，再弹出节点进行打印，那么得到的顺序就是 **“左-右-根”**的遍历顺序，这就是后序遍历的顺序。
//使用两个栈实现后序遍历：左、右、根
void post(TreeNode *cur) {
cout << "post-order:";
if (cur == nullptr) return ;
//准备两个栈
stack sta1;
stack sta2;
sta1.push(cur);
while (!sta1.empty()) { //弹出栈的顺序是：根、右、左
cur = sta1.top();
sta1.pop();
sta2.push(cur); //弹出的节点放到另一个栈中
if (cur->lchild != nullptr) { //左节点入栈
sta1.push(cur->lchild);
}
if (cur->rchild != nullptr) { //右节点入栈
sta1.push(cur->rchild);
}
}
while (!sta2.empty()) { //弹出栈中的顺序是：左、右、根，就是后序遍历顺序
cout << sta2.top()->val << " ";
sta2.pop();
}
cout << endl;
}
4.3 中序遍历流程
1）当前节点 cur，cur 为根的树，整条左边界入栈，直到遇到空节点。即先将根节点开始的所有左孩子入栈，然后转 2）
2）栈中弹出节点打印，cur 变成节点的右孩子，转 1）
3）栈为空停止
//中序遍历
void in(TreeNode *cur) {
cout << "in-order:";
if (cur == nullptr) return ;
stack sta;
while (!sta.empty() || cur != nullptr) {
if (cur != nullptr) {
sta.push(cur);
cur = cur->lchild;
} else {
cur = sta.top();
sta.pop();
cout << cur->val << " ";
cur = cur->rchild;
}
}
cout << endl;
}
这个原理就是每棵树都能由左树进行分解，当前节点出栈，一定是左子树被处理完毕，才会到当前节点，所以最终得到的顺序是 “左-根-右”，即中序遍历顺序。
4.4 完整代码实现 C++ 版#includeJava 版#include using namespace std; class TreeNode { public: int val; TreeNode *lchild; TreeNode *rchild; TreeNode(int v) : val(v) { } }; //先序遍历：根 左 右 void pre(TreeNode *root) { cout << "pre-order:"; if (root == nullptr) return ; stack sta; sta.push(root); //根节点入栈 while (!sta.empty()) { root = sta.top(); // 复用root sta.pop(); //弹出栈顶 cout << root->val << " "; if (root->rchild != nullptr) { //右孩子入栈 sta.push(root->rchild); } if (root->lchild != nullptr) { //左孩子入栈 sta.push(root->lchild); } } cout << endl; } //中序遍历 void in(TreeNode *cur) { cout << "in-order:"; if (cur == nullptr) return ; stack sta; while (!sta.empty() || cur != nullptr) { if (cur != nullptr) { sta.push(cur); cur = cur->lchild; } else { cur = sta.top(); sta.pop(); cout << cur->val << " "; cur = cur->rchild; } } cout << endl; } //使用两个栈实现后序遍历：左、右、根 void post(TreeNode *cur) { cout << "post-order:"; if (cur == nullptr) return ; stack sta1; stack sta2; sta1.push(cur); while (!sta1.empty()) { //弹出栈的顺序是：根、右、左 cur = sta1.top(); sta1.pop(); sta2.push(cur); //弹出的节点放到另一个栈中 if (cur->lchild != nullptr) { //左节点入栈 sta1.push(cur->lchild); } if (cur->rchild != nullptr) { //右节点入栈 sta1.push(cur->rchild); } } while (!sta2.empty()) { //弹出栈中的顺序是：左、右、根，就是后序遍历顺序 cout << sta2.top()->val << " "; sta2.pop(); } cout << endl; } //使用一个栈实现后序遍历 void post2(TreeNode *root) { cout << "post-order2:"; if (root == nullptr) return ; stack sta; sta.push(root); TreeNode *cur = nullptr; while (!sta.empty()) { cur = sta.top(); if (cur->lchild != nullptr && root != cur->lchild && root != cur->rchild) { sta.push(cur->lchild); } else if (cur->rchild != nullptr && root != cur->rchild) { sta.push(cur->rchild); } else { cout << sta.top()->val << " "; sta.pop(); root = cur; } } cout << endl; } int main() { TreeNode *root = new TreeNode(1); root->lchild = new TreeNode(2); root->rchild = new TreeNode(3); root->lchild->lchild = new TreeNode(4); root->lchild->rchild = new TreeNode(5); root->rchild->lchild = new TreeNode(6); root->rchild->rchild = new TreeNode(7); pre(root); cout << "============" << endl; in(root); cout << "============" << endl; post(root); cout << "============" << endl; post2(root); cout << "============" << endl; return 0; }
import java.util.Stack;
public class UnRecursiveTraversalBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
public static void pre(Node head) {
System.out.print("pre-order: ");
if (head != null) {
Stack stack = new Stack();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
System.out.println();
}
public static void in(Node cur) {
System.out.print("in-order: ");
if (cur != null) {
Stack stack = new Stack();
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
System.out.print(cur.value + " ");
cur = cur.right;
}
}
}
System.out.println();
}
public static void pos1(Node head) {
System.out.print("pos-order: ");
if (head != null) {
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop(); // 头 右 左
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
// 左 右 头
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
public static void pos2(Node h) {
System.out.print("pos-order: ");
if (h != null) {
Stack stack = new Stack();
stack.push(h);
Node c = null;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
pre(head);
System.out.println("========");
in(head);
System.out.println("========");
pos1(head);
System.out.println("========");
pos2(head);
System.out.println("========");
}
}
