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:

916 7 11 32 28 2 23 8 1516 23 7 32 11 2 28 15 8715 is the root8 and 2 are siblings32 is the parent of 1123 is the left child of 1628 is the right child of 27 and 11 are on the same levelIt is a full tree

Sample Output:

YesNoYesNoYesYesYes

题目限度：

题目粗心：

给定一颗二叉树的中序和后序，现有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;}