首页 > 代码库 > Uva 122 树的层次遍历 Trees on the level lrj白书 p149
Uva 122 树的层次遍历 Trees on the level lrj白书 p149
是否可以把树上结点的编号,然后把二叉树存储在数组中呢?很遗憾如果结点在一条链上,那将是2^256个结点
所以需要采用动态结构
- 首先要读取结点,建立二叉树addnode()+read_input()承担这样的工作
- 然后遍历二叉树,读取结点编号输出bfs()
这道题有内存池应用的背景
附链接 http://blog.csdn.net/shawngucas/article/details/6574863
#include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn=256+5; bool failed; char s[maxn]; struct Node{ bool have_value;//是否被赋值过 int v;//结点值 Node *left,*right; Node():have_value(false),left(NULL),right(NULL){}//构造函数 }; Node* root;//二叉树的根节点,指针类型给了,但是指针是空的 //如果要定义一棵二叉树,一般是要定义一个“结点”类型的struct(如叫Node), //然后保存树根的指针(Node *root) Node * newnode(){ return new Node(); } //程序动态申请内存,请注意内存泄漏 void remove_tree(Node *u){ //后序遍历 先递归地把当前结点的左子树删除 再递归地把当前结点的右子树删除完,最后考虑当前结点 if(u==NULL) return ; remove_tree(u->left); remove_tree(u->right); delete u; /* //前序遍历 delete u; remove_tree(u->left); remove_tree(u->right); //中序遍历 remove_tree(u->left); delete u; remove(u->right); */ } //addnode(11,"LL)") void addnode(int v,char* s){ int n=strlen(s); Node* u =root; for(int i=0;i<n;i++) if(s[i]==‘L‘){ //左子结点如果空建立新结点 if(u->left==NULL){ u->left=newnode(); } u=u->left; } else if(s[i]==‘R‘){ //右子结点如果空建立新结点 if(u->right==NULL){ u->right=newnode(); } u=u->right; } if (u->have_value) failed=true; //这里错了,先忍着,主函数再说 u->v=v; u->have_value=http://www.mamicode.com/true;"%s",s)!=1) return false;//!!整个输入结束 if(!strcmp(s,"()")) break; int v; sscanf(&s[1],"%d",&v);//(11,LL)对应11,LL) addnode(v,strchr(s,‘,‘)+1);//查找逗号,然后插入结点 } return true; } //包括用vector ans记录树结点编号的工作 bool bfs(vector <int> &ans){ queue<Node*> q; ans.clear(); q.push(root);//队列中初始只有一个根结点 while(!q.empty()){ Node* u=q.front();q.pop(); if(!u->have_value) return false; ans.push_back(u->v);//增加结点值到输出序列尾部 if(u->left!=NULL) q.push(u->left);//让左子结点进队(如果有的话) if(u->right!=NULL) q.push(u->right);//让右子结点进队(如果有的话) } return true; } int main(){ vector <int> ans; while(read_input()){ if(!bfs(ans)) failed=true;//最后一层判断输入是否正确 if(failed) printf("not complete\n"); else { for (int i=0;i<ans.size();i++){ printf(" "); printf("%d",ans[i]); } printf("\n"); } } return 0; }
Uva 122 树的层次遍历 Trees on the level lrj白书 p149
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。