摘要：二叉樹(shù)主要有3種遍歷算法，分為為先序纹笼、中序纹份、后序。本文對(duì)二叉樹(shù)的3種遍歷算法的遍歷規(guī)則進(jìn)行介紹廷痘，并給出3種遍歷算法的遞歸和迭代版本的C++實(shí)現(xiàn)矮嫉。文章發(fā)出后，我的好朋友指出還有一個(gè)層次遍歷牍疏，我將在文章最后介紹蠢笋。
1. 二叉樹(shù)遍歷
如圖1所示，一顆二叉樹(shù)T由根節(jié)點(diǎn)V鳞陨、左子樹(shù)L和右子樹(shù)R構(gòu)成昨寞。
則二叉樹(shù)T的遍歷指：按照某種次序訪問(wèn)樹(shù)中各節(jié)點(diǎn)瞻惋，每個(gè)節(jié)點(diǎn)被訪問(wèn)恰好一次。二叉樹(shù)T的先序援岩、中序歼狼、后序遍歷的結(jié)果如圖2所示。
從圖中可以看出，先序添瓷、中序梅屉、后序的區(qū)別在于局部根節(jié)點(diǎn)的訪問(wèn)時(shí)機(jī)，而對(duì)于左右孩子的訪問(wèn)鳞贷，其訪問(wèn)順序總是滿足先左后右的規(guī)則坯汤。下面舉例說(shuō)明二叉樹(shù)的遍歷規(guī)則，一棵二叉樹(shù)的結(jié)構(gòu)如圖3所示搀愧，則其遍歷結(jié)果如下：
先序遍歷結(jié)果：A B D E G H C F
中序遍歷結(jié)果：D B G H E A C F
后序遍歷結(jié)果：D H G E B F C A
2. 二叉樹(shù)節(jié)點(diǎn)
在實(shí)現(xiàn)二叉樹(shù)的遍歷算法之前惰聂，我們先創(chuàng)建一個(gè)二叉樹(shù)節(jié)點(diǎn)類。二叉樹(shù)節(jié)點(diǎn)是二叉樹(shù)的基本組成單位咱筛，節(jié)點(diǎn)與節(jié)點(diǎn)之間有父子關(guān)系搓幌、兄弟關(guān)系等，由于節(jié)點(diǎn)的數(shù)據(jù)類型不確定迅箩，所以采用模板實(shí)現(xiàn)二叉樹(shù)的節(jié)點(diǎn)類溉愁。
/*
二叉樹(shù)節(jié)點(diǎn)
*/
#define BiNodePos(T) BiNode<T>*
template<typename T>
struct BiNode{
BiNodePos(T) parent= nullptr, lChild = nullptr, rChild = nullptr;
T data; int height;
BiNode(T data, BiNodePos(T) parent){
this->data = data;
this->parent = parent;
}
//子樹(shù)規(guī)模
int size() {
int s = 1;//計(jì)入本身
if (lChild) s += lChild.size();//遞歸計(jì)入左子樹(shù)規(guī)模
if (rChild) s += rChild.size();//遞歸計(jì)入右子樹(shù)規(guī)模
return s;
}
//插入左孩子
BiNodePos(T) insertAsLC(const T &) {
return lChild = new BiNode(e, this);
}
//插入右孩子
BiNodePos(T) insertAsRC(const T &) {
return rChild = new BiNode(e, this);
}
};
3. 二叉樹(shù)遍歷算法的實(shí)現(xiàn)
3.1. 遞歸版本
#include <stack>
using namespace std;
//先序遍歷
template<typename T, typename VST >
void preTraverse(BiNodePos(T) x, VST& visit)
{
if (!x) return;
visit(x->data);
preTraverse(x->lChild);
preTraverse(x->rChild);
}//O(n)
//中序遍歷
template<typename T, typename VST >
void midTraverse(BiNodePos(T) x, VST& visit)
{
if (!x) return;
midTraverse(x->lChild);
visit(x->data);
midTraverse(x->rChild);
}//O(n)
//后序遍歷
template<typename T, typename VST >
void postTraverse(BiNodePos(T) x, VST& visit)
{
if (!x) return;
postTraverse(x->lChild);
postTraverse(x->rChild);
visit(x->data);
}//O(n)
3.2. 迭代版本
遞歸版本的時(shí)間復(fù)雜度是O(n)，理論上遞歸遍歷算法已經(jīng)事件復(fù)雜度已經(jīng)最小了沙热。但實(shí)際上，由于遞歸實(shí)例必須具有通用的格式罢缸，所以在運(yùn)行棧中篙贸，每一個(gè)遞歸實(shí)例對(duì)應(yīng)的一幀不可能做到足夠的小。而針對(duì)于具體的問(wèn)題枫疆，我們完全可以通過(guò)精巧的設(shè)計(jì)使得每一幀做到足夠小的爵川，所以，我們有必要將遞歸版本轉(zhuǎn)化為迭代版本息楔。
#include <stack>
using namespace std;
template<typename T, typename VST>
static void visitAlongLeftBranch(BiNodePos(T) x, VST& visit, stack<BiNodePos(T)> &s)
{
while (x!=nullptr)
{
visit(x->data);
s.push(x->rChild);
x = x->lChild;
}
}
template<typename T, typename VST >
void preIterationTraverse(BiNodePos(T) x, VST& visit)
{
stack<BiNodePos(T)> s;
while (true)
{
visitAlongLeftBranch(x, visit, s);
if (s.empty) break;
x = s.top();
s.pop();
}
}//O(n)
template<typename T>
static void goAlongLeftBranch(BiNodePos(T) x,stack<BiNodePos(T)> &s)
{
while (x!=nullptr)
{
s.push(x);
x = x->lChild;
}
}
template<typename T, typename VST >
void inIterationTraverse(BiNodePos(T) x, VST& visit)
{
stack<BiNodePos(T)> s;
while (true)
{
goAlongLeftBranch(x, s);
if (s.empty) break;
x = s.top();
s.pop();
visit(x->data);
x = x->rChild;
}
}//O(n)
template < typename T>
static void gotoLVFL(stack<BiNodePos(T)> s) {
BiNodePos(T) node;
while (node = s.top()) {
if (node->lChild){
if (node->rChild)
s->push(node->rChild);
s->push(node->lChild);
}
else
s->push(node->rChild);
}
s.pop();
}
template<typename T, typename VST >
void postIterationTraverse(BiNodePos(T) x, VST& visit)
{
stack<BiNodePos(T)> s;
if (x!=nullptr) s.push(x);
while (!s.empty())
{
if (s.top() != x->parent)
gotoLVFL<T>(s);
x = s.top();
visit(x->data);
}
}//O(n)
4. 層次遍歷
首先寝贡，感謝大佬幫我指正問(wèn)題。
層次遍歷是指：按層次遍歷樹(shù)的所有節(jié)點(diǎn)（即逐層地值依，從左到右訪問(wèn)所有節(jié)點(diǎn)）圃泡。下面是層次遍歷的迭代實(shí)現(xiàn)。
#include <deque>
using namespace std;
template<typename T, typename VST >
void levelIterationTraverse(BiNodePos(T) x, VST& visit)
{
deque<BiNodePos(T)> q;
q.push_back(x);
while (!q.empty())
{
x = q.front(); q.pop_front();
visit(x.data);
if (x->lChild) q.push_back(x->lChild);
if (x->rChild) q.push_back(x->rChild);
}
}//O(n)
5. Java版本的實(shí)現(xiàn)（補(bǔ)充）
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public void preOrder(TreeNode root)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null || !stack.empty())
{
while(root != null)
{
System.out.print(root.val + " ");
stack.push(root);
root = root.left;
}
if(!stack.empty())
{
root = stack.pop();
root = root.right;
}
}
}
void midOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null || !stack.empty())
{
while(root != null)
{
stack.push(root);
root = root.left;
}
if(!stack.empty())
{
root = stack.pop();
System.out.print(root.val + " ");
root = root.right;
}
}
}
/**
* 后序遍歷的難點(diǎn)在于：
* 需要判斷上次訪問(wèn)的節(jié)點(diǎn)是位于左子樹(shù)愿险，還是右子樹(shù)颇蜡。
* 若是位于左子樹(shù)，則需跳過(guò)根節(jié)點(diǎn)，先進(jìn)入右子樹(shù)风秤，再回頭訪問(wèn)根節(jié)點(diǎn)鳖目；
* 若是位于右子樹(shù)，則直接訪問(wèn)根節(jié)點(diǎn)
* @param root
*/
void postOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root, last = null;
//先把curr移動(dòng)到左子樹(shù)最下邊
while (curr != null){
stack.push(curr);
curr = curr.left;
}
while (!stack.isEmpty()){
curr = stack.peek();
//一個(gè)根節(jié)點(diǎn)被訪問(wèn)的前提是：無(wú)右子樹(shù)或右子樹(shù)已被訪問(wèn)過(guò)
if (curr.right == null || curr.right == last){
System.out.print(curr.val + " ");
last = curr;
stack.pop();
}
else {
//進(jìn)入右子樹(shù)
curr = curr.right;
while (curr != null){
stack.push(curr);
curr = curr.left;
}
}
}
}
void levelOrder(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);
}
}
