本文共 4533 字，大约阅读时间需要 15 分钟。
基于hdu1662改的二叉树（www.cnblogs.com/general10/p/5856794.html）
非递归遍历忘记打了 回头补上……
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define M(a,b) memset(a,b,sizeof(a)) 12 using namespace std; 13 typedef long long ll; 14 const int inf=0x3f3f3f3f; 15 queue ans; 16 struct Binary_Tree //二叉树 17 { 18 int value; 19 Binary_Tree *lchild,*rchild; 20 Binary_Tree() 21 { 22 value=0; 23 lchild=rchild=NULL; 24 } 25 }; 26 27 bool add(Binary_Tree *&Root,char *s,int value) //向二叉树中加入点 28 { 29 if(Root==NULL) 30 Root=new Binary_Tree(); 31 if(*s=='\0') 32 { 33 if(Root->value!=0) 34 { 35 return false; 36 } 37 Root->value=value; 38 return true; 39 } 40 if(*s=='L') //寻找路径 41 { 42 return add(Root->lchild,s+1,value); 43 } 44 else if(*s=='R') 45 { 46 return add(Root->rchild,s+1,value); 47 } 48 return false; 49 } 50 51 //bool add(Binary_Tree *&Root,int num,int value){ //向完全二叉树中加入点 52 // if(Root==NULL) 53 // { 54 // Root=new Binary_Tree(); 55 // Root->value=value; 56 // return true; 57 // } 58 // if(num==0||num==1) //根据序号判断左右孩子 59 // { 60 // if(num) 61 // (Root->rchild)->value=value; 62 // else 63 // (Root->lchild)->value=value; 64 // return true; 65 // } 66 // if(num%2==0) //寻找路径 67 // { 68 // return add(Root->lchild,num/2,value); 69 // } 70 // else 71 // { 72 // return add(Root->rchild,num/2+1,value); 73 // } 74 // return false; 75 //} 76 77 void Delete(Binary_Tree *Root) //删除二叉树 78 { 79 if(Root==NULL) return ; 80 Delete(Root->lchild); 81 Delete(Root->rchild); 82 delete Root; 83 } 84 bool bfs(Binary_Tree *Root) //层次遍历 85 { 86 Binary_Tree *q[260]; //数组模拟队列 87 int front=0; 88 int rear=1; 89 q[0]=Root; 90 while (front value) //没有值就返回false 94 { 95 return false; 96 } 97 ans.push(temp->value); //当前节点入ans队 98 if(temp->lchild) //左孩子入队 99 {100 q[rear++]=temp->lchild;101 }102 if(temp->rchild) //右孩子入队103 {104 q[rear++]=temp->rchild;105 }106 }107 return true;108 }109 110 bool preorder(Binary_Tree *Root) //递归先序遍历二叉树111 {112 if(Root==NULL)113 {114 return false;115 }116 ans.push(Root->value);117 preorder(Root->lchild);118 preorder(Root->rchild);119 return true;120 }121 122 bool midorder(Binary_Tree *Root) //递归中序遍历二叉树123 {124 if(Root==NULL)125 {126 return false;127 }128 midorder(Root->lchild);129 ans.push(Root->value);130 midorder(Root->rchild);131 return true;132 }133 134 bool inorder(Binary_Tree *Root) //递归后序遍历二叉树135 {136 if(Root==NULL)137 {138 return false;139 }140 inorder(Root->lchild);141 inorder(Root->rchild);142 ans.push(Root->value);143 return true;144 }145 146 int main()147 {148 Binary_Tree *Root=NULL;149 char s[50];150 bool no=false;151 while(true)152 {153 no=false;154 Delete(Root);155 Root=NULL; //二叉树初始化156 while(true)157 {158 if(scanf("%s",s)==EOF) //读入159 {160 return 0;161 }162 if(strcmp(s,"()")==0)163 {164 break;165 }166 int val;167 char loc[10];168 strcpy(loc,"");169 sscanf(&s[1],"%d",&val);170 char *start=strchr(s,',')+1;171 sscanf(start,"%[A-Z]",&loc);172 if(!add(Root,loc,val))173 {174 no=true;175 }176 }177 // int n; //建立完全二叉树178 // scanf("%d",&n); //输入二叉树层数179 // int num=(int)(pow(2,n)+0.5)-1;180 // int sum=0;181 // while(num!=sum)182 // {183 // int value;184 // scanf("%d",&value);185 // sum++;186 // add(Root,sum,value);187 // }188 string str;189 while(cin>>str)190 {191 if(str=="end") break;192 if(str=="front")193 {194 preorder(Root);195 while(!ans.empty())196 {197 int ll=ans.front();198 ans.pop();199 printf("%d%c",ll,ans.empty()?'\n':' ');200 }201 }202 if(str=="middle")203 {204 midorder(Root);205 while(!ans.empty())206 {207 int ll=ans.front();208 ans.pop();209 printf("%d%c",ll,ans.empty()?'\n':' ');210 }211 }212 if(str=="back")213 {214 inorder(Root);215 while(!ans.empty())216 {217 int ll=ans.front();218 ans.pop();219 printf("%d%c",ll,ans.empty()?'\n':' ');220 }221 }222 if(str=="bfs")223 {224 bfs(Root);225 while(!ans.empty())226 {227 int ll=ans.front();228 ans.pop();229 printf("%d%c",ll,ans.empty()?'\n':' ');230 }231 }232 }233 /* if(no)234 {235 puts("not complete");236 }237 else238 {239 if(!bfs(Root))240 puts("not complete");241 else242 {243 while(!ans.empty())244 {245 int ll=ans.front();246 ans.pop();247 printf("%d%c",ll,ans.empty()?'\n':' ');248 }249 }250 }*/251 }252 return 0;253 }254 /*255 256 (11,LL) (7,LLL) (8,R)257 (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()258 259 (3,L) (4,R) ()260 261 262 263 5264 4 8265 11 13 4266 7 2 1267 268 */
转载于:https://www.cnblogs.com/general10/p/6114396.html