SDUT《数据结构与算法》专题训练5 二叉树

数据结构实验之二叉树一:树的同构

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

img
图1

img
图2

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

Input

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

Output

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

Sample Input

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 -

Sample Output

Yes

Reference Code

#include <stdio.h>
#include <stdlib.h>
struct BiTreeNode
{
    char data;
    int left,right;
}BiTree1[100],BiTree2[100];
int cnt1, cnt2;

void createBiTree(struct BiTreeNode BiTree[],int cnt)
{
    int i;
    char ch[2];
    for (i = 0; i < cnt;i++)
    {
        scanf("%s", ch);
        BiTree[i].data = ch[0];
        scanf("%s", ch);
        if (ch[0]=='-')
        {
            BiTree[i].left = 11;
        }
        else
        {
            BiTree[i].left = ch[0] - '0';
        }
        scanf("%s", ch);
        if (ch[0]=='-')
        {
            BiTree[i].right = 11;
        }
        else
        {
            BiTree[i].right = ch[0] - '0';
        }
    }
}

int checkc(int i,int j)
{
    if(BiTree1[BiTree1[i].left].data==BiTree2[BiTree2[j].left].data&&BiTree1[BiTree1[i].right].data==BiTree2[BiTree2[j].right].data)
        return  1;
    if(BiTree1[BiTree1[i].left].data==BiTree2[BiTree2[j].right].data&&BiTree1[BiTree1[i].right].data==BiTree2[BiTree2[j].left].data)
        return 1;
    return 0;
}

int check(struct BiTreeNode BiTree1[],int n1,struct BiTreeNode BiTree2[],int n2)
{
    int i,j;
    for(i=0;i<n1;i++)
    {
        for(j=0;j<n2;j++)
        {
            if(BiTree1[i].data==BiTree2[j].data)
            {
                if(checkc(i,j))break;
                else return 0;
            }
        }
        if(j==n2)return 0;
    }
    return 1;
}

int main()
{
    while(~scanf("%d",&cnt1))
    {
        createBiTree(BiTree1, cnt1);
        scanf("%d", &cnt2);
        createBiTree(BiTree2, cnt2);
        if (cnt1!=cnt2)
        {
            printf("No\n");
        }
        else if(check(BiTree1,cnt1,BiTree2,cnt2))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

数据结构实验之二叉树二:遍历二叉树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知二叉树的一个按先序遍历输入的字符序列,如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

Input

连续输入多组数据,每组数据输入一个长度小于50个字符的字符串。

Output

每组输入数据对应输出2行:
第1行输出中序遍历序列;
第2行输出后序遍历序列。

Sample Input

abc,,de,g,,f,,,

Sample Output

cbegdfa
cgefdba

Reference Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct BiTree
{
    int data;
    struct BiTree *lchild, *rchild;
};
int cnt;
char str[51];

struct BiTree * createBitree()
{
    struct BiTree *root;
    if(str[cnt]==',')
    {
        root = NULL;
        cnt++;
    }
    else
    {
        root = (struct BiTree *)malloc(sizeof(struct BiTree));
        root->data = str[cnt++];
        root->lchild = createBitree();
        root->rchild = createBitree();
    }
    return root;
}

void mid(struct BiTree *root)
{
    if (root)
    {
        mid(root->lchild);
        printf("%c", root->data);
        mid(root->rchild);
    }
}

void last(struct BiTree *root)
{
    if (root)
    {
        last(root->lchild);
        last(root->rchild);
        printf("%c", root->data);
    }
}

int main()
{
    while(~scanf("%s",str))
    {
        cnt = 0;
        struct BiTree *root;
        root = createBitree();
        mid(root);
        printf("\n");
        last(root);
        printf("\n");
    }
    return 0;
}

数据结构实验之二叉树三:统计叶子数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知二叉树的一个按先序遍历输入的字符序列,如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并求二叉树的叶子结点个数。

Input

连续输入多组数据,每组数据输入一个长度小于50个字符的字符串。

Output

输出二叉树的叶子结点个数。

Sample Input

abc,,de,g,,f,,,

Sample Output

3

Reference Code

#include<stdio.h>
#include<stdlib.h>
struct BiTreeNode
{
    int data;
    struct BiTreeNode *lchild, *rchild;
};
int cnt,flag;
char str[51];

struct BiTreeNode * createBitree()
{
    struct BiTreeNode *root;
    if(str[cnt]==',')
    {
        root = NULL;
        cnt++;
    }
    else
    {
        root = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
        root->data = str[cnt++];
        root->lchild = createBitree();
        root->rchild = createBitree();
    }
    return root;
}

void mid(struct BiTreeNode *root)
{
    if (root)
    {
        if (!root->lchild&&!root->rchild)
            flag++;
        mid(root->lchild);
        mid(root->rchild);
    }
}

int main()
{
    while(~scanf("%s",str))
    {
        flag = 0;
        cnt = 0;
        struct BiTreeNode *root;
        root = createBitree();
        mid(root);
        printf("%d\n",flag);
    }
    return 0;
}

数据结构实验之二叉树四:(先序中序)还原二叉树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。

Input

输入数据有多组,每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数,随后2行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区分大小写)的字符串。

Output

输出一个整数,即该二叉树的高度。

Sample Input

9 
ABDFGHIEC
FDHGIBEAC

Sample Output

5

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct BiTreeNode
{
    int data;
    char c;
    struct BiTreeNode *lchind, *rchild;
};

char str1[100], str2[100];

struct BiTreeNode *creat(int n, char str1[], char str2[])
{
    int i = 0;
    struct BiTreeNode *root;
    if (n == 0)
        return NULL;
    root = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
    root->c = str1[0];
    for (i = 0; i < n; i++)
    {
        if (str1[0] == str2[i])
        {
            root->lchind = creat(i, str1 + 1, str2);
            root->rchild = creat(n - i - 1, str1 + i + 1, str2 + i + 1);
        }
    }
    return root;
}

int reset(struct BiTreeNode *root)
{
    if (root->lchind == NULL && root->rchild == NULL)
    {
        root->data = 1;
    }
    else if (root->lchind == NULL && root->rchild != NULL)
    {
        root->data = reset(root->rchild) + 1;
    }

    else if (root->lchind != NULL && root->rchild == NULL)
    {
        root->data = reset(root->lchind) + 1;
    }
    else if (root->lchind != NULL && root->rchild != NULL)
    {
        if (reset(root->lchind) > reset(root->rchild))
        {
            root->data = reset(root->lchind) + 1;
        }
        else
        {
            root->data = reset(root->rchild) + 1;
        }
    }
    return root->data;
}

int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        scanf("%s %s", str1, str2);
        struct BiTreeNode *root;
        root = creat(n, str1, str2);
        printf("%d\n", reset(root));
    }
    return 0;
}

数据结构实验之二叉树五:层序遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知一个按先序输入的字符序列,如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

Input

输入数据有多行,第一行是一个整数t (t<1000),代表有t行测试数据。每行是一个长度小于50个字符的字符串。

Output

输出二叉树的层次遍历序列。

Sample Input

2
abd,,eg,,,cf,,,
xnl,,i,,u,,

Sample Output

abcdefg
xnuli

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct BiTree
{
    char data;
    struct BiTree *lchild, *rchild;
};
int cnt;
char str[51];

struct BiTree *createBitree()
{
    struct BiTree *root;
    if (str[cnt] == ',')
    {
        root = NULL;
        cnt++;
    }
    else
    {
        root = (struct BiTree *)malloc(sizeof(struct BiTree));
        root->data = str[cnt++];
        root->lchild = createBitree();
        root->rchild = createBitree();
    }
    return root;
}

void cxvisit(struct BiTree *r)
{
    struct BiTree *que[100];
    int i = 0, j = 0;
    que[j++] = r;
    while (i < j)
    {
        if (que[i])
        {
            que[j++] = que[i]->lchild;
            que[j++] = que[i]->rchild;
            printf("%c", que[i]->data);
        }
        i++;
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", str);
        cnt = 0;
        struct BiTree *root;
        root = createBitree();
        cxvisit(root);
        printf("\n");
    }
    return 0;
}

数据结构实验之二叉树六:哈夫曼编码

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

字符的编码方式有多种,除了大家熟悉的ASCII编码,哈夫曼编码(Huffman Coding)也是一种编码方式,它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码,称之为最优编码。哈夫曼编码常被用于数据文件压缩中,其压缩率通常在20%~90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。

Input

输入数据有多组,每组数据一行,表示要编码的字符串。

Output

对应字符的ASCII编码长度la,huffman编码长度lh和la/lh的值(保留一位小数),数据之间以空格间隔。

Sample Input

AAAAABCD
THE_CAT_IN_THE_HAT

Sample Output

64 13 4.9
144 51 2.8

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct BiTree
{
    char data;
    int w, l, r, p;
} s[100000];

int INF = 1e9 + 7;

int main()
{
    char str[100050];
    int i, j, num, m, n, w1, w2, k1, k2, p, sum, f[100050];
    while (scanf("%s", str) != EOF)
    {
        memset(f, 0, sizeof(f));
        n = strlen(str);
        m = 0;
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < m; j++)
            {
                if (s[j].data == str[i])
                {
                    s[j].w++;
                    break;
                }
            }
            if (j == m)
            {
                s[m].data = str[i];
                s[m].w = 1;
                s[m].l = s[m].r = s[m].p = -1;
                m++;
            }
        }
        for (i = m; i < 2 * m - 1; i++)
        {
            w1 = w2 = INF;
            k1 = k2 = -1;
            for (j = 0; j < i; j++)
            {
                if (f[j])
                    continue;
                if (s[j].w < w1)
                {
                    w2 = w1;
                    k2 = k1;
                    w1 = s[j].w;
                    k1 = j;
                }
                else if (s[j].w < w2)
                {
                    w2 = s[j].w;
                    k2 = j;
                }
            }
            f[k1] = f[k2] = 1;
            s[i].w = s[k1].w + s[k2].w;
            s[i].l = k1;
            s[i].r = k2;
            s[i].p = -1;
            s[k1].p = s[k2].p = i;
        }
        sum = 0;
        for (i = 0; i < m; i++)
        {
            num = 0;
            p = s[i].p;
            while (p != -1)
            {
                num++;
                p = s[p].p;
            }
            sum += num * s[i].w;
        }
        printf("%d %d %.1f\n", n * 8, sum, 8.0 * n / sum);
    }
    return 0;
}

数据结构实验之二叉树七:叶子问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知一个按先序输入的字符序列,如abd,,eg,,,cf,,,(其中,表示空结点)。请建立该二叉树并按从上到下从左到右的顺序输出该二叉树的所有叶子结点。

Input

输入数据有多行,每一行是一个长度小于50个字符的字符串。

Output

按从上到下从左到右的顺序输出二叉树的叶子结点。

Sample Input

abd,,eg,,,cf,,,
xnl,,i,,u,,

Sample Output

dfg
uli

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct BiTree
{
    char data;
    struct BiTree *lchild, *rchild;
};
int cnt;
char str[51];

struct BiTree *createBitree()
{
    struct BiTree *root;
    if (str[cnt] == ',')
    {
        root = NULL;
        cnt++;
    }
    else
    {
        root = (struct BiTree *)malloc(sizeof(struct BiTree));
        root->data = str[cnt++];
        root->lchild = createBitree();
        root->rchild = createBitree();
    }
    return root;
}

void cxvisit(struct BiTree *r)
{
    struct BiTree *que[100];
    int i = 0, j = 0;
    que[j++] = r;
    while (i < j)
    {
        if (que[i])
        {
            que[j++] = que[i]->lchild;
            que[j++] = que[i]->rchild;
            if (!que[i]->lchild && !que[i]->rchild)
            {
                printf("%c", que[i]->data);
            }
        }
        i++;
    }
}

int main()
{
    while (~scanf("%s", str))
    {
        cnt = 0;
        struct BiTree *root;
        root = createBitree();
        cxvisit(root);
        printf("\n");
    }
    return 0;
}

数据结构实验之二叉树八:(中序后序)求二叉树的深度

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知一颗二叉树的中序遍历序列和后序遍历序列,求二叉树的深度。

Input

输入数据有多组,输入T,代表有T组数据。每组数据包括两个长度小于50的字符串,第一个字符串表示二叉树的中序遍历,第二个表示二叉树的后序遍历。

Output

输出二叉树的深度。

Sample Input

2
dbgeafc
dgebfca
lnixu
linux

Sample Output

4
3

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct BiTree
{
    char data;
    struct BiTree *lchild, *rchild;
};

char a[110], b[110];

struct BiTree *Creat(int n, char a[], char b[])
{
    if (n == 0)
        return NULL;
    char *p;
    struct BiTree *T;
    T = (struct BiTree *)malloc(sizeof(struct BiTree));
    T->data = b[n - 1];          ///树根是当前树中所有元素在后序遍历中最后出现的元素
    for (p = a; *p != '\0'; p++) ///找出根节点在中序遍历中的位置
    {
        if (*p == b[n - 1])
            break;
    }
    int t = p - a;
    T->lchild = Creat(t, a, b);                 ///根左边的元素就是左子树的全部元素,递归
    T->rchild = Creat(n - t - 1, p + 1, b + t); ///根右边的就是右子树的全部元素,递归求解
    return T;
}

int Depth(struct BiTree *T)
{
    int ldepth, rdepth;
    if (!T)
        return 0;
    else
    {
        ldepth = Depth(T->lchild);
        rdepth = Depth(T->rchild);
        return ldepth > rdepth ? ldepth + 1 : rdepth + 1;
    }
}

int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        while (n--)
        {
            memset(a, 0, sizeof(a));
            memset(b, 0, sizeof(b));
            struct BiTree *T;
            scanf("%s%s", a, b);
            int len = strlen(a);
            T = Creat(len, a, b);
            printf("%d\n", Depth(T));
        }
    }
    return 0;
}
~~End Of File~~

本文永久链接:https://blog.xmgspace.me/archives/sdut-experiments-data-structure-5.html

本文文章标题:SDUT《数据结构与算法》专题训练5 二叉树

本站欢迎转载与引用~但您需要注明文章标题与链接,并表明转载/引用自Xiaomage's Blog。

授权协议:署名-非商业性使用-相同方式共享 4.0 国际(CC BY 4.0)

标签:C语言学习 , 数据结构

还没有人评论哦,还不快抢沙发~

添加新评论

i_f01.pngi_f02.pngi_f03.pngi_f04.pngi_f05.pngi_f06.pngi_f07.pngi_f08.pngi_f09.pngi_f10.pngi_f11.pngi_f12.pngi_f13.pngi_f14.pngi_f15.pngi_f16.pngi_f17.pngi_f18.pngi_f19.pngi_f20.pngi_f21.pngi_f22.pngi_f23.pngi_f24.pngi_f25.pngi_f26.pngi_f27.pngi_f28.pngi_f29.pngi_f30.pngi_f31.pngi_f32.pngi_f33.png