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

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

2022考研复习重置版

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

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

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

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

字符的编码方式有多种,除了大家熟悉的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>
void arrange(int *a, int lt, int rt)
{
  int key = a[lt], i = lt, j = rt;
  if (i >= j)
    return;
  while (i < j)
  {
    while (i < j && a[j] >= key)
      j--;
    a[i] = a[j];
    while (i < j && a[i] <= key)
      i++;
    a[j] = a[i];
  }
  a[i] = key;
  arrange(a, lt, i - 1);
  arrange(a, i + 1, rt);
}
int main()
{
  int len, i;
  char s[500];
  int q[1000], t[1000];
  while (~scanf("%s", s))
  {
    int head = 0, tail = 0;
    memset(t, 0, sizeof(t));
    len = strlen(s);
    for (i = 0; i < len; i++)
    {
      t[s[i]]++;
    }
    for (i = 0; i < 500; i++)
    {
      if (t[i])
      {
        q[head++] = t[i];
      }
    }
    arrange(q, 0, head - 1);

    int sum = 0;
    int a, b;
    while (head != tail)
    {
      a = q[tail++];
      if (head != tail)
      {
        b = q[tail++];
        sum += a + b;
        q[head++] = a + b;
        arrange(q, tail, head - 1);
      }
    }
    printf("%d %d %.1lf\n", len * 8, sum, 1.0 * len * 8 / 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;
}

二叉树

Description

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

Input

多组测试数据,对于每组测试数据,输入一个长度小于50的按前序遍历输入的字符序列。

Output

对于每组测试数据,第1行输出其前序遍历序列、第2行输出其中序遍历序列、第3行输出其后序遍历序列、第4行输出其深度、第5行输出其叶子数。

Sample Input

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

Sample Output

abcdegf
cbegdfa
cgefdba
abcdefg
5
3

Reference Code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct BiTree
{
  int data;
  struct BiTree *lchild, *rchild;
};
int cnt;
int leaf;
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 front(struct BiTree *root)
{
  if (root)
  {
    printf("%c", root->data);
    front(root->lchild);
    front(root->rchild);
  }
}
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 depth(struct BiTree *root)
{
  int ldepth, rdepth;
  if (!root)
    return 0;
  else
  {
    ldepth = depth(root->lchild);
    rdepth = depth(root->rchild);
    return ldepth > rdepth ? ldepth + 1 : rdepth + 1;
  }
}
void leaves(struct BiTree *root)
{
  if (root)
  {
    if (!root->lchild && !root->rchild)
      leaf++;
    leaves(root->lchild);
    leaves(root->rchild);
  }
}
void cxvisit(struct BiTree *root)
{
    struct BiTree *que[100];
    int i = 0, j = 0;
    que[j++] = root;
    while (i < j)
    {
        if (que[i])
        {
            que[j++] = que[i]->lchild;
            que[j++] = que[i]->rchild;
            printf("%c", que[i]->data);
        }
        i++;
    }
}
int main()
{
  while (~scanf("%s", str))
  {
    cnt = 0;
    leaf = 0;
    struct BiTree *root;
    root = createBitree();
    front(root);
    printf("\n");
    mid(root);
    printf("\n");
    last(root);
    printf("\n");
    cxvisit(root);
    printf("\n");
    printf("%d\n", depth(root));
    leaves(root);
    printf("%d\n",leaf);
  }
  return 0;
}

迷失の搜索树

Description

小璐在机缘巧合之下获得了一个二叉搜索树,这个二叉搜索树恰好有n个节点,每个节点有一个权值,每个节点的权值都在[1,n]这个区间内,并且两两不相同,真是优美的性质啊

但是命运的不公又让她失去了这个二叉搜索树

幸运的是,她还记得自己丢失的二叉搜索树的前序遍历序列。

在丢了二叉搜索树之后,小璐无比想念她的这个树的后序遍历

那么问题来了,聪明的你在知道这个二叉搜索树的前序遍历的序列的情况下,能帮她找到这个二叉搜索树的后序遍历嘛?

Input

多组输入,以文件结尾

每组数据第一行为一个整数n,代表这个二叉搜索树的节点个数(1<=n<=100)

接下来一行n个整数,代表这个二叉搜索树的前序遍历序列

Output

输出n个整数

表示这个二叉树的后序遍历序列

Sample Input

5
4 2 1 3 5

Sample Output

1 3 2 5 4

Hint

二叉查找树是一棵空树,或者是具有下列性质的二叉树:

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值

若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

它的左、右子树也分别为二叉排序树

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct BiTree
{
  int data;
  struct BiTree *lchild, *rchild;
};
struct BiTree *creat(int str, struct BiTree *root)
{
  if (root == NULL)
  {
    root = (struct BiTree *)malloc(sizeof(struct BiTree));
    root->data = str;
    root->lchild = root->rchild = NULL;
    return root;
  }
  if (root->data > str)
  {
    root->lchild = creat(str, root->lchild);
  }
  else
  {
    root->rchild = creat(str, root->rchild);
  }
  return root;
};
int flag;
void print(struct BiTree *root)
{
  if (root != NULL)
  {
    print(root->lchild);
    print(root->rchild);
    if (flag == 0)
    {
      printf("%d", root->data);
      flag = flag + 1;
    }
    else
      printf(" %d", root->data);
  }
}
int main()
{
  int str, n;
  while (scanf("%d", &n) != EOF)
  {
    flag = 0;
    struct BiTree *root = NULL;
    while (n--)
    {
      scanf("%d", &str);
      root = creat(str, root);
    }
    print(root);
    printf("\n");
  }
  return 0;
}

巨斧砍大树

Description

阿福最近练就了一个新的招式:巨斧砍大树。这个招式可以砍掉一颗二叉搜索树的某个子树。现在,阿福面前有一颗 nn 个结点的二叉搜索树,他要使用 mm 次招式,于是他想询问你每次使用「巨斧砍大树」后二叉搜索树会被砍成什么样子。

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。

Input

第一行输入 22 个整数 nn, mm (1 \leqslant n, m \leqslant 10)(1⩽n,m⩽10)。表示二叉搜索树的结点个数和招式使用次数。

第二行输入 nn 个空格隔开的整数 vv (1 \leqslant v \leqslant 10)(1⩽v⩽10),表示二叉搜索树是以此序列顺序插入生成的二叉树(保证互不相同)。

接下来输入 mm 行,每行一个整数 ww (1 \leqslant w \leqslant 10)(1⩽w⩽10),表示阿福要砍掉结点上数值为 ww 的子树(保证 ww 是初始二叉树上存在的数值)。

Output

对于每次砍树,如果成功砍掉子树,则先输出一行 Cut x,其中 xx 为被砍掉子树的根节点上的数值。如果要砍掉的结点在之前已被砍掉,则输出一行 Already cut x,xx 的含义同上。

随后输出一行,表示此次砍树结束后当前二叉树的中序遍历结果,以空格分隔(行末没有多余空格,如果整颗二叉树已为空,则输出一行空行)。

Sample Input

5 5
1 3 2 4 5
5
2
3
4
1

Sample Output

Cut 5
1 2 3 4
Cut 2
1 3 4
Cut 3
1
Already cut 4
1
Cut 1

Refrence Code

#include <stdio.h>
typedef struct node
{
  int data;
  struct node *lc, *rc;
} tree;
int flag;
tree *creat(tree *root, int x)
{
  if (root == NULL)
  {
    root = (tree *)malloc(sizeof(tree));
    root->data = x;
    root->lc = root->rc = NULL;
    return root;
  }
  if (x < root->data)
    root->lc = creat(root->lc, x);
  else
    root->rc = creat(root->rc, x);
  return root;
}
tree *cut(tree *root, int x)
{
  if (root == NULL)
  {
    flag = 1;
    return root;
  }
  if (root->data == x)
  {
    root->lc = NULL;
    root->rc = NULL;
    root = NULL;
    flag = 0;
    return root;
  }
  else if (root->data < x)
    root->rc = cut(root->rc, x);
  else if (root->data > x)
    root->lc = cut(root->lc, x);
  return root;
}
void mid(tree *root)
{
  if (root)
  {
    mid(root->lc);
    if (flag == 1)
    {
      flag = 0;
      printf("%d", root->data);
    }
    else
      printf(" %d", root->data);
    mid(root->rc);
  }
}
int main()
{
  int n, m, x;
  tree *root;
  root = NULL;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    root = creat(root, x);
  }
  while (m--)
  {
    scanf("%d", &x);
    root = cut(root, x);
    if (flag == 0)
      printf("Cut %d\n", x);
    else
      printf("Already cut %d\n", x);
    flag = 1;
    mid(root);
    printf("\n");
  }
  return 0;
}
本文永久链接:https://blog.xmgspace.me/archives/sdut-experiments-data-structure-5.html
本文文章标题:SDUT《数据结构与算法》专题训练5 二叉树
如文章内无特殊说明,只要您标明转载/引用自Xiaomage's Blog,您就可以自由的转载/引用文章。禁止CSDN/采集站采集转载。
授权协议:署名-非商业性使用-相同方式共享 4.0 国际(CC BY 4.0)
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇