=================先序遍歷===============
先序遍歷偽代碼1：
void preOrder1(TNode *root)
{
Stack st;
while((root != NULL) || !st.empty())
{
if(root!=NULL)
{
visit(root); //先訪問再入棧
st.push(root);
root = root->left;
}
else
{
root = st.pop();
root = root->right;
}
}
}
先序遍歷偽代碼2：
void preOrder2(TNode* root)
{
if(root != NULL)
{
Stack st;
st.push(root);
while( !st.empty() )
{
TNode* node = st.pop();
visit(node); //先訪問根節點，然後根節點就不用入棧了
st.push(node->right); //先push右節點，然後是左節點
st.push(node->left); //這樣上邊先訪問到左節點
}
}
}
先序遍歷不用棧：
void preOrder3(TNode* root)
{
while(root != NULL)
{
if(!root->bVisited)
{
visit(root);
root->bVisited = true;
}
if(root->left && !root->left->bVisited)
{
root = root->left;
}
else if(root->right!=NULL && !root->right->bVisited)
{
root = root->right;
}
else
{ //回溯
root = root->parent;
}
}
}
=================中序遍歷===============
中序遍歷偽代碼：
void inOrder1(TNode* root)
{
Stack s;
while(root != NULL || !s.empty())
{
while(root!=NULL) //找到左子樹
{
s.push(root); //先入棧
root = root->left;
}
if(!s.empty())
{
root = s.pop(); //再訪問
visit(root);
root = root->right; //通過下一次循環遍歷右子樹
}
}
}
中序遍歷不用棧：
void inOrder3(TNode* root)
{
while(root!=NULL)
{
while(root->left!=NULL && !root->left->bVisited)
{
root = root->left;
}
if(!root->bVisited)
{
visit(root);
root->bVisited = true;
}
if(root->right!=NULL && !root->right->bVisited)
{
root = root->right;
}
else
{
root = root->parent; // 回溯
}
}
}
=================後序遍歷===============
後序遍歷的偽代碼：
void PostOrder(TNode* root)
{
stack s;
if(root != NULL)
s.push(root);
while(!s.empty())
{
TNode* node = s.pop();
if(node->bPushed) //其左右子樹都已入棧，則訪問該節點
{
visit(node);
}
else
{ //左右子樹尚未入棧，則依次將根節點、右節點和左節點入棧
s.push(node); // 1> root入棧
if( node->right != NULL)
{
node->right->bPushed = false; //先把左右子樹設為false
s.push(node->right); // 2> 右子樹入棧
}
if( node->left != NULL)
{
node->left->bPushed = false; //先把左右子樹設為false
s.push(node->left); // 3> 左子樹入棧
}
node->bPushed = true; // 左右子樹都已入棧，根節點可以訪問了
}
}
}
=================層序遍歷===============
分層遍歷偽代碼：
void levelOrder(TNode* root)
{
Queue Q;
Q.push(root);
while(!Q.empty())
{
TNode* node = Q.front();
visit(node);
if( node->left != NULL)
{
Q.push(node->left);
}
if(node->right != NULL)
{
Q.push(node->right);
}
}
}
《編程之美》中使用vector容器來儲存n個節點信息，並用一個游標變量last記錄前一層的訪問結束條件，實現如下:
void PrintNodeByLevel(Node* root)
{
vector<Node*> vec; // 這裡我們使用STL 中的vector來代替數組，可利用到其動態擴展的屬性
vec.push_back(root);
int cur = 0;
int last = 1;
while(cur < vec.size()) {
Last = vec.size(); // 新的一行訪問開始，重新定位last於當前行最後一個節點的下一個位置
while(cur < last) {
cout << vec[cur]->data << " "; // 訪問節點
if(vec[cur] -> lChild) // 當前訪問節點的左節點不為空則壓入
vec.push_back( vec[cur]->lChild );
// 當前訪問節點的右節點不為空則壓入，注意左右節點的訪問順序不能顛倒
if( vec[cur]->rChild )
vec.push_back( vec[cur]->rChild );
cur++;
}
cout << endl; // 當cur == last時,說明該層訪問結束，輸出換行符
}
}
另外，
============求樹深==========
//若T為空樹，則深度為0，否則其深度等於左子樹或右子樹的最大深度加1
int getDepth(BiTree T)
{
if (T==NULL) return 0;
else{
dep1 = getDepth(T-> lchild);
dep2 = getDepth(T-> rchild);
return dep1 > dep2 ? dep1+1 : dep2+1;
}
小結一下：
用棧來實現比增加指向父節點指針回溯更方便：
1.采用棧的方法，就是跟蹤指針移動，用棧保存中間結果的實現方式，先序與中序難度一致，後序很困難。先序與中序只需要修改一下訪問的位置即可。
2.采用增加父節點的方法，直接用棧來模擬遞歸，先序非常簡單；而中序與後序難度一致。先序簡單是因為節點可以直接訪問，訪問完畢後無需記錄。
而中序與後序時，節點在彈棧後還不能立即訪問，還需要等其他節點訪問完畢後才能訪問，因此節點需要設置標志位來判定，因此需要額外的O(n)空間。
附：C源程序
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define NULL 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T){
char ch;
ch=getchar();
if (ch== '# ') (*T)=NULL; /* #代表空指針*/
else {
(*T)=(BiTree) malloc(sizeof(BiTNode));/*申請結點 */
(*T)-> data=ch; /*生成根結點 */
CreateBiTree(&(*T)-> lchild) ; /*構造左子樹 */
CreateBiTree(&(*T)-> rchild) ; /*構造右子樹 */
}
return 1;
}
void PreOrder(BiTree T){
if (T) {
printf( "%2c ",T-> data); /*訪問根結點，此處簡化為輸出根結點的數據值*/
PreOrder(T-> lchild); /*先序遍歷左子樹*/
PreOrder(T-> rchild); /*先序遍歷右子樹*/
}
}
void LevleOrder(BiTree T){
/*層次遍歷二叉樹T，從第一層開始，每層從左到右*/
/*用一維數組表示隊列，front和rear分別表示隊首和隊尾指針*/
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;
if(T) /*若樹非空*/
{
Queue[rear++]=T; /*根結點入隊列*/
while(front != rear){ /*當隊列非空*/
b=Queue[front++]; /*隊首元素出隊列，並訪問這個結點*/
printf( "%2c ",b-> data);
if(b-> lchild!=NULL)
Queue[rear++]=b-> lchild; /*左子樹非空，則入隊列*/
if(b-> rchild!=NULL)
Queue[rear++]=b-> rchild; /*右子樹非空，則入隊列*/
}
}
}//LevelOrder
int getDepth(BiTree T)
{
if (T==NULL) return 0;
else{
dep1 = getDepth(T-> lchild);
dep2 = getDepth(T-> rchild);
return dep1 > dep2 ? dep1+1 : dep2+1;
}//depth
main(){
BiTree T=NULL;
printf( "\nCreate a Binary Tree\n ");
CreateBiTree(&T); /*建立一棵二叉樹T*/
printf( "\nThe preorder is:\n ");
PreOrder(T); /*先序遍歷二叉樹*/
printf( "\nThe level order is:\n ");
LevleOrder(T); /*層次遍歷二叉樹*/
printf( "\nThe depth is:%d\n ",depth(T));
}
作者 sdtarena
