做个网站商城要多少钱,怎么查看一个网站的建设地区,兰州网络推广方案,seo推广的特点题目#xff1a;
例#xff1a;输入一棵二叉树#xff0c;你的任务是按从上到下#xff0c;从左到右的顺序输出每一个节点的值。每个节点都按照从根节点到它的移动序列给出(L表示左#xff0c;R表示右)。在输入中#xff0c;每个节点的左括号和右括号之间没有空格#…题目
例输入一棵二叉树你的任务是按从上到下从左到右的顺序输出每一个节点的值。每个节点都按照从根节点到它的移动序列给出(L表示左R表示右)。在输入中每个节点的左括号和右括号之间没有空格相邻节点之间用一个空格隔开。每课树的输入用一对空括号“()”结束(这对括号本身不代表任何节点)。注意如果从根到某个节点的路径上有的节点没有在输入的中给出或者给出超过一次输出not complete。节点个数不超过256个。 样例输入 (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
样例输出 5 4 8 11 13 4 7 2 1
-1
分析与解答
1.整体来说需要输入建立结点将其组织成一棵树利用bfs队列进行层次遍历输出 2.二叉树结点定义一个结点树根的值左子树(还是结点类型)右子树。递归定义每次需要新node调用newnode 3.数据填到树上从根开始按照输入往左往右走如果目标不存在调用newnode 4.按层次顺序遍历每次取出一个结点把他左右子节点放进队列取出q.front放到输出序列vector里 5.遍历vector输出即可 6.为了防止内存被浪费需要在下一组数据前释放本组数据生成的二叉树
// UVa122 Trees on the level
#includecstdio
#includecstdlib
#includecstring
#includevector
#includequeue
using namespace std;const int maxn 256 10;struct Node{//二叉树的结点定义 bool have_value;//是否被赋值过 int v;//结点值 Node* left, *right;Node():have_value(false),left(NULL),right(NULL){}//构造函数
};Node* root;//二叉树的根结点 Node* newnode() { return new Node(); }//需要node就申请一个新的node bool failed;
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 true;// 做标记
}void remove_tree(Node* u) {//释放二叉树的代码 if(u NULL) return;//提前判断 remove_tree(u-left);//释放左子树空间 remove_tree(u-right);// 释放右子树空间 delete u;//调用析构函数释放u结点本身内存
}char s[maxn];//保存读入结点 bool read_input() {failed false;remove_tree(root);//释放上一棵二叉树 root newnode();//创建根节点 for(;;) {if(scanf(%s, s) ! 1) return false;//整个输入结束 if(!strcmp(s, ())) break;//读到结束标志退出循环 int v;sscanf(s[1], %d, v);//读入结点值 addnode(v, strchr(s, ,)1);//查找逗号然后插入结点 }return true;
}bool bfs(vectorint ans) {//按层次顺序遍历树 queueNode* 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() {vectorint ans;while(read_input()) {if(!bfs(ans)) failed 1;if(failed) printf(not complete\n);else {for(int i 0; i ans.size(); i) {if(i ! 0) printf( );printf(%d, ans[i]);}printf(\n);}}return 0;
}
