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

2023-12-21 16:30:27

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

分类： 数据结构及算法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. }  
 ZT 二叉树先序，中序，后序遍历非递归实现


 

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

上一篇：Java重定向输出流实现程序日志


下一篇：Balanced Binary Tree