二叉树的非递归遍历C语言实现

腾讯面试中被问到二叉树的非递归遍历实现,当时记得不太清楚,回来专门复习了非递归的实现,整理代码如下:

[cpp]

  1. //采用二叉链表存储方式的二叉树,非递归中序遍历C语言实现代码  
  2. #include<stdio.h>  
  3. #include <malloc.h>  
  4. //函数结果状态代码  
  5. #define TRUE 1  
  6. #define FALSE 0  
  7. #define OK 1  
  8. #define ERROR 0  
  9. #define INFEASIBLE -1  
  10. #define OVERFLOW -2  
  11. //Status是函数的类型,其值是函数结果状态代码  
  12. typedef int Status;  
  13.   
  14. #define STACK_INIT_SIZE 10  
  15. #define STACKINCREMENT 2  
  16.   
  17. typedef struct BiTNode{  
  18.     int data;  
  19.     struct BiTNode *lchild,*rchild;  
  20. }BiTNode,*BiTree;  
  21.   
  22. typedef struct{  
  23.     BiTree *base;  
  24.     BiTree *top;  
  25.     int stacksize;  
  26. }SqStack;  
  27.   
  28. Status InitStack(SqStack *S)  
  29. {  
  30.     /* 构造一个空栈S */  
  31.     (*S).base = (BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));  
  32.     if(!(*S).base)  
  33.         exit(OVERFLOW);      /* 存储分配失败 */  
  34.     (*S).top = (*S).base;  
  35.     (*S).stacksize = STACK_INIT_SIZE;  
  36.     return OK;  
  37. }  
  38.   
  39. Status StackEmpty(SqStack S)  
  40. {  
  41. /* 若栈S为空栈,则返回TRUE,否则返回FALSE */  
  42.     if(S.top==S.base)  
  43.         return TRUE;  
  44.     else  
  45.         return FALSE;  
  46. }  
  47. int StackLength(SqStack S)  
  48. {  
  49.     /* 返回S的元素个数,即栈的长度 */  
  50.     return S.top-S.base;  
  51. }  
  52.   
  53. Status GetTop(SqStack S,BiTree *e)  
  54. {  
  55.     /* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */  
  56.     if(S.top>S.base)  
  57.     {  
  58.         *e = *(S.top-1);  
  59.         return OK;  
  60.     }  
  61.     else  
  62.         return ERROR;  
  63. }  
  64. Status Push(SqStack *S,BiTree e)  
  65. {  
  66.     if((*S).top-(*S).base>=(*S).stacksize)/*栈满,追加存储空间*/  
  67.     {  
  68.         (*S).base = (BiTree *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(BiTree));  
  69.         if(!(*S).base)  
  70.             exit(OVERFLOW);  
  71.         (*S).top = (*S).base + (*S).stacksize;  
  72.         (*S).stacksize += STACKINCREMENT;  
  73.     }  
  74.     *((*S).top)++=e;  
  75.     return OK;  
  76. }  
  77. Status Pop(SqStack *S,BiTree *e)  
  78. {  
  79.     /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */  
  80.    if((*S).top==(*S).base)  
  81.        return ERROR;  
  82.    *e=*–(*S).top;  
  83.    return OK;  
  84. }  
  85.   
  86. /*按前序输入二叉树中结点的值*/  
  87. /*#表示空树,构造二叉链表表示二叉树T*/  
  88. void CreateBiTree(BiTree *T) //输入前序序列1,2,3方法为1 2 0 0 3 0 0  
  89. {  
  90.     int data;  
  91.     scanf(“%d”,&data);  
  92.     if(data == 0)  
  93.         *T = NULL;  
  94.     else  
  95.     {  
  96.         *T = (BiTree)malloc(sizeof(BiTNode));  
  97.         if(!*T)  
  98.             exit(OVERFLOW);  
  99.         (*T)->data = data;  
  100.         CreateBiTree(&(*T)->lchild);  
  101.         CreateBiTree(&(*T)->rchild);  
  102.     }  
  103. }  
  104.   
  105. Status Visit(int e)  
  106. {  
  107.     printf(“%d “,e);  
  108.     return OK;  
  109. }  
  110. //中序非弟归遍历二叉树(二叉链表存储)  
  111. Status InOrderTraverse(BiTree T,Status (*Visit)(int)){  
  112.     SqStack S;  
  113.     BiTree p = T;  
  114.     InitStack(&S);  
  115.     while(p || !StackEmpty(S)){  
  116.         if(p){  
  117.             Push(&S,p);  
  118.             p = p->lchild;  
  119.         }  
  120.         else  
  121.         {  
  122.             Pop(&S,&p);  
  123.             if(!Visit(p->data))  
  124.                 return ERROR;  
  125.             p = p->rchild;  
  126.         }  
  127.     }  
  128.     return OK;  
  129. }  
  130.   
  131. void main()  
  132. {  
  133.     BiTree T;  
  134.     CreateBiTree(&T);  
  135.     InOrderTraverse(T,Visit);  
  136. }  

标签