习题整理——二叉树NOI1758、UVA679、UVA122
NOI 1758
如图所示的二叉树，每个节点到根节点只有唯一一条路径，我们的任务是给出两个节点，找到它们的路径的第一个重合的节点。例如，4和10两个节点的路径分别是（4，2，1）和（10，5，2，1）所以第一个重合的节点是2，2就是我们要找的节点。
思路：这个二叉树的特点就是每个节点的左孩子是节点的二倍，右孩子是节点的二倍加1. 所以一个节点到根节点的路径只要不断除以2就行。每次循环，两个数较大的数除以二，直到两数相等，就是第一个重合节点了
代码：
#include<iostream>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
while(1){
if(x == y){
cout<<x<<endl;
break;
}
else if(x<y)
y = y/2;
else
x = x/2;
}
return 0;
}UVA 679
如图的二叉树，初始时每个节点都为false，之后有小球下落，落到某个节点上时，如果节点为false，小球向左落，如果节点为true，小球向右落，节点变为相反的值。给出树高D和下落小球数I，求第I个小球落到的叶节点。
思路：
某个节点第n次被小球砸到，如果n为奇数，那么小球往左落，如果n为偶数小球往右落。假设第八颗球，节点1被砸8次，对于节点1是向右落的。对于节点3，节点3被砸8/2=4次还是，向右落。依次类推。假设第7颗球，节点1被砸7次，向左落，节点2被砸7/2+1=4次，向右落，节点5被砸4/2=2次向右落，所以最后是11.
代码：
#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
int main(){
int num;
cin>>num;
while(num--){
int D,I;
int node=1;
cin>>D>>I;
for(int i=0;i<D;i++){
if(I%2 == 1){
node = node*2;
I = I/2 +1;
}
else{
node = node*2+1;
I = I/2;
}
}
cout<<node/2<<endl;
}
return 0;
}UVA 122
树的层次遍历：
思路1:
分别用两个数组存储值和路径例如number = {11，7，8，5，4，13，2，1，4}, s = {LL,LLL,R, ,L,RL,LLR,RRR,RR}，对s进行排序，相应的number跟着s修改。
排序规则为：两个字符串长度较长的排在后边，如果长度一样，则按照字典序。上边例子排完后，number = {5，4，8，11，13，4，7，2，1}, s = { ,L,R,LL,RL,RR,LLL,LLR,RRR}。这样排过序后的s，就是按照一层一层的遍历的。
检测是否重复，就可以看s中是否有相同字符串，检测是否缺了节点，以RRR为例，去掉最后一个字符变成RR，之后在s中向前搜索是否有RR，有的话再去掉最后一个字符变成R，再向前搜索是否有R。搜索完成后判断RRR是否为空。
代码：
#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
int number[256];
string s[256] ;
void clear(){
for(int i=0;i<256;i++){
number[i]=0;
s[i]="";
}
}
bool compare(string s1,string s2){
if(s1.length()>s2.length())
return true;
else if(s1.length()<s2.length())
return false;
else
return s1>s2;
}
void sort_s(int count){
for(int i=0;i<count;i++)
for(int j=0;j<count-i-1;j++)
if(compare(s[j], s[j+1])){
swap(s[j],s[j+1]);
swap(number[j],number[j+1]);
}
}
bool check(int count){
for(int i=1;i<count;i++){
if(s[i]==s[i-1])
return false;
}
if(s[0] != " ")
return false;
for(int i=count-1;i>=0;i--){
string temp = s[i];
for(int j=i;j>=0;j--){
if(temp == s[j])
temp.pop_back();
}
if(temp!=""){
return false;
}
}
return true;
}
void show(int count){
if(check(count)){
for(int i=0;i<count;i++){
if(i!=0)
cout<<' ';
cout<<number[i];
}
}
else
cout<<"not complete";
cout<<endl;
}
int main(){
char ch;
int num;
int count = 0;
clear();
while((ch=getchar())!=EOF){
if(ch == '('){
num = 0;
scanf("%d",&num);
if(num==0){
sort_s(count);
show(count);
clear();
count = 0;
continue;
}
number[count]=num;
getchar();
while(cin>>ch && (ch == 'L' || ch == 'R')){
s[count] = s[count] + ch;
}
if(s[count] == "")
s[count] = " ";
count++;
}
}
return 0;
}
思路2:
动态建立二叉树，层次遍历可以借助一个队列，初始时队列中只有根节点，每次取出队列中的一个节点，之后将这个节点的左右孩子分别压入队列，直到队列为空。
代码：
#include<iostream>
#include<math.h>
#include<cstring>
#include<queue>
using namespace std;
typedef struct Node{
int element = 0;
Node *left = NULL;
Node * right = NULL;
}Node;
void create(Node * &N){
if(N==NULL)
N = new Node;
}
bool check(Node *N){
queue<Node*> q;
q.push(N);
while(!q.empty()){
Node * temp = q.front();
if(temp->element==0)
return false;
if(temp->left!=NULL)
q.push(temp->left);
if(temp->right!=NULL)
q.push(temp->right);
q.pop();
}
return true;
}
void show(Node *N){
queue<Node*> q;
q.push(N);
int i=0;
while(!q.empty()){
if(i!=0)
cout<<' ';
i=1;
Node * temp = q.front();
if(temp->left!=NULL)
q.push(temp->left);
if(temp->right!=NULL)
q.push(temp->right);
cout<<temp->element;
q.pop();
}
cout<<endl;
}
void clear(Node *&N){
if(N==NULL)
return;
clear(N->left);
clear(N->right);
delete N;
}
int main(){
Node * root = new Node;
char ch;
int num;
int flag =0;
while((ch=getchar())!=EOF){
if(ch == '('){
Node *temp = root;
num = 0;
scanf("%d",&num);
if(num==0){
if(check(root) && flag != 1)
show(root);
else
cout<<"not complete"<<endl;
clear(root);
root = new Node;
flag = 0;
continue;
}
while(cin>>ch && ch != ')'){
if(ch == 'L'){
create(temp->left);
temp = temp->left;
}
else if(ch== 'R'){
create(temp->right);
temp = temp->right;
}
}
if(temp->element!=0)
flag = 1;
temp->element = num;
}
}
return 0;
}