遍歷二叉樹的各種操作（非遞歸遍歷）

先使用先序的方法建立一棵二叉樹，然後分別使用遞歸與非遞歸的方法實現前序、中序、後序遍歷二叉樹，並使用了兩種方法來進行層次遍歷二叉樹，一種方法就是使用STL中的queue，另外一種方法就是定義了一個數組隊列，分別使用了front和rear兩個數組的下標來表示入隊與出隊，還有兩個操作就是求二叉樹的深度、結點數。

#include<iostream> 
#include<queue> 
#include<stack> 
using namespace std; 
 
//二叉樹結點的描述 
typedef struct BiTNode
{ 
    char data; 
    struct BiTNode *lchild, *rchild;      //左右孩子 
}BiTNode,*BiTree; 
 
//按先序遍歷創建二叉樹 
//BiTree *CreateBiTree()    //返回結點指針類型 
//void CreateBiTree(BiTree &root)      //引用類型的參數 
void CreateBiTree(BiTNode **root)    //二級指針作為函數參數 
{ 
    char ch; //要插入的數據 
    scanf("\n%c", &ch);
    //cin>>ch; 
    if(ch=='#')
        *root = NULL;
    else
    {
        *root = (BiTNode *)malloc(sizeof(BiTNode));
        (*root)->data = ch;
        printf("請輸入%c的左孩子：",ch);
        CreateBiTree(&((*root)->lchild));
        printf("請輸入%c的右孩子：",ch);
        CreateBiTree(&((*root)->rchild));
    }
}
 
//前序遍歷的算法程序 
void PreOrder(BiTNode *root)
{ 
    if(root==NULL) 
        return ; 
    printf("%c ", root->data); //輸出數據 
    PreOrder(root->lchild); //遞歸調用，前序遍歷左子樹 
    PreOrder(root->rchild); //遞歸調用，前序遍歷右子樹 
} 
 
//中序遍歷的算法程序 
void InOrder(BiTNode *root) 
{ 
    if(root==NULL)
        return ;
    InOrder(root->lchild); //遞歸調用，前序遍歷左子樹 
    printf("%c ", root->data); //輸出數據 
    InOrder(root->rchild); //遞歸調用，前序遍歷右子樹 
} 
 
//後序遍歷的算法程序 
void PostOrder(BiTNode *root)
{
    if(root==NULL)
        return ;
    PostOrder(root->lchild);      //遞歸調用，前序遍歷左子樹 
    PostOrder(root->rchild);      //遞歸調用，前序遍歷右子樹 
    printf("%c ", root->data);    //輸出數據   
} 
 
/*
二叉樹的非遞歸前序遍歷，前序遍歷思想：先讓根進棧，只要棧不為空，就可以做彈出操作，
每次彈出一個結點，記得把它的左右結點都進棧，記得右子樹先進棧，這樣可以保證右子樹在棧中總處於左子樹的下面。
*/ 
void PreOrder_Nonrecursive(BiTree T)    //先序遍歷的非遞歸   
{ 
    if(!T)   
        return ;   
   
    stack<BiTree> s; 
    s.push(T); 
 
    while(!s.empty()) 
    { 
        BiTree temp = s.top(); 
        cout<<temp->data<<" "; 
        s.pop(); 
        if(temp->rchild) 
            s.push(temp->rchild); 
        if(temp->lchild) 
            s.push(temp->lchild); 
    } 
} 

void PreOrder_Nonrecursive1(BiTree T)    //先序遍歷的非遞歸
{
 if(!T) 
        return ;
 stack<BiTree> s;
 BiTree curr = T;
 while(curr != NULL || !s.empty())
 {
  while(curr != NULL)
  {
   cout<<curr->data<<"  ";
   s.push(curr);
   curr = curr->lchild;
  }
  if(!s.empty())
  {
   curr = s.top();
   s.pop();
   curr = curr->rchild;
  }
 }
}

void PreOrder_Nonrecursive2(BiTree T)    //先序遍歷的非遞歸 
{ 
    if(!T)
        return ; 
 
    stack<BiTree> s; 
    while(T)          // 左子樹上的節點全部壓入到棧中 
    { 
        s.push(T); 
        cout<<T->data<<"  "; 
        T = T->lchild; 
    } 
     
    while(!s.empty()) 
    {         
        BiTree temp = s.top()->rchild;  // 棧頂元素的右子樹 
        s.pop();                        // 彈出棧頂元素 
        while(temp)          // 棧頂元素存在右子樹，則對右子樹同樣遍歷到最下方 
        { 
            cout<<temp->data<<"  "; 
            s.push(temp); 
            temp = temp->lchild; 
        } 
    } 
} 

void InOrderTraverse1(BiTree T)  // 中序遍歷的非遞歸 
{ 
    if(!T) 
        return ; 
    BiTree curr = T;    // 指向當前要檢查的節點 
    stack<BiTree> s;
 while(curr != NULL || !s.empty())
 {
  while(curr != NULL)
  {
   s.push(curr);
   curr = curr->lchild;
  }//while
  if(!s.empty())
  {
   curr = s.top();
   s.pop();
   cout<<curr->data<<"  ";
   curr = curr->rchild;
  }
 }
}

void InOrderTraverse(BiTree T)  // 中序遍歷的非遞歸 
{ 
    if(!T) 
        return ; 
    stack<BiTree> s; 
    BiTree curr = T->lchild;    // 指向當前要檢查的節點 
    s.push(T); 
    while(curr != NULL || !s.empty()) 
    { 
        while(curr != NULL)    // 一直向左走 
        { 
            s.push(curr); 
            curr = curr->lchild; 
        } 
        curr = s.top(); 
        s.pop(); 
        cout<<curr->data<<"  "; 
        curr = curr->rchild; 
    } 
} 

void PostOrder_Nonrecursive1(BiTree T)  // 後序遍歷的非遞歸   
{   
    stack<BiTree> S;   
    BiTree curr = T ;          // 指向當前要檢查的節點 
    BiTree previsited = NULL;    // 指向前一個被訪問的節點 
    while(curr != NULL || !S.empty())  // 棧空時結束   
    {   
        while(curr != NULL)            // 一直向左走直到為空 
        {   
            S.push(curr);   
            curr = curr->lchild;   
        }   
        curr = S.top(); 
        // 當前節點的右孩子如果為空或者已經被訪問，則訪問當前節點 
        if(curr->rchild == NULL || curr->rchild == previsited)   
        {   
            cout<<curr->data<<"  ";   
            previsited = curr;   
            S.pop();   
            curr = NULL;   
        }   
        else 
            curr = curr->rchild;      // 否則訪問右孩子 
    }   
} 
 
void PostOrder_Nonrecursive(BiTree T)  // 後序遍歷的非遞歸    雙棧法 
{   
    stack<BiTree> s1 , s2;   
    BiTree curr ;          // 指向當前要檢查的節點 
    s1.push(T); 
    while(!s1.empty())  // 棧空時結束   
    { 
        curr = s1.top(); 
        s1.pop(); 
        s2.push(curr); 
        if(curr->lchild) 
            s1.push(curr->lchild); 
        if(curr->rchild) 
            s1.push(curr->rchild); 
    } 
    while(!s2.empty()) 
    { 
        printf("%c ", s2.top()->data); 
        s2.pop(); 
    } 
} 
 
 
int visit(BiTree T) 
{ 
    if(T) 
    { 
        printf("%c ",T->data); 
        return 1; 
    } 
    else 
        return 0; 
} 
 
void LeverTraverse(BiTree T)  //方法一、非遞歸層次遍歷二叉樹 
{ 
    queue <BiTree> Q; 
    BiTree p; 
    p = T; 
    if(visit(p)==1) 
        Q.push(p); 
    while(!Q.empty()) 
    { 
        p = Q.front(); 
        Q.pop(); 
        if(visit(p->lchild) == 1) 
            Q.push(p->lchild); 
        if(visit(p->rchild) == 1) 
            Q.push(p->rchild); 
    } 
} 
void LevelOrder(BiTree BT)    //方法二、非遞歸層次遍歷二叉樹 
{ 
    BiTNode *queue[10];//定義隊列有十個空間 
    if (BT==NULL) 
        return; 
    int front,rear; 
    front=rear=0; 
    queue[rear++]=BT; 
    while(front!=rear)//如果隊尾指針不等於對頭指針時 
    { 
        cout<<queue[front]->data<<"  ";  //輸出遍歷結果 
        if(queue[front]->lchild!=NULL)  //將隊首結點的左孩子指針入隊列 
        { 
            queue[rear]=queue[front]->lchild; 
            rear++;    //隊尾指針後移一位 
        } 
        if(queue[front]->rchild!=NULL) 
        { 
            queue[rear]=queue[front]->rchild;    //將隊首結點的右孩子指針入隊列 
            rear++;  //隊尾指針後移一位 
        } 
        front++;    //對頭指針後移一位 
    } 
} 
 
int depth(BiTNode *T)  //樹的深度 
{ 
    if(!T) 
        return 0; 
    int d1,d2; 
    d1=depth(T->lchild); 
    d2=depth(T->rchild); 
    return (d1>d2?d1:d2)+1; 
    //return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1; 
} 
int CountNode(BiTNode *T) 
{ 
    if(T == NULL) 
        return 0; 
    return 1+CountNode(T->lchild)+CountNode(T->rchild); 
} 
 
int main(void) 
{ 
    BiTNode *root=NULL; //定義一個根結點 
    int flag=1,k; 
    printf("                    本程序實現二叉樹的基本操作。\n"); 
    printf("可以進行建立二叉樹，遞歸先序、中序、後序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n"); 
 
    while(flag) 
    { 
        printf("\n"); 
        printf("|--------------------------------------------------------------|\n"); 
        printf("|                    二叉樹的基本操作如下:                    |\n"); 
        printf("|                        0.創建二叉樹                          |\n"); 
        printf("|                        1.遞歸先序遍歷                        |\n"); 
        printf("|                        2.遞歸中序遍歷                        |\n"); 
        printf("|                        3.遞歸後序遍歷                        |\n"); 
        printf("|                        4.非遞歸先序遍歷                      |\n"); 
        printf("|                        5.非遞歸中序遍歷                      |\n"); 
        printf("|                        6.非遞歸後序遍歷                      |\n"); 
        printf("|                        7.非遞歸層序遍歷                      |\n"); 
        printf("|                        8.二叉樹的深度                        |\n"); 
        printf("|                        9.二叉樹的結點個數                    |\n"); 
        printf("|                        10.退出程序                            |\n"); 
        printf("|--------------------------------------------------------------|\n"); 
        printf("                        請選擇功能："); 
        scanf("%d",&k); 
        switch(k) 
        { 
        case 0: 
            printf("請建立二叉樹並輸入二叉樹的根節點："); 
            CreateBiTree(&root); 
            break; 
        case 1: 
            if(root) 
            { 
                printf("遞歸先序遍歷二叉樹的結果為："); 
                PreOrder(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 2: 
            if(root) 
            { 
                printf("遞歸中序遍歷二叉樹的結果為："); 
                InOrder(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 3: 
            if(root) 
            { 
                printf("遞歸後序遍歷二叉樹的結果為："); 
                PostOrder(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 4: 
            if(root) 
            { 
                printf("非遞歸先序遍歷二叉樹："); 
                PreOrder_Nonrecursive1(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 5: 
            if(root) 
            { 
                printf("非遞歸中序遍歷二叉樹："); 
                InOrderTraverse1(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 6: 
            if(root) 
            { 
                printf("非遞歸後序遍歷二叉樹："); 
                PostOrder_Nonrecursive(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 7: 
            if(root) 
            { 
                printf("非遞歸層序遍歷二叉樹："); 
                //LeverTraverse(root); 
                LevelOrder(root); 
                printf("\n"); 
            } 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 8: 
            if(root) 
                printf("這棵二叉樹的深度為：%d\n",depth(root)); 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        case 9: 
            if(root) 
                printf("這棵二叉樹的結點個數為：%d\n",CountNode(root)); 
            else 
                printf("          二叉樹為空！\n"); 
            break; 
        default: 
            flag=0; 
            printf("程序運行結束，按任意鍵退出！\n"); 
        } 
    } 
    system("pause"); 
    return 0; 
}

運行效果圖如下：

分別輸入：

1

2

4

#

#

5

#

#

3

6

#

#

7

#

# 

就可以構造如下圖所示的二叉樹了。。

後序遍歷非遞歸的另外一種寫法：

/*
後序遍歷由於遍歷父節點是在遍歷子節點之後，而且左節點和右節點遍歷後的行為不一樣，
所以需要用變量來記錄前一次訪問的節點，根據前一次節點和現在的節點的關系來確定具體執行什麼操作
*/
void Postorder(BiTree T)
{
 if(T == NULL)
  return ;
 stack<BiTree> s;
 BiTree prev = NULL , curr = NULL;
 s.push(T);
 while(!s.empty())
 {
  curr = s.top();
  if(prev == NULL  || prev->lchild == curr || prev->rchild == curr)
  {
   if(curr->lchild != NULL)
    s.push(curr->lchild);
   else if(curr->rchild != NULL)
    s.push(curr->rchild);
  }
  else if(curr->lchild == prev)
  {
   if(curr->rchild != NULL)
    s.push(curr->rchild);
  }
  else
  {
   cout<<curr->data;
   s.pop();
  }
  prev = curr;
 }
}

輸入二叉樹中的兩個節點，輸出這兩個結點在樹中最低的共同父節點。
思路：遍歷二叉樹，找到一條從根節點開始到目的節點的路徑，然後在兩條路徑上查找共同的父節點。

// 得到一條從根節點開始到目的節點的路徑
bool GetNodePath(TreeNode *pRoot , TreeNode *pNode , vector<TreeNode *> &path)
{
 if(pRoot == NULL)
  return false;
 if(pRoot == pNode)
  return true;
 else if(GetNodePath(pRoot->lchild , pNode , path) )
 {
  path.push_back(pRoot->lchild);
  return true;
 }
 else if(GetNodePath(pRoot->rchild , pNode , path) )
 {
  path.push_back(pRoot->rchild);
  return true;
 }
 return false;
}
TreeNode *GetLastCommonNode(const vector<TreeNode *> &path1 , const vector<TreeNode *> &path2)
{
 vector<TreeNode *>::const_iterator iter1 = path1.begin();
 vector<TreeNode *>::const_iterator iter2 = path2.begin();
 TreeNode *pLast;
 while(iter1 != path1.end() && iter2 != path2.end() )
 {
  if(*iter1 == *iter2)
   pLast = *iter1;
  else
   break;
  iter1++;
  iter2++;
 }
 return pLast;
}
TreeNode *GetLastCommonParent(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2)
{
 if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
  return  NULL;
 vector<TreeNode *> path1;
 GetNodePath(pRoot , pNode1 , path1);

 vector<TreeNode *> path2;
 GetNodePath(pRoot , pNode2 , path2);
 return GetLastCommonNode(path1 , path2);
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm