关于算法-数据结构:PAT甲级1043-Is-It-a-Binary-Search-Tree

题目粗心:

现给定一颗N个结点的树,判断该树是否是二叉查找树或者镜像二叉查找树,如果是输入YES并输入该树的后序遍历,否则输入NO

算法思路:

咱们首先通过给定的N个结点间接构建一个二叉查找树,而后再取得其先序遍历序列和镜像先序遍历序列,别离判断是否和输出的序列相等,如果输出的序列是先序遍历序列,那么就输入YES并取得其后序遍历序列进行输入,如果输出序列是镜像先序遍历序列,那么就输入YES并取得镜像后序遍历序列进行输入,如果都不是,就输入NO。

构建二叉查找树:

这里采纳间接模仿手工构建二叉查找树的过程,首先是依据插入的数据值,新建一个叶子结点,而后从根节点进行查找,如果根节点为空,阐明曾经找到插入地位,将根结点赋值为以后叶子结点即可,如果根节点的数据值小于叶子结点数据值,递归向左子树插入该结点,否则递归向右子树插入该结点。代码如下:

struct Node{
    int data;
    struct Node* left;
    struct Node* right;
};
// 创立结点 
Node* newNode(int data){
    Node* node = new Node();
    node->data = data;
    node->left = node->right = nullptr;
    return node;
}

// 插入结点到root中 
void insert(Node* &root,int data){
    if(root==nullptr){
        // 查找到插入地位
        root = newNode(data);
        return;
    }
    if(root->data>data){
        // 在左子树中查找插入地位
        insert(root->left,data); 
    }else{
        // 在右子树中查找插入地位
        insert(root->right,data); 
    }
}
// 建树 
for(int i=0;i<N;++i){
    scanf("%d",&num[i]);
    insert(root,num[i]);
}

留神点:

  • 1、当输出序列为镜像先序查找树的时候,其后序序列为镜像后序序列,样例2就是该状况。

提交后果:

AC代码:

#include<cstdio>
#include<vector>

using namespace std;

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

int N;
int num[1001];// 存储输出序列
vector<int> pre,mirrorPre,post,postMirror;// 先序,先序镜像先序,后序序列 ,后序镜像序列 

// 创立结点 
Node* newNode(int data){
    Node* node = new Node();
    node->data = data;
    node->left = node->right = nullptr;
    return node;
}

// 插入结点到root中 
void insert(Node* &root,int data){
    if(root==nullptr){
        // 查找到插入地位
        root = newNode(data);
        return;
    }
    if(root->data>data){
        // 在左子树中查找插入地位
        insert(root->left,data); 
    }else{
        // 在右子树中查找插入地位
        insert(root->right,data); 
    }
}

void preTraverse(Node* root){
    if(root==nullptr) return;
    pre.push_back(root->data);
    preTraverse(root->left);
    preTraverse(root->right);
}

void preMirrotTraverse(Node* root){
    if(root==nullptr) return;
    mirrorPre.push_back(root->data);
    preMirrotTraverse(root->right);
    preMirrotTraverse(root->left);
}

void postTraverse(Node* root){
    if(root==nullptr) return;
    postTraverse(root->left);
    postTraverse(root->right);
    post.push_back(root->data);
}

void postMirrorTraverse(Node* root){
    if(root==nullptr) return;
    postMirrorTraverse(root->right);
    postMirrorTraverse(root->left);
    postMirror.push_back(root->data);
}

// 判断输出序列是否是先序序列
bool isPre(){ 
    for(int i=0;i<N;++i){
        if(pre[i]!=num[i]){
            return false;
        }
    }
    return true;
}

// 判断输出序列是否是先序镜像序列
bool isPreMirror(){ 
    for(int i=0;i<N;++i){
        if(mirrorPre[i]!=num[i]){
            return false;
        }
    }
    return true;
}

int main(){
    scanf("%d",&N);
    Node* root = nullptr;
    // 建树 
    for(int i=0;i<N;++i){
        scanf("%d",&num[i]);
        insert(root,num[i]);
    }
    preTraverse(root);
    preMirrotTraverse(root); 
    if(isPre()){
        // 是先序序列
        printf("YES\n");
        postTraverse(root);
        for(int i=0;i<N;++i){
            printf("%d",post[i]);
            if(i<N-1) printf(" ");
        }
    }else if(isPreMirror()){
        // 是先序镜像序列
        printf("YES\n");
        postMirrorTraverse(root);
        for(int i=0;i<N;++i){
            printf("%d",postMirror[i]);
            if(i<N-1) printf(" ");
        }
    }else {
        printf("NO");
    }
    return 0;
}
在这里再给出间接建设BST和镜像BST的写法
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
/*
题目要求:现给定一颗N个结点的树,判断该树是否是二叉查找树或者镜像二叉查找树,如果是输入YES并输入该树的后序遍历,否则输入NO 
算法思路:因为得输入对应的后序遍历序列,那么就得构建这颗树了,因为有可能有2种合乎题意的树,咱们采纳2次先判断再建设树的形式.
1.首先咱们先判断该树是否是BST:这里采纳的是利用先序遍历序列构建BST的过程判断是否是BST的,在以后递归体中,咱们用index保留第一个大于等于根节点的地位,
因为根节点前面到index地位都小于根节点,所以只需判断前面index到完结地位是否满足BST的定义就好,也就是说如果右子树中有小于根节点的结点,那么让flag=false
(flag是用来判断该树是否是BST的标记),并且return进行递归,如果右子树结点均合乎定义则进行左子树和右子树的递归即可
2.如果该树是BST,就构建BST,构建BST树的过程和判断极为类似,咱们在进入递归的时候首先初始化根节点Node* root = new Node;root->data = pre[preL];同样的咱们用
index保留第一个大于等于根节点的地位,区间[preL+1,index-1]就是左子树,区间[index,preR]就是右子树,而后顺次构建左子树root->left = create(preL+1,index-1),
右子树root->right = create(index,preR),最初返回根结点root即可
3.如果该树不是BST,就判断是否是镜像BST,这里只需将index改为保留第一个小于根节点的地位即可,而后在右子树中有大于等于根节点的结点,如果有,那么让flag=false,
并且return,如果右子树结点均合乎定义则进行左子树和右子树的递归即可
4.如果是镜像BST,则构建镜像BST树,这里与构建BST惟一的区别就是找到第一个小于根节点的地位index,而后左右区间均一样,递归建设树即可
5.如果都不是则输入NO
6.最初得记得输入后序序列postOrder 
*/
const int maxn = 1001;//最多结点数目 
struct Node{
    int data;
    Node* left;
    Node* right;
}node[maxn];
int pre[maxn];//前序和后序序列 
int n;//结点个数 

void isBST(int preL,int preR,bool &flag){//依据先序遍历判断该树是否是BST 
    if(preL>preR) return;
    int index;//保留第一个大于等于根节点的地位 
    for(index=preL+1;index<=preR;++index){
        if(pre[index]>=pre[preL]){
            break;
        }
    }
    for(int i=index;i<=preR;++i){
        if(pre[i]<pre[preL]){//右子树中有小于根节点的结点 
            flag = false;
            return;
        }
    } 
    isBST(preL+1,index-1,flag);
    isBST(index,preR,flag);
}

void isMirrorBST(int preL,int preR,bool &flag){//依据先序遍历判断该树是否是镜像BST 
    if(preL>preR) return;
    int index;//保留第一个小于根节点的地位 
    for(index=preL+1;index<=preR;++index){
        if(pre[index]<pre[preL]){
            break;
        }
    }
    for(int i=index;i<=preR;++i){
        if(pre[i]>=pre[preL]){//右子树中有大于等于根节点的结点 
            flag = false;
            return;
        }
    } 
    isMirrorBST(preL+1,index-1,flag);
    isMirrorBST(index,preR,flag);
}

Node* create(int preL,int preR){//依据先序遍历建设BST 
    if(preL>preR) return NULL;
    Node* root = new Node;
    root->data = pre[preL];
    root->left = root->right = NULL;
    int index;//保留第一个大于等于根节点的地位 
    for(index=preL+1;index<=preR;++index){
        if(pre[index]>=root->data){
            break;
        }
    }
    root->left = create(preL+1,index-1);
    root->right = create(index,preR);
    return root;
}

Node* createMirror(int preL,int preR){//依据先序遍历建设镜像BST 
    if(preL>preR) return NULL;
    Node* root = new Node;
    root->data = pre[preL];
    root->left = root->right = NULL;
    int index;//保留第一个小于根节点的地位 
    for(index=preL+1;index<=preR;++index){
        if(pre[index]<root->data){
            break;
        }
    }
    root->left = createMirror(preL+1,index-1);
    root->right = createMirror(index,preR);
    return root;
}
int num = 0;//用来统计输入节点个数并管制输入空格 
void postOrder(Node *root){//后序遍历二叉树,并输入后序遍历序列 
    if(root==NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d",root->data);
    if(num<n-1) printf(" ");
    ++num;    
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&pre[i]);
    }
    bool flag1 = true;
    bool flag2 = true;
    isBST(0,n-1,flag1);
    isMirrorBST(0,n-1,flag2);
    if(flag1||flag2){
        printf("YES\n");
        Node *root;
        if(flag1){//阐明是BST 
            root = create(0,n-1);
        }else{
            root = createMirror(0,n-1);
        }
        postOrder(root);
    }else{
        printf("NO\n");
    }
    return 0;
} 

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理