关于算法-数据结构:PAT甲级2019年春季考试-74-Structure-of-a-Binary-Tree

76次阅读

共计 7783 个字符，预计需要花费 20 分钟才能阅读完成。

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

题目限度：

题目粗心：

给定一颗二叉树的中序和后序，现有 7 种不同的查问语句，如果该语句形容正确，输入 Yes，否则输入 No。

算法思路：

这里给出 2 种不同的实现形式，一种是先建树，而后应用 BFS 记录该树的信息 (比拟好想到)，第二种是在建树的过程中间接记录所须要的所有信息。
首先给出 7 种查问，该如何判断是否正确的办法：

  • A is the root(直接判断后序序列最初一个节点是否和 A 相等即可)
  • A and B are siblings(应用 parent 数组记录所有的节点的父亲，只有判断 parent[A]是否和 parent[B]相等即可)
  • A is the parent of B（判断 parent[B]是否和 A 相等即可）
  • A is the left child of B（应用 leftChild 数组记录所有节点恶左孩子，判断 leftChild[B]与 A 是否相等即可）
  • A is the right child of B（应用 rightChild 数组记录所有节点恶左孩子，判断 rightChild[B]与 A 是否相等即可）
  • A and B are on the same level（应用 level 数组记录所有节点的档次，而后判断 level[A]和 level[B]是否相等即可）
  • It is a full tree（应用 isFullTree 记录该树是否存在只有一个孩子的状况，如果是阐明不是 full tree，否则就是）
先建树，而后应用 BFS 获取信息：
Node* createTree(int postL,int postR,int inL,int inR){if(postL>postR) return nullptr;
    Node *root = new Node;
    root->data = post[postR];
    int k = pos[post[postR]];// 根节点地位
    int numOfLeft = k-inL;
    root->left = createTree(postL,postL+numOfLeft-1,inL,k-1);
    root->right = createTree(postL+numOfLeft,postR-1,k+1,inR);
    return root;
}

void BFS(Node *root,bool &isFullTree){
    queue<Node*> q;
    root->level = 1;
    parent[root->data] = -1;
    level[root->data] = 1;
    q.push(root);
    while (!q.empty()){Node *t = q.front();
        q.pop();
        if((t->left||t->right)&&!(t->left&&t->right)){isFullTree = false;}
        if(t->left!= nullptr){
            t->left->level = t->level+1;
            parent[t->left->data] = t->data;
            level[t->left->data] = t->level+1;
            leftChild[t->data] = t->left->data;
            q.push(t->left);
        }
        if(t->right!= nullptr){
            t->right->level = t->level+1;
            level[t->right->data] = t->level+1;
            parent[t->right->data] = t->data;
            rightChild[t->data] = t->right->data;
            q.push(t->right);
        }
    }
}
在建树的时候获取信息：
bool isFullTree = true;
Node* createTree(int postL,int postR,int inL,int inR,int depth,int pa){if(postL>postR) return nullptr;
    Node *root = new Node;
    root->data = post[postR];
    parent[root->data] = pa;
    level[root->data] = depth;
    int k = pos[post[postR]];// 根节点地位
    int numOfLeft = k-inL;
    root->left = createTree(postL,postL+numOfLeft-1,inL,k-1,depth+1,root->data);
    root->right = createTree(postL+numOfLeft,postR-1,k+1,inR,depth+1,root->data);
    leftChild[root->data] = root->left?post[postL+numOfLeft-1]:-1;
    rightChild[root->data] = root->right?post[postR-1]:-1;
    if((root->left||root->right)&&!(root->left&&root->right)){isFullTree = false;}
    return root;
}
将输出的字符串依据空格划分为字符串数组：
string query;
getline(cin,query);
vector<string> all;
string r;
for(char i : query){if(i==' '){all.push_back(r);
        r = "";
    } else{r += i;}
}
all.push_back(r);

留神点：

  • 1、在判断类型的时候，最好是先判断长度，再判断关键字，不然测试点 1 和测试点 4 会呈现运行时谬误。尤其是在判断 A and B are on the same level 类型的时候。
  • 2、在应用 getline 第一次输出的时候须要先应用 getchar()接管回车。

提交后果：

AC 代码 1(一遍建树一遍获取信息)：

#include<cstdio>
#include <string>
#include <vector>
#include <iostream>

using namespace std;
/*
 * 题目粗心：*
 */
struct Node{
    int data;
    Node* left;
    Node* right;
};

int N;
int in[40],post[40],pos[1005],parent[1005],leftChild[1005],rightChild[1005],level[1005];
bool isFullTree = true;
Node* createTree(int postL,int postR,int inL,int inR,int depth,int pa){if(postL>postR) return nullptr;
    Node *root = new Node;
    root->data = post[postR];
    parent[root->data] = pa;
    level[root->data] = depth;
    int k = pos[post[postR]];// 根节点地位
    int numOfLeft = k-inL;
    root->left = createTree(postL,postL+numOfLeft-1,inL,k-1,depth+1,root->data);
    root->right = createTree(postL+numOfLeft,postR-1,k+1,inR,depth+1,root->data);
    leftChild[root->data] = root->left?post[postL+numOfLeft-1]:-1;
    rightChild[root->data] = root->right?post[postR-1]:-1;
    if((root->left||root->right)&&!(root->left&&root->right)){isFullTree = false;}
    return root;
}

int main(){scanf("%d",&N);
    for (int i = 0; i < N; ++i) {scanf("%d",&post[i]);
    }
    for (int i = 0; i < N; ++i) {scanf("%d",&in[i]);
        pos[in[i]] = i;
    }
    Node *root = createTree(0,N-1,0,N-1,1,-1);
    int M;
    scanf("%d",&M);
    getchar();
    for (int j = 0; j < M; ++j) {
        string query;
        getline(cin,query);
        vector<string> all;
        string r;
        for(char i : query){if(i==' '){all.push_back(r);
                r = "";
            } else{r += i;}
        }
        all.push_back(r);
        if(all[3]=="root"){if(root->data==stoi(all[0])){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all[4]=="siblings"){int a = stoi(all[0]);
            int b = stoi(all[2]);
            if(parent[a]==parent[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all[3]=="parent"){int a = stoi(all[0]);
            int b = stoi(all[5]);
            if(a==parent[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all[3]=="left"){int a = stoi(all[0]);
            int b = stoi(all[6]);
            if(a==leftChild[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        }else if(all[3]=="right"){int a = stoi(all[0]);
            int b = stoi(all[6]);
            if(a==rightChild[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all.size()==8){int a = stoi(all[0]);
            int b = stoi(all[2]);
            if(level[a]==level[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else{if(isFullTree){printf("Yes\n");
            } else {printf("No\n");
            }
        }
    }
    return 0;
}

AC 代码 2(先建树后 BFS)：

#include<cstdio>
#include <string>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;
    int level;
};

int N;
int in[40],post[40],pos[1005],parent[1005],leftChild[1005],rightChild[1005],level[1005];

Node* createTree(int postL,int postR,int inL,int inR){if(postL>postR) return nullptr;
    Node *root = new Node;
    root->data = post[postR];
    int k = pos[post[postR]];// 根节点地位
    int numOfLeft = k-inL;
    root->left = createTree(postL,postL+numOfLeft-1,inL,k-1);
    root->right = createTree(postL+numOfLeft,postR-1,k+1,inR);
    return root;
}

void BFS(Node *root,bool &isFullTree){
    queue<Node*> q;
    root->level = 1;
    parent[root->data] = -1;
    level[root->data] = 1;
    q.push(root);
    while (!q.empty()){Node *t = q.front();
        q.pop();
        if((t->left||t->right)&&!(t->left&&t->right)){isFullTree = false;}
        if(t->left!= nullptr){
            t->left->level = t->level+1;
            parent[t->left->data] = t->data;
            level[t->left->data] = t->level+1;
            leftChild[t->data] = t->left->data;
            q.push(t->left);
        }
        if(t->right!= nullptr){
            t->right->level = t->level+1;
            level[t->right->data] = t->level+1;
            parent[t->right->data] = t->data;
            rightChild[t->data] = t->right->data;
            q.push(t->right);
        }
    }
}

int main(){scanf("%d",&N);
    for (int i = 0; i < N; ++i) {scanf("%d",&post[i]);
    }
    for (int i = 0; i < N; ++i) {scanf("%d",&in[i]);
        pos[in[i]] = i;
    }
    Node *root = createTree(0,N-1,0,N-1);
    bool isFullTree = true;
    BFS(root,isFullTree);
    int M;
    scanf("%d",&M);
    for (int j = 0; j < M; ++j) {
        string query;
        if(j==0){
            // 要排汇第一个回车
            getchar();}
        getline(cin,query);
        vector<string> all;
        string r;
        for(char i : query){if(i==' '){all.push_back(r);
                r = "";
            } else{r += i;}
        }
        all.push_back(r);
        if(all[3]=="root"){if(root->data==stoi(all[0])){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all[4]=="siblings"){int a = stoi(all[0]);
            int b = stoi(all[2]);
            if(parent[a]==parent[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all[3]=="parent"){int a = stoi(all[0]);
            int b = stoi(all[5]);
            if(a==parent[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all[3]=="left"){int a = stoi(all[0]);
            int b = stoi(all[6]);
            if(a==leftChild[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        }else if(all[3]=="right"){int a = stoi(all[0]);
            int b = stoi(all[6]);
            if(a==rightChild[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else if(all.size()==8){int a = stoi(all[0]);
            int b = stoi(all[2]);
            if(level[a]==level[b]){printf("Yes\n");
            } else {printf("No\n");
            }
        } else{if(isFullTree){printf("Yes\n");
            } else {printf("No\n");
            }
        }
    }
    return 0;
}

正文完
算法-数据结构
发表至： 算法-数据结构
2020-12-02
 0
关于算法-数据结构:一周刷完剑指offer7斐波那契数列
关于算法-数据结构:PAT甲级2019年冬季考试-74-Cartesian-Tree
关于算法-数据结构:PAT甲级1067-Sort-with-Swap0-i
关于算法-数据结构:荷兰国旗问题以及快速排序