pta 6-2至6-4上机实验题

6-2 判断两棵二叉树是否同构（递归法）

函数接口定义

bool Isomorphism(BiTree T1,BiTree T2);

裁判测试程序样例

#include<iostream>
#include<string.h>
#define N 100;
using namespace std;
typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T,char a[],int &i){    
    char ch;
    ch=a[i++];
    if(ch=='#')  T=NULL;
    else{                            
        T=new BiTNode;
        T->data=ch;                    
        CreateBiTree(T->lchild,a,i);    
        CreateBiTree(T->rchild,a,i);    
    }                        
}    

bool Isomorphism(BiTree T1,BiTree T2);

int main(){
    BiTree T1,T2;
    int i=0,j=0;
    char a[N];
    char b[N];
    cin>>a>>b;
    CreateBiTree(T1,a,i);
    CreateBiTree(T2,b,j);    
    cout<<Isomorphism(T1,T2);    
    return 0;
}

/* 请在这里填写答案 */

• 大致思路：递归，注意对是否为空指针的判断。

AC代码

bool Isomorphism(BiTree T1, BiTree T2)
{
    if (T1 == NULL && T2 == NULL)
        return true;
    if (T1 != NULL && T2== NULL || T1 == NULL && T2 != NULL)
        return false;
    else {
        Isomorphism(T1->lchild, T2->lchild);
        Isomorphism(T1->rchild, T2->rchild);
    }
}

6-4 二叉树的遍历

本题构造一个含3个结点的二叉树，输入的第一个结点为根结点，第二个结点为根结点的左儿子，第三个结点为根结点的右儿子，输出这个二叉树的先序、中序和后序序列。

函数接口定义：

bool Isomorphism(BiTree T1,BiTree T2);

裁判测试程序样例：

#include<iostream>
#include<string.h>
#define N 100
using namespace std;
typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T,char a[],int &i){    
    char ch;
    ch=a[i++];
    if(ch=='#')  T=NULL;
    else{                            
        T=new BiTNode;
        T->data=ch;                    
        CreateBiTree(T->lchild,a,i);    
        CreateBiTree(T->rchild,a,i);    
    }                        
}    

bool Isomorphism(BiTree T1,BiTree T2);

int main(){
    BiTree T1,T2;
    int i=0,j=0;
    char a[N];
    char b[N];
    cin>>a>>b;
    CreateBiTree(T1,a,i);
    CreateBiTree(T2,b,j);    
    cout<<Isomorphism(T1,T2);    
    return 0;
}

/* 请在这里填写答案 */

• 大致思路：创建树的时候要注意不管左孩子还是右孩子都要分配空间，并要注意分配空间时的类型转换。(这里因为只有三个结点，在先序中序后序的时候偷了下懒 QWQ…)

AC代码

Bptr creat()
{
    Bptr B;
    B = (Bptr)malloc(sizeof(Bnode));
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    B->data = a;
    B->Lson = (Bptr)malloc(sizeof(Bnode));
    B->Rson = (Bptr)malloc(sizeof(Bnode));
    B->Lson->data = b;
    B->Rson->data = c;
    return B;
}
void preorder(Bptr p)
{
    printf("%d ", p->data);
    printf("%d ", p->Lson->data);
    printf("%d ", p->Rson->data);
}
void inorder(Bptr p)
{
    printf("%d ", p->Lson->data);
    printf("%d ", p->data);
    printf("%d ", p->Rson->data);
}
void postorder(Bptr p)
{
    printf("%d ", p->Lson->data);
    printf("%d ", p->Rson->data);
    printf("%d ", p->data);
}

6-3 求根结点到x结点的路径（递归法）

求根结点到x结点的路径（假定结点值不重复）。

函数接口定义：

bool Findxpath(BiTree bt,char x,vector<char> tmppath,vector<char> &path) ;

裁判测试程序样例：

#include<iostream>
#include<stdlib.h>
#include<vector>

using namespace std;
typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T){    
    char ch;
    cin>>ch;
    if(ch=='#')  T=NULL;
    else{                            
        T=new BiTNode;
        T->data=ch;                    
        CreateBiTree(T->lchild);    
        CreateBiTree(T->rchild);    
    }                        
}    

bool Findxpath(BiTree bt,char x,vector<char> tmppath,vector<char> &path);

int main(){
    BiTree T;
    char x;
    vector<char>tmppath;
    vector<char>path;    
    CreateBiTree(T);
    cin>>x;
    Findxpath(T,x,tmppath,path);
    for(int i=0;i<path.size();i++)
        cout<<path[i]<<" ";
    return 0;
}

/* 请在这里填写答案 */

• 大致思路：递归，先存到没有&的tmppath数组里便于每次递归回到之前位置，找到了所需x后，在将其赋值到path数组中。

AC代码

bool flag = false;
bool Findxpath(BiTree bt, char x, vector<char> tmppath, vector<char>& path)
{
    if (bt != NULL)
    {
        tmppath.push_back(bt->data);
        if (bt->data != x)
        {
            if (bt->lchild != NULL)
                Findxpath(bt->lchild, x, tmppath, path);
            if (bt->rchild != NULL && !flag)
                Findxpath(bt->rchild, x, tmppath, path);
        }
        else
        {
            flag = true;
            path = tmppath;
            return true;
        }
    }
    if (flag)
        return true;
    else
        return false;
}