基于visual Studio2013解决面试题之0401非递归遍历二叉树

大灰狼



题目

解决代码及点评

• <pre code_snippet_id="110774" snippet_file_name="blog_20131213_1_9696279" class="cpp" name="code"><pre code_snippet_id="110774" snippet_file_name="blog_20131213_1_9696279" class="cpp" name="code"><pre code_snippet_id="110774" snippet_file_name="blog_20131213_1_9696279" class="cpp" name="code"><pre code_snippet_id="110774" snippet_file_name="blog_20131213_1_9696279" name="code" class="cpp"><pre code_snippet_id="110774" snippet_file_name="blog_20131213_1_9696279" name="code" class="cpp"></pre></pre><pre code_snippet_id="110774" snippet_file_name="blog_20131213_2_7776669" name="code" class="cpp">/*
•     非递归实现中序遍历二叉树
•     中序遍历概念：先访问左子树，然后再访问根节点，然后再访问右子树
•     用递归的方法非常简单，理解思想几行代码，但是不用递归该如何实现？
•     不用递归，则需要用栈来保存现场，要遍历左子树之前，将根节点压栈
•     再访问左子树，当该根节点要被弹出来时，说明左子树已经遍历完毕
•     以下代码只注释inOrder，其他类推即可
• */  
•   
•   
• #include <iostream>  
• #include <stack>  
• using namespace std;  
•   
• typedef struct BiTNode  
• {  
•     int nValue;  
•     struct BiTNode *pLChild;  
•     struct BiTNode *pRChild;  
• }BiTNode, *PBiTree;  
•   
• PBiTree Create()  
• {  
•     int nValue;  
•     PBiTree pRoot;  
•     scanf_s("%d", &nValue);  
•     if (nValue == 0)  
•     {  
•         pRoot = NULL;  
•     }  
•     else  
•     {  
•         pRoot = (PBiTree)malloc(sizeof(BiTNode));  
•         if (NULL == pRoot)  
•         {  
•             printf("分配内存失败!\n");  
•         }  
•         else  
•         {  
•             pRoot->nValue = nValue;  
•             printf("请输入%d结点的左子结点:", pRoot->nValue);  
•             pRoot->pLChild = Create();  
•   
•             printf("请输入%d结点的右子结点:", pRoot->nValue);  
•             pRoot->pRChild = Create();  
•         }  
•     }  
•     return pRoot;  
• }  
•   
• void Visit(PBiTree p)  
• {  
•     printf("%d ", p->nValue);  
• }  
•   
• void PreOrder(PBiTree pRoot)      
• {  
•     stack<PBiTree> pStack;  
•     PBiTree pCur = pRoot;  
•     while (pStack.size()>0||pCur!=NULL)  
•     {  
•         while (pCur!=NULL)//遍历到左边最下边  
•         {  
•             Visit(pCur);      //和中序相似，就是这一句位置不同  
•             pStack.push(pCur);  
•             pCur=pCur->pLChild;  
•         }  
•         if(pStack.size()>0)  
•         {  
•             pCur=pStack.top();  
•   
•             pStack.pop();  
•             pCur=pCur->pRChild;  
•   
•   
•         }  
•   
•     }  
• }  
•   
• //中序遍历  
• void InOrder(PBiTree pRoot)     
• {  
•     stack<PBiTree> pStack;  
•     PBiTree pCur = pRoot;  
•     while (pStack.size()>0 || pCur!=NULL)  
•     {  
•         // 通过这层循环，找到最左下边节点  
•         while (pCur!=NULL)//遍历到左边最下边  
•         {  
•             // 如果左儿子不是空，则压栈  
•             pStack.push(pCur);  
•             pCur=pCur->pLChild;  
•         }  
•   
•         // 将最左下的节点弹出并访问，然后将pCur指向最左下节点的右儿子，继续遍历  
•         if(pStack.size()>0)  
•         {  
•             // 访问栈顶的元素  
•             pCur=pStack.top();  
•             Visit(pCur);  
•   
•             // 弹出栈顶  
•             pStack.pop();  
•   
•             // 然后访问右子树  
•             pCur=pCur->pRChild;  
•         }  
•     }  
• }  
• void PostOrder(PBiTree pRoot)  
• {  
•   
•     stack<PBiTree> pStack;  
•     PBiTree pCur = pRoot;  
•   
•     while (pCur!=NULL)//遍历到左边最下边  
•     {  
•         pStack.push(pCur);  
•         pCur=pCur->pLChild;  
•     }  
•     while(pStack.size()>0)  
•     {  
•         PBiTree pLastVisit = pCur;  //判断当前该访问左节点还是右节点  
•   
•         pCur=pStack.top();  
•         pStack.pop();  
•   
•         //pStack.pop();  
•         if (pCur->pRChild==NULL||pCur->pRChild==pLastVisit)  
•         {  
•             Visit(pCur);  
•         }  
•         else if (pCur->pLChild==pLastVisit)  
•         {  
•             pStack.push(pCur);  
•             pCur=pCur->pRChild;  
•             pStack.push(pCur);  
•             while (pCur!=NULL)  
•             {  
•                 if (pCur->pLChild!=NULL)  
•                 {  
•                     pStack.push(pCur->pLChild);  
•                 }  
•                 pCur=pCur->pLChild;  
•             }  
•         }  
•   
•   
•   
•   
•   
•     }  
• }  
• int main()  
• {  
•     printf("请输入根结点的值:");  
•     PBiTree pRoot = Create();  
•   
•     printf("前序遍历:");  
•     PreOrder(pRoot);  
•     cout<<endl;  
•     printf("中序遍历:");  
•     InOrder(pRoot);  
•     cout<<endl;  
•     printf("后序遍历:");  
•     PostOrder(pRoot);  
•     cout<<endl;  
•   
•     system("pause");  
•     return 0;  
• }  
•   
• </pre><br><br></pre></pre></pre>  
  

代码下载及其运行

代码下载地址：http://download.csdn.net/detail/yincheng01/6704519

解压密码：c.itcast.cn

下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：

1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”

2）在下拉框中选择相应项目，项目名和博客编号一致

3）点击“本地Windows调试器”运行

程序运行结果