【问题描述】 给出一个按照先序遍历得出的字符串，'#' 代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并采用非递归的先序、中序、后序遍历 的算法分别输出每一个非空节点。
【输入形式】输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。
【输出形式】 共有三行，每一行包含一串字符，表示分别按非递归的先序、中序、后序遍历得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。
【样例输入】 ABC##DE#G##F###
【样例输出】
A B C D E G F
C B E G D F A
C G E F D B A
#include<bits/stdc++.h> using namespace std; #define N 20 typedef struct Tree{ char data; struct Tree *LeftChild; struct Tree *RightChild; }BiTNode, *BiTree; BiTree CreateTree(){ BiTree tree; char ch; cin>>ch; if(ch=='#'){return NULL;} else{ tree=(BiTree)malloc(sizeof(BiTNode)); tree->data=ch; tree->LeftChild=CreateTree(); tree->RightChild=CreateTree(); return tree;//在这里return } } void NPreOrder(BiTree bt){ BiTree *s;//相当于 BiTNode**s BiTree p; int top=-1; //创建栈 s=(BiTree*)malloc((N+1)*sizeof(BiTree)); s[++top]=bt;//s[0]=bt top=0 while(top!=-1){ p=s[top--]; cout<<p->data;//输出s[top] top再--(第一次是直接输出s[0],top=-1了) if(p->RightChild){ s[++top]=p->RightChild;//让新的二叉树节点进栈，得是先++top(第一次top=-1了都)(s[0]=新的) } if(p->LeftChild){ s[++top]=p->LeftChild;//这里 必须先是右节点进栈 再是左节点进栈 自己想一下 } } } void YPreOrder(BiTree bt){ //前序递归遍历中左右 if(bt){ cout<<bt->data; YPreOrder(bt->LeftChild); YPreOrder(bt->RightChild);//这里就是先递归左孩子再是右孩子了 } } void NInOrder(BiTree bt){ BiTree *s; BiTree p,q; s=(BiTree*)malloc((N+1)*sizeof(BiTree)); int top=-1;//top==-1就是栈空的意思 if(bt){ while(bt){ s[++top]=bt; bt=bt->LeftChild; } //左子树全部进栈(到最左的叶子节点了) while(top!=-1){//栈不空 p=s[top--];//取出栈顶元素(其实就是左下角的树节点) cout<<p->data; while(p->RightChild){//看看这个节点是否有右孩子 q=p->RightChild; s[++top]=q;//有则赋给q 进栈 while(q->LeftChild){ //颗颗q有没有左孩子 s[++top]=q->LeftChild; q=q->LeftChild; } break;//while语句里的break就是直接跳出这个while循环 所以接下来就是看这个q有没有右孩子( 看上面的qwhile 有左孩子的话那也全进栈了 ) } } } } void YInOrder(BiTree bt){ if(bt){ YInOrder(bt->LeftChild); cout<<bt->data; YInOrder(bt->RightChild); } } /* 后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点， 而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点， 如果从左子树回退到根节点，此时就应该去访问右子树， 而如果从右子树回退到根节点，此时就应该访问根节点。 所以相比前序和后序，必须得在压栈时添加信息， 以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作 */ void NPostOrder(BiTree bt){ BiTree *s; BiTree p,q; q=NULL; s=(BiTree*)malloc((N+1)*sizeof(BiTree)); int top=-1; while(bt!=NULL||top!=-1){ if(bt){ s[++top]=bt; bt=bt->LeftChild; }//这个if在这里是可以的(对比while) 也遍历完左边的树节点了啊 因为if满足不会执行下面的else语句 就会一直执行if else{ bt=s[top];//先把栈顶元素拿出来试探一下 if(bt->RightChild==NULL||bt->RightChild==q){//无右孩子或者右孩子已经遍历过了 cout<<bt->data; q=bt;//保存到q，为下一次已处理节点前驱 top--; bt=NULL; /*bt是一直用来动的节点，这个最后赋值为空的目的是 已知在这个条件下，该去访问中间节点了， 如何访问呢，只能往回走，就是看看栈的情况，怎么看栈的情况，只能满足第二个条件不满第一个*/ } else{//正经遍历右节点 bt=bt->RightChild; } } } } void YPostOrder(BiTree bt){ if(bt){ YInOrder(bt->LeftChild); YInOrder(bt->RightChild); cout<<bt->data; } } int main(){ BiTree pt; cout<<"创建二叉树"<<endl; pt=CreateTree(); cout<<"前序非递归遍历："<<endl; NPreOrder(pt); cout<<endl; cout<<"前序递归遍历"<<endl; YPreOrder(pt); cout<<endl; cout<<"中序非递归遍历:"<<endl; NInOrder(pt); cout<<endl; cout<<"中序递归遍历:"<<endl; YInOrder(pt);cout<<endl; cout<<"后序非递归遍历"<<endl; NPostOrder(pt);cout<<endl; cout<<"后序递归遍历"<<endl; YPostOrder(pt);cout<<endl; }