1 #include2 #include 3 4 using namespace std; 5 6 //本文用前序遍历、中序遍历、后序遍历实现二叉树的建立，再用三种遍历方法实现遍历输出 7 8 //构建节点的数据结构 9 typedef struct BiNode 10 { 11 char data; 12 struct BiNode *lchild,*rchild; 13 }BiNode,*BiTree; 14 15 /* 16 //构建节点的数据结构 17 typedef struct BiNode 18 { 19 char data; 20 struct BiNode lchild,rchild; //这里写成这样子是不对的，因为还没有定义完成BiNode结构体，并不知道给lchild分配多少空间，所以会报错， 21 但是如果像上面一样定义指针的话，不需要分配空间，所以不会报错 22 }BiNode,*BiTree; 23 */ 24 25 //前序遍历方式创建二叉树 26 //void createPreBst(BiTree T) 这里这样子写会出现错误，因为值传递和地址传递和引用传递的区别。 27 28 void createPreBst(BiTree &T) //指针的值改变，之后就会被释放，应该改变指针的地址。 这里可以是引用也可以是指针 29 { 30 char inPut; 31 scanf("%c",&inPut); 32 if(inPut == '#') 33 { 34 T = NULL; 35 } 36 else 37 { 38 T = (BiTree)malloc(sizeof(BiNode)); 39 if(T == NULL) 40 exit(OVERFLOW); 41 42 T->data = inPut; 43 createPreBst(T->lchild); 44 createPreBst(T->rchild); 45 } 46 } 47 48 /* 这里面是不对的，不能仅仅用简单的交换来达到中序和后序的实现！！ 49 //中序遍历方式创建二叉树 50 void createInBst(BiTree &T) 51 { 52 char inPut; 53 scanf("%c",&inPut); 54 if(inPut == '#') 55 { 56 T = NULL; 57 } 58 else 59 { 60 T = (BiTree)malloc(sizeof(BiNode)); 61 if(T == NULL) 62 exit(OVERFLOW); 63 64 65 66 createInBst(T->lchild); 67 T->data = inPut; 68 createInBst(T->rchild); 69 } 70 } 71 72 73 74 void createPostBst(BiTree &T) 75 { 76 char inPut; 77 scanf("%c",&inPut); 78 if(inPut == '#') 79 { 80 T = NULL; 81 } 82 83 if(T==NULL) 84 T = (BiTree)malloc(sizeof(BiNode)); 85 //if(T == NULL) 86 // exit(OVERFLOW); 87 88 89 createPostBst(T->lchild); 90 createPostBst(T->rchild); 91 T->data = inPut; 92 93 } 94 */ 95 96 97 //前序遍历方式输出（递归法） 98 99 void preOrder(BiTree T)100 {101 if(T == NULL)102 {103 return;104 }105 printf("%c ", T->data);106 preOrder(T->lchild);107 preOrder(T->rchild);108 }109 110 //前序遍历方式输出（非递归法） 用一个栈来实现111 void preOrder01(BiTree T)112 {113 stack sta;114 if( T == NULL)115 {116 return;117 }118 //while(T || sta.empty() != 0) 这里的empty的值不能是零，empty() 堆栈为空则返回真119 while(T || sta.empty() != true)120 {121 while(T)122 {123 sta.push(T);124 printf("%c",T->data);125 T = T->lchild;126 }127 128 T = sta.top();129 sta.pop();130 T = T->rchild;131 }132 133 }134 135 //中序遍历方式输出（递归法）136 void inOrder(BiTree T)137 {138 if(T == NULL)139 {140 return;141 }142 143 inOrder(T->lchild);144 printf("%c ", T->data);145 inOrder(T->rchild);146 }147 148 //中序遍历方式输出（非递归法） 149 void inOrder02(BiTree T)150 {151 if(T == NULL)152 {153 return;154 }155 stack sta;156 157 //while(T || sta.empty() != 0) 这里的empty的值不能是零，empty() 堆栈为空则返回真158 while(T || sta.empty() != true)159 {160 while(T)161 {162 sta.push(T);163 T = T->lchild;164 }165 166 T = sta.top();167 printf("%c" , T->data);168 sta.pop();169 T = T->rchild ;170 }171 172 }173 174 //后序遍历方式输出（递归法）175 void postOrder(BiTree &T)176 {177 if(T == NULL)178 {179 return;180 }181 182 postOrder(T->lchild);183 postOrder(T->rchild);184 printf("%c ", T->data);185 }186 187 //后序遍历方式输出（非递归法） 用两个栈实现188 void postOrder02(BiTree T)189 {190 stack sta;191 stack sta2;192 if( T == NULL)193 {194 return;195 }196 197 sta.push(T);198 while(sta.empty() != true)199 {200 T = sta.top();201 sta.pop();202 sta2.push(T);203 if(T->lchild != NULL)204 {205 sta.push(T->lchild);206 }207 if(T->rchild != NULL)208 {209 sta.push(T->rchild);210 }211 }212 213 while(sta2.empty() != true)214 {215 BiTree temp = sta2.top();216 cout<< temp->data <<' ';217 sta2.pop();218 }219 220 221 }222 //后序遍历方式输出（非递归法） 用1个栈实现223 //这里回退的时候，必须知道知否遍历过了，要有标识224 void postOrder03(BiTree T)225 {226 stack sta;227 228 if( T == NULL)229 {230 return;231 }232 233 sta.push(T);234 BiTree temp = T;235 while(sta.empty() != true)236 {237 T = sta.top();238 if(T->lchild != NULL && temp != T->lchild && temp != T->rchild) //if(T->lchild != NULL && temp != T->lchild ) 上面的如果不加另一个约束项会陷入无限的循环239 {240 sta.push(T->lchild);241 }242 else if (T->rchild != NULL && temp != T->rchild)243 {244 sta.push(T->rchild);245 }246 else247 {248 sta.pop();249 temp = T;250 cout<< T->data << ' ';251 }252 }253 254 }255 256 int main()257 {258 BiTree Tr;//259 //Tree->lchild = Tree->rchild = NULL; 加上这样子的句子 也不对260 //BiTree Tr = {'\0'};261 //Tr=(BiTree)malloc(sizeof(BiNode));262 createPreBst(Tr);263 postOrder02(Tr); //这种也会引发值传递和地址传递的情况，但是由于打印语句是在函数中，所以结果是对的，但是有隐患。264 system("pause");265 }
这里面有很多的盲点，比如stl中栈的empty（）返回的是真。
在结构体中不能声明结构体类型的变量，但可以声明结构体类型的指针（这个与分不分配内存有关系）