1 #include "stdafx.h"  2 #include<string>  3 #include<iostream>  4 #include<stack>  5   6 using namespace std;  7   8 struct BinaryTreeNode  9 { 10     int m_nValue; 11     BinaryTreeNode* m_pLeft; 12     BinaryTreeNode* m_pRight; 13 }; 14  15 void beforeTraverse(BinaryTreeNode *root) 16 { 17     if(root!=NULL) 18     { 19         cout<<root->m_nValue<<"  "; 20         beforeTraverse(root->m_pLeft); 21         beforeTraverse(root->m_pRight); 22     } 23 } 24  25 void PreOrder(BinaryTreeNode* pRoot) 26 {//迭代先序遍历 27     if (pRoot==NULL) 28         return; 29     std::stack<BinaryTreeNode*> S; 30     BinaryTreeNode *p=pRoot;   //二叉树分左右，所以光有栈不行，合理的运用遍历指针是关键之一 31     while(p!=NULL) 32     { 33         cout<<p->m_nValue<<"  "; 34         if (p->m_pRight!=NULL) 35             S.push(p->m_pRight); 36         if (p->m_pLeft!=NULL) 37             p=p->m_pLeft; 38         else 39         { 40             if (S.empty()) 41                 break; 42             p=S.top(); 43             S.pop(); 44         } 45     } 46 } 47  48  49  50  51 void midTraverse(BinaryTreeNode *root) 52 { 53     if(root!=NULL) 54     { 55         midTraverse(root->m_pLeft); 56         cout<<root->m_nValue<<"  "; 57         midTraverse(root->m_pRight); 58     } 59 } 60  61  62 void InOrder(BinaryTreeNode* pRoot) 63 {//迭代中序遍历 64     if (pRoot==NULL) 65         return; 66     std::stack<BinaryTreeNode*> S; 67     BinaryTreeNode *p=pRoot; 68     do  69     { 70         while(p!=NULL) 71         { 72             S.push(p); 73             p=p->m_pLeft; 74         } 75         //若进行到这里左子树为空 76         if (!S.empty())//Stack不空时退栈，然后访问该元素 77         { 78             p=S.top(); 79             cout<<p->m_nValue<<"  "; 80             S.pop(); 81             p=p->m_pRight; 82         } 83     } while (p!=NULL||!S.empty()); 84     //这里的p==NULL表示右子树为空，然后堆栈如果也空的话，才是处理完毕 85 } 86  87 void backTraverse(BinaryTreeNode *root) 88 { 89     if(root!=NULL) 90     { 91         backTraverse(root->m_pLeft); 92         backTraverse(root->m_pRight); 93         cout<<root->m_nValue<<"  "; 94     } 95 } 96  97 void PostOrder(BinaryTreeNode* pRoot) 98 { 99     if (pRoot==NULL)100         return;101     std::pair<BinaryTreeNode*,char> w;102     std::stack<std::pair<BinaryTreeNode*,char> > S;103     BinaryTreeNode *p=pRoot;      104     do 105     {106         while(p!=NULL)           //左子树经过节点加L进栈107         {108             w.first=p;109             w.second=‘L‘;110             S.push(w);111             p=p->m_pLeft;112         }113         bool continuel=true;     //继续循环标志，用于L改为R的时候就开始向右遍历114         while (continuel && !S.empty()) //用一个break语句也能实现循环标志continuel的功能115         {116             w=S.top();117             S.pop();118             p=w.first;119             if (w.second==‘L‘)  //标记为L表示左子树遍历完120             {121                 w.second=‘R‘;122                 S.push(w);123                 continuel=false;124                 p=p->m_pRight;125             }126             else127                 cout<<(p->m_nValue)<<"   ";      //如果标记为R，表示右子树遍历完128         }129     }while (!S.empty());130 }131 132 BinaryTreeNode* createTree(int *leftArr,int leftarrl,int leftarrr,int *midArr,int midarrl,int midarrr)133 {134     if(leftarrl<=leftarrr){135         BinaryTreeNode* root =new BinaryTreeNode;136         root->m_nValue= http://www.mamicode.com/leftArr[leftarrl];//取先序遍历的第一个元素作为根节点137         //取出这个结点以后..要在midArr里面找到这个节点138         int temIndex = -1;139 140         for(int i = midarrl;i<=midarrr;++i)141         {142             if(midArr[i]==leftArr[leftarrl])143             {144                 temIndex =i;145                 break;146             }147         }148         if(temIndex==-1)149         {150             cout<<"数据有误"<<endl;151             throw std::exception("valid data");152             153         }154         int lengthl = temIndex-midarrl;155         root->m_pLeft = createTree(leftArr,leftarrl+1,leftarrl+lengthl,midArr,midarrl,temIndex-1);156         root->m_pRight =createTree(leftArr,leftarrl+lengthl+1,leftarrr,midArr,temIndex+1,midarrr);157         return root;158 }159     else160     {161         return NULL;162     }163 }164 BinaryTreeNode* cTree(int *leftArr,int *midArr,int len)165 {166     return createTree(leftArr,0,len-1,midArr,0,len-1);167 }168 169 170 171 172 int _tmain(int argc, _TCHAR* argv[])173 {174     175     BinaryTreeNode *roots = new BinaryTreeNode;176     roots->m_nValue=http://www.mamicode.com/1;177     BinaryTreeNode *lchild = new BinaryTreeNode;178     lchild->m_nValue = http://www.mamicode.com/2;179     lchild->m_pLeft=lchild->m_pRight=NULL;180     BinaryTreeNode *rchild = new BinaryTreeNode;181     rchild->m_nValue = http://www.mamicode.com/3;182     rchild->m_pLeft=rchild->m_pRight=NULL;183     roots->m_pLeft = lchild;184     roots->m_pRight = rchild; 185 186     beforeTraverse(roots);187     cout<<endl;188     midTraverse(roots);189     cout<<endl;190     backTraverse(roots);191     cout<<endl;192 193     //下面根据先序和中序构建一棵树194     const int len = 8;195     int left[]={1,2,4,7,3,5,6,8};196     int mid[]={4,7,2,1,5,3,8,6};197     BinaryTreeNode *root;198     root = cTree(left,mid,len);199     200     cout<<"先序遍历:";201     beforeTraverse(root);202     cout<<endl;203     cout<<"迭代版先序遍历:";204     PreOrder(root);205     cout<<endl;206     cout<<"中序遍历:";207     midTraverse(root);208     cout<<endl;209     cout<<"迭代中序遍历:";210     InOrder(root);211     cout<<endl;212     cout<<"后序遍历:";213     backTraverse(root);214     cout<<endl;215     cout<<"迭代后序遍历:";216     PostOrder(root);217     cout<<endl;218     return 0;219 }