1. /*
    2.     试写出先序遍历（非递归算法）
    3.     分析：
    4.         和中序遍历大同小异，唯一的差别在于每次先访问节点，在判断有没有左孩子，有则入栈，然后出栈，往右走。直至栈空。
    5. */
    6. struct biTree {//树的结构体
    7.     char data;
    8.     struct biTree *lchild;
    9.     struct biTree *rchild;
    10. };
    11. struct Stack {//栈的结构体
    12.     char* arr;    //内存首地址
    13.     int  len;    //栈的容量
    14.     int top;     //栈的下标
    15. };
    16. #include <stdio.h>
    17. #include <stdlib.h>
    18. void preOrder(biTree *T, Stack *s) {//先序遍历
    19.     biTree *p = T;
    20.     bool empty(Stack *);
    21.     bool push(Stack *, biTree *);
    22.     biTree *top(Stack *);
    23.     bool pop(Stack *);
    24.     while (p || !empty(s)) {
    25.         if (p) {//一路向左
    26.             printf("%c ", p->data);//打印当前元素
    27.             push(s, p);
    28.             p = p->lchild;
    29.         }
    30.         else {
    31.             p = top(s);
    32.             pop(s);//栈顶元素出栈
    33.             p = p->rchild;//向右寻找
    34.         }
    35.     }
    36. }
    37. int main() {
    38.     int count = 0;
    39.     struct biTree *T = (struct biTree *)malloc(sizeof(struct biTree));
    40.     struct Stack *s = (struct Stack*)malloc(sizeof(struct Stack));
    41.     biTree *create(biTree*);
    42.     void nodeNum(biTree *, int *);
    43.     Stack *createStack(int);
    45.     T = create(T);
    46.     nodeNum(T, &count);
    48.     s = createStack(count);//创建二叉树节点个数大小的栈
    50.     preOrder(T, s);
    51.     return 0;
    52. }
    53. //一名谦虚的学生