首页 > 其他 > 详细

ZT 二叉树先序，中序，后序遍历非递归实现

时间：2014-02-06 17:30:18      阅读：337      评论：0      收藏：0      [点我收藏+]

二叉树先序，中序，后序遍历非递归实现

分类： 数据结构及算法2012-04-28 14:30 8572人阅读 评论(6) 收藏 举报
structc

利用栈实现二叉树的先序，中序，后序遍历的非递归操作

[cpp] view plaincopy
  1. #include <stdio.h>  
  2. #include <malloc.h>  
  3. #include <stdlib.h>  
  4. #include <queue>  
  5. #include <stack>  
  6. #include <iostream>  
  7. using namespace std;  
  8. typedef struct BiTNode{  
  9.     char data;  
  10.     BiTNode *lchild, *rchild;  
  11. }BiTNode,*BiTree;  
  12.   
  13. void CreateBiTree(BiTree &T)//建树，按先序顺序输入节点  
  14. {  
  15.     char ch;  
  16.     scanf("%c",&ch);  
  17.     if(ch==‘ ‘)  
  18.     {  
  19.         T=NULL;  
  20.         return;  
  21.     }  
  22.     else  
  23.     {  
  24.         T=(BiTree)malloc(sizeof(BiTNode));  
  25.         if(!T)  
  26.             exit(1);  
  27.         T->data=ch;  
  28.         CreateBiTree(T->lchild);  
  29.         CreateBiTree(T->rchild);  
  30.     }  
  31. }  
  32. void InOrderTraverse(BiTree T)//非递归中序遍历  
  33. {  
  34.       
  35.     stack<BiTree> Stack;  
  36.     if(!T)  
  37.     {  
  38.         printf("空树！\n");  
  39.         return;  
  40.     }  
  41.       
  42.     while(T || !Stack.empty())  
  43.     {  
  44.         while(T)  
  45.         {  
  46.             Stack.push(T);  
  47.             T=T->lchild;  
  48.         }  
  49.         T=Stack.top();  
  50.         Stack.pop();  
  51.         printf("%c",T->data);  
  52.         T=T->rchild;  
  53.     }                                                                                                                                     
  54. }  
  55.   
  56.   
  57.   
  58. void PreOrderTraverse(BiTree T)//非递归先序遍历  
  59. {  
  60.       
  61.     stack<BiTree> Stack;  
  62.     if(!T)  
  63.     {  
  64.         printf("空树！\n");  
  65.         return;  
  66.     }  
  67.     while(T || !Stack.empty())  
  68.     {  
  69.         while(T)  
  70.         {  
  71.             Stack.push(T);  
  72.             printf("%c",T->data);  
  73.             T=T->lchild;  
  74.         }  
  75.         T=Stack.top();  
  76.         Stack.pop();          
  77.              T=T->rchild;          
  78.     }                                                                                                                                     
  79. }  
  80.   
  81.   
  82. void PostOrderTraverse(BiTree T)//非递归后序遍历,用一个标记标记右子树是否访问过  
  83. {  
  84.     int flag[20];  
  85.     stack<BiTree> Stack;  
  86.     if(!T)  
  87.     {  
  88.         printf("空树！\n");  
  89.         return;  
  90.     }  
  91.     while(T)  
  92.     {  
  93.         Stack.push(T);  
  94.         flag[Stack.size()]=0;  
  95.         T=T->lchild;  
  96.     }  
  97.     while(!Stack.empty())  
  98.     {  
  99.         T=Stack.top();            
  100.         while(T->rchild && flag[Stack.size()]==0)  
  101.         {  
  102.             flag[Stack.size()]=1;  
  103.             T=T->rchild;  
  104.             while(T)  
  105.             {  
  106.                 Stack.push(T);  
  107.                 flag[Stack.size()]=0;  
  108.                 T=T->lchild;  
  109.             }  
  110.         }  
  111.         T=Stack.top();  
  112.         printf("%c",T->data);  
  113.         Stack.pop();  
  114.     }                                                                                                                                     
  115. }  
  116. void main()  
  117. {  
  118.     
  119.     BiTree T;  
  120.     CreateBiTree(T);  
  121.     PreOrderTraverse(T);  
  122.     printf("\n");  
  123.          InOrderTraverse(T);  
  124.     printf("\n");  
  125.     PostOrderTraverse(T);  
  126.     printf("\n");  
  127. }  
 bubuko.com,布布扣


 

ZT 二叉树先序，中序，后序遍历非递归实现

原文：http://www.cnblogs.com/jeanschen/p/3538800.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！