1. /*
    2.     是写出中序遍历的非递归算法
    3.     分析：
    4.         如果采用非递归，我们就需要用到栈这个数据结构了，具体流程为：从根节点一路往下找左孩子并将其入栈直至左孩子为空
    5.         然后依次出栈，并判断是否存在右孩子，如果有，右孩子入栈，继续往下找左孩子，如此重复直至栈空
    6. */
    7. struct biTree {//树的结构体
    8.     char data;
    9.     struct biTree *lchild;
    10.     struct biTree *rchild;
    11. };
    12. struct Stack {//栈的结构体
    13.     char* arr;    //内存首地址
    14.     int  len;    //栈的容量
    15.     int top;     //栈的下标
    16. };
    17. #include <stdio.h>
    18. #include <stdlib.h>
    19. void inOrder(biTree *T,Stack *s) {//中序遍历
    20.     biTree *p = T;
    21.     bool empty(Stack *);
    22.     bool push(Stack *,biTree * );
    23.     biTree *top(Stack *);
    24.     bool pop(Stack *);
    25.     while (p||!empty(s)) {
    26.         if (p) {//一路向左
    27.             push(s,p);
    28.             p = p->lchild;
    29.         }
    30.         else {
    31.             p = top(s);
    32.             printf("%c ",p->data);//打印栈顶元素
    33.             pop(s);//栈顶元素出栈
    34.             p = p->rchild;//向右寻找
    35.         }
    36.     }
    37. }
    38. int main() {
    39.     int count=0;//计数器，二叉树节点个数
    40.     struct biTree *T = (struct biTree *)malloc(sizeof(struct biTree));
    41.     struct Stack *s = (struct Stack*)malloc(sizeof(struct Stack));
    42.     biTree *create(biTree*);
    43.     void nodeNum(biTree *,int *);
    44.     Stack *createStack(int);
    46.     T = create(T);
    47.     nodeNum(T,&count);
    49.     s = createStack(count);//创建二叉树节点个数大小的栈
    51.     inOrder(T,s);
    52.     return 0;
    53. }