题外话: 考试的时候花了一个小时做了 27 分, 由于 Siblings 这个单词不知道意思, 所以剩下的 3 分就没去纠结了, 后来发现单词是兄弟的意思, 气哭~~
这道题的麻烦之处在于如何从一个字符串中去找数字. 先首先我们需要整行读取(包括空格), 这个我自己写另一个函数, 挺好用的:
- string mygets()
- {
- char str[100];
- fgets(str,sizeof(str),stdin);
- int len = strlen(str);
- if(str[len-1]=='\n') str[len-1] = '\0';
- return str;
- }
用的时候只要 string str = mygets(); 就可以了, 里面已经去掉换行符了.
下一步是再写一个从 istart 位置读取数字的函数, 先从 istart 位置读取字符串(遇到空格, 读取结束), 然后用 atoi 把字符串转换成数字.
- // 字符串中 istart 位置开始取某个单词(以空格结束)
- int getNum(string str,int istart)
- {
- int len = str.length();
- string strA="";
- for(int i=istart;i<len;++i)
- if(str[i]==' ') break;
- else strA += str[i];
- //printf("%s\n",strA.c_str());
- int a = atoi(strA.c_str());
- return a;
- }
题目中的字符串格式太多了是吧, 眼花缭乱:
- 15 is the root
- 8 and 2 are siblings
- 32 is the parent of 11
- 23 is the left child of 16
- 28 is the right child of 2
- 7 and 11 are on the same level
- It is a full tree
拿字符串 siblings 举例吧, 想用 find 函数 siblings 字符串, 如果返回不等于 - 1, 表示就是此种类型, 然后用以下代码获取数字 8 和 2. 注意 find 函数的用法, 返回的是查找字符串的首地址, 所以 find "of" 返回的是 o 出现的首地址, 没有找到 of 则返回 - 1, 否则返回 o 的首地址. 然后我们可以想象一下 istart+1 是 f,istart+2 是空格, istart+3 就是我们所要的数字出现的首地址.
- if(str.find("siblings")!=-1)
- {
- int a = getNum(str,0);
- int b = getNum(str,str.find("of")+3);
- }
以下是我的代码:
PS: 如果我的构树代码看不懂, 可以看我写的这篇文章让你懂得已知先序 (后序) 与中序遍历如何快速构树: https://www.cnblogs.com/jlyg/p/10402919.html
树的结构体中我加了 level 变量, 记录当前节点的水平深度. 其他看代码吧~~
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<vector>
- #include<queue>
- #include<map>
- #include<set>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- struct Node{
- int val;
- int level;
- Node* left;
- Node* right;
- Node(){
- left = right = NULL;
- level = 0;
- }
- };
- map<int,int> valtoid; // 通过值去找 id
- map<int,Node*> valtonode; // 通过值去找节点
- // 构造数
- Node* Insert(Node* node,int val)
- {
- if(node==NULL)
- {
- node = new Node();
- node->val= val;
- valtonode[val] = node;
- }
- else if(valtoid[val] <valtoid[node->val])
- {
- node->left = Insert(node->left,val);
- node->left->level = node->level+1;
- }
- else
- {
- node->right= Insert(node->right,val);
- node->right->level = node->level+1;
- }
- return node;
- }
- Node* root = NULL;
- int n;
- // 是不是满二叉树
- bool isFullTree(Node* root)
- {
- queue<Node*> q;
- q.push(root);
- Node* node;
- while(!q.empty())
- {
- node = q.front();
- q.pop();
- if(node->left)
- q.push(node->left);
- if(node->right)
- q.push(node->right);
- if(node->left&&!node->right || !node->left&&node->right)
- return false;
- }
- return true;
- }
- // 字符串中 istart 位置开始取某个单词(以空格结束)
- int getNum(string str,int istart)
- {
- int len = str.length();
- string strA="";
- for(int i=istart;i<len;++i)
- if(str[i]==' ') break;
- else strA += str[i];
- //printf("%s\n",strA.c_str());
- int a = atoi(strA.c_str());
- return a;
- }
- // 是不是兄弟节点
- bool isSiblings(Node* node,Node* child1,Node* child2)
- {
- if(node==NULL) return false;
- if(node->left==child1&&node->right!=child2||
- node->left==child2&&node->right!=child1) return false;
- else if(node->left==child1&&node->right==child2||
- node->left==child2&&node->right==child1) return true;
- return isSiblings(node->left,child1,child2)||isSiblings(node->right,child1,child2);
- }
- // 判断这一个这句话是不是对的
- bool isRight(string str)
- {
- if(str.find("root")!=-1)
- {
- int a = getNum(str,0);
- return a == root->val;
- }
- else if(str.find("siblings")!=-1)
- {
- int a = getNum(str,0);
- int b = getNum(str,str.find("of")+3);
- // 兄弟节点, 必须在同一层
- if(valtonode[b]&&valtonode[a]&&valtonode[b]->level==valtonode[a]->level)
- {
- if(isSiblings(root,valtonode[a],valtonode[b]))
- return true;
- }
- return false;
- }
- else if(str.find("parent")!=-1)
- {
- int a = getNum(str,0);
- int b = getNum(str,str.find("of")+3);
- if(valtonode[b]&&valtonode[a])
- {
- if(valtonode[a]->left == valtonode[b] || valtonode[a]->right == valtonode[b])
- return true;
- }
- return false;
- }
- else if(str.find("left")!=-1)
- {
- int a = getNum(str,0);
- int b = getNum(str,str.find("of")+3);
- if(valtonode[b]&&valtonode[a])
- {
- if(valtonode[b]->left==valtonode[a])
- return true;
- }
- return false;
- }
- else if(str.find("right")!=-1)
- {
- int a = getNum(str,0);
- int b = getNum(str,str.find("of")+3);
- if(valtonode[b]&&valtonode[a])
- {
- if(valtonode[b]->right==valtonode[a])
- return true;
- }
- }
- else if(str.find("same")!=-1)
- {
- int a = getNum(str,0);
- int b = getNum(str,str.find("and")+4);
- if(valtonode[b]&&valtonode[a])
- {
- if(valtonode[b]->level==valtonode[a]->level)
- return true;
- }
- return false;
- }
- else if(str.find("full")!=-1)
- {
- return isFullTree(root);
- }
- return false;
- }
- string mygets()
- {
- char str[100];
- fgets(str,sizeof(str),stdin);
- int len = strlen(str);
- if(str[len-1]=='\n') str[len-1] = '\0';
- return str;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("1.txt","r",stdin);
- #endif
- scanf("%d",&n);
- int post[n];
- for(int i=0;i<n;++i)
- scanf("%d",&post[i]);
- for(int i=0;i<n;++i)
- {
- int a;
- scanf("%d",&a);
- valtoid[a] = i;
- }
- for(int i=n-1;i>=0;--i)
- root = Insert(root,post[i]);
- int m;
- scanf("%d",&m);
- getchar();
- for(int i=0;i<m;++i)
- {
- string str = mygets();
- bool bRight = isRight(str);
- printf("%s\n",bRight?"Yes":"No");
- }
- return 0;
- }
- View Code
题目在下面:
- 7-4 Structure of a Binary Tree (30 分)
- Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.
- Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:
- A is the root
- A and B are siblings
- A is the parent of B
- A is the left child of B
- A is the right child of B
- A and B are on the same level
- It is a full tree
- Note:
- Two nodes are on the same level, means that they have the same depth.
- A full binary tree is a tree in which every node other than the leaves has two children.
- Input Specification:
- Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 10
- ?3
- ?? and are separated by a space.
- Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.
- Output Specification:
- For each statement, print in a line Yes if it is correct, or No if not.
- Sample Input:
- 9
- 16 7 11 32 28 2 23 8 15
- 16 23 7 32 11 2 28 15 8
- 7
- 15 is the root
- 8 and 2 are siblings
- 32 is the parent of 11
- 23 is the left child of 16
- 28 is the right child of 2
- 7 and 11 are on the same level
- It is a full tree
- Sample Output:
- Yes
- No
- Yes
- No
- Yes
- Yes
- Yes
来源: http://www.bubuko.com/infodetail-2975585.html