PTA二叉树练习_输入的第一行给出两个正整数:待查询的结点对数 m(≤ 1 000)和二叉搜索树中结点个

7-1 树的同构

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

现给定两棵树，请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:

Yes

输入样例2（对应图2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:

No

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    char data;
    int left,right;
}Node;
 
int N;
void in(Node* n){
    for(int i=0;i<N;i++){
        cin>>n[i].data;
        char left,right;
        cin>>left>>right;
        if(left=='-')
            n[i].left=-1;
        else if(left>='0'&&left<='9')
            n[i].left=left-'0';
        if(right=='-')
            n[i].right=-1;
        else if(right>='0'&&right<='9')
            n[i].right=right-'0';
    }
}
 
int judge(Node* n1,Node* n2){
    int flag=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(n1[i].data==n2[j].data){
                if(n1[n1[i].left].data==n2[n2[j].left].data){
                    if(n1[n1[i].right].data!=n2[n2[j].right].data){
                        flag=0;
                        return flag;
                    }
                }
                else if(n1[n1[i].left].data==n2[n2[j].right].data){
                    if(n1[n1[i].right].data!=n2[n2[j].left].data){
                        flag=0;
                        return flag;
                    }
                }
                else{
                    flag=0;
                    return flag;
                }
            }
        }
    }
    return flag;
}
 
int main(){
    cin>>N;
    Node n1[N],n2[N];
    in(n1);
    cin>>N;
    in(n2);
    if(N==1&&n1[0].data==n2[0].data){
        cout<<"Yes";
        return 0;
    }
    else if(N==1&&n1[0].data!=n2[0].data){
        cout<<"No";
        return 0;
    }
    int flag=judge(n1,n2);
    if(flag) cout<<"Yes";
    else cout<<"No";
    return 0;
}

7-2 二叉搜索树的结构

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式：

输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：

• A is the root，即"A是树的根"；

• A and B are siblings，即"A和B是兄弟结点"；

• A is the parent of B，即"A是B的双亲结点"；

• A is the left child of B，即"A是B的左孩子"；

• A is the right child of B，即"A是B的右孩子"；

• A and B are on the same level，即"A和B在同一层上"。

题目保证所有给定的整数都在整型范围内。

输出格式：

对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。

输入样例：

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例：

Yes
Yes
Yes
Yes
Yes
No
No
No

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int data;
    int father=-1;
    int left=-1;
    int right=-1;
    int level=1;
}Node;
 
void intree(Node* n,int gen,int ru){
    if(n[ru].data<n[gen].data){
        if(n[gen].left==-1){
            n[gen].left=ru;
            n[ru].father=gen;
            n[ru].level=n[gen].level+1;
        }
        else
            intree(n,n[gen].left,ru);
    }
    else if(n[ru].data>n[gen].data){
        if(n[gen].right==-1){
            n[gen].right=ru;
            n[ru].father=gen;
            n[ru].level=n[gen].level+1;
        }
        else
            intree(n,n[gen].right,ru);
    }
}
 
int main(){
    int N;
    cin>>N;
    Node n[N];
    cin>>n[0].data;
    for(int i=1;i<N;i++){
        cin>>n[i].data;
        intree(n,0,i);
    }
    int M;
    cin>>M;
    string s;
    M++;
    while(M--){
        int a,b,c,d,flag=0;
        getline(cin,s);
        if(s.find("root")!=s.npos){
            sscanf(s.c_str(),"%d is the root",&a);
            if(n[0].data==a) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if(s.find("siblings")!=s.npos){
            sscanf(s.c_str(),"%d and %d are siblings",&a,&b);
            for(int i=0;i<N;i++){
                if(n[i].data==a)
                    c=i;
                if(n[i].data==b)
                    d=i;
            }
            if(n[c].father==n[d].father) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if(s.find("parent")!=s.npos){
            sscanf(s.c_str(),"%d is the parent of %d",&a,&b);
            for(int i=0;i<N;i++){
                if(n[i].data==a){
                    c=i;
                    flag+=1;
                }
                if(n[i].data==b){
                    d=i;
                    flag+=1;
                }
            }
            if((n[d].father==c)&&(flag==2)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if(s.find("left")!=s.npos){
            sscanf(s.c_str(),"%d is the left child of %d",&a,&b);
            for(int i=0;i<N;i++){
                if(n[i].data==a)
                    c=i;
                if(n[i].data==b)
                    d=i;
            }
            if(n[d].left==c) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if(s.find("right")!=s.npos){
            sscanf(s.c_str(),"%d is the right child of %d",&a,&b);
            for(int i=0;i<N;i++){
                if(n[i].data==a)
                    c=i;
                if(n[i].data==b)
                    d=i;
            }
            if(n[d].right==c) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if(s.find("level")!=s.npos){
            sscanf(s.c_str(),"%d and %d are on the same level",&a,&b);
            for(int i=0;i<N;i++){
                if(n[i].data==a)
                    c=i;
                if(n[i].data==b)
                    d=i;
            }
            if(n[c].level==n[d].level) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

7-3 二叉搜索树的最近公共祖先

给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。

输入格式：

输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1 000）和二叉搜索树中结点个数 N（≤ 10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。

输出格式：

对每一对给定的 U 和 V，如果找到 A 是它们的最近公共祖先结点的键值，则在一行中输出 LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出 X is an ancestor of Y.，其中 X 是那个祖先结点的键值，Y 是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出 ERROR: U is not found. 或者 ERROR: V is not found.，或者 ERROR: U and V are not found.。

输入样例：

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

输出样例：

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef struct TNode{
    int data;
    struct TNode* left=NULL,*right=NULL;
}TNode,*BinTree;
 
void in(BinTree& BST,int n){
    if(BST==NULL){
        BST=new TNode;
        BST->data=n;
    }
    else{
        if(n<BST->data)
            in(BST->left,n);
        else if(n>BST->data)
            in(BST->right,n);
    }
}
 
int findLCA(BinTree BST,int a,int b){
    while (1){
        if (BST->data>a&&BST->data>b)
            BST=BST->left;
        else if(BST->data<a&&BST->data<b)
            BST=BST->right;
        else
            break;
    }
    return BST->data;
}
 
int main(){
    BinTree BST=NULL;
    int M,N;
    cin>>M>>N;
    int n[N];
    for(int i=0;i<N;i++){
        cin>>n[i];
        in(BST,n[i]);
    }
    int a,b;
    while(M--){
        int flaga=0,flagb=0;
        cin>>a>>b;
        for(int i=0;i<N;i++){
            if(a==n[i]) flaga=1;
            if(b==n[i]) flagb=1;
            if(flaga&&flagb) break;
        }
        if(!flaga&&!flagb)
            printf("ERROR: %d and %d are not found.\n",a,b);
        else if(!flaga&&flagb)
            printf("ERROR: %d is not found.\n",a);
        else if(flaga&&!flagb)
            printf("ERROR: %d is not found.\n",b);
        else{
            int find;
            find=findLCA(BST,a,b);
            if(find==a)
                printf("%d is an ancestor of %d.\n",a,b);
            else if(find==b)
                printf("%d is an ancestor of %d.\n",b,a);
            else
                printf("LCA of %d and %d is %d.\n",a,b,find);
        }
    }
    return 0;
}

7-4 完全二叉树的层序遍历

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

输入格式：

输入在第一行中给出正整数 N（≤30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。

输出格式：

在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8
91 71 2 34 10 15 55 18

输出样例：

18 34 55 71 2 10 15 91

代码如下：

#include <bits/stdc++.h>
#define N 31
using namespace std;
int result[N];
int postorder[N];
int in = 1;
void dfs(int x, int m){
    if(x > m) return;
    dfs(x*2, m);
    dfs(2*x+1, m);
    result[x]=postorder[in++];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>postorder[i];
    dfs(1,n);
    cout<<result[1];
    for(int i=2;i<=n;i++)
        cout<<" "<<result[i];
    return 0;
}

7-5 根据后序和中序遍历输出先序遍历

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

代码如下：

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node* l,*r;
};
node* buildTree(int len,int* post,int* mid){
    node* root=new node;
    if(!len) return NULL;
    root->data=post[len];
    int index;
    for(index=1;index<=len;index++)
        if(mid[index]==root->data) break;
    root->l=buildTree(index-1,post,mid);
    root->r=buildTree(len-index,post+index-1,mid+index);
    return root;
}
void out(node* root){
    if(root){
        cout<<" "<<root->data;
    out(root->l);
    out(root->r);
    }
}
int main(){
    int n;
    cin>>n;
    int postorder[n+1],midorder[n+1];
    for(int i=1;i<=n;i++)
        cin>>postorder[i];
    for(int i=1;i<=n;i++)
        cin>>midorder[i];
    node* root=buildTree(n,postorder,midorder);
    cout<<"Preorder:";
    out(root);
    return 0;
}