1 #include<cstdio>
 2 #include <iostream>
 3 #include<cstring>
 4 #define size 50
 5 using namespace std;
 6 typedef struct BitNode
 7 {
 8     char Data;
 9     struct BitNode* lchild, * rchild;
10 }BitNode,*Bitnode1;
11 /*************二叉树的非递归遍历，要理解递归的原理******************/
12 //栈的建立
13 typedef struct Stack {
14     Bitnode1 Tree[size];
15     int top;
16 }Stack;
17 void InitStack(Stack& S)
18 {
19     S.top = 0;
20 }
21 void Push(Stack& S, Bitnode1 T)
22 {
23     S.Tree[S.top++] = T;
24 }
25 void Pop(Stack& S, Bitnode1& T)
26 {
27     T = S.Tree[--S.top];
28 }
29 bool IsEmpty(Stack& S)
30 {
31     if (S.top == 0) return 1;
32     return 0;
33 }
34 //二叉树的创建；
35 void CreatorderTree(Bitnode1& T)
36 {
37     char ch[size];
38     int i = 0;
39     cin >> ch;
40     if (ch[i] == ‘*‘)
41         T = NULL;
42     else
43     {
44         T = new BitNode;
45         T->Data = ch[i++];
46         CreatorderTree(T->lchild);
47         CreatorderTree(T->rchild);
48     }
49 }
50 void Visit(Bitnode1 T)
51 {
52     cout << T->Data << ‘ ‘;
53 }
54 //非递归遍历二叉树
55 void PreOreder(Bitnode1& T,Stack& S)
56 {
57     Bitnode1 P = T;
58     while (P || !IsEmpty(S))
59     {
60         if (P) {
61             Visit(P); Push(S, P);
62             P = P->lchild;
63         }
64         else {
65             Pop(S, P);
66             P = P->rchild;
67         }
68     }
69 }
70 int main()
71 {
72     BitNode* T;
73     Stack S;
74     InitStack(S);
75     CreatorderTree(T);
76     PreOreder(T, S);
77     cout << endl;
78     return 0;
79 }