数据结构学习记录——判断是否为同一颗二叉搜索树(题意理解、求解思路、程序搭建框架、具体函数的实现)

简介: 数据结构学习记录——判断是否为同一颗二叉搜索树(题意理解、求解思路、程序搭建框架、具体函数的实现)

题意理解

给定一个插入序列就可以唯一确定一颗二叉搜索树

但是,一颗给定的二叉搜索树却可以由多种不同的插入序列得到。

例如,按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树,都得到一样的结果。


问题

描述

对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

输入样例

4 2              第一部分是两个整数:4表示插入二叉搜索树的节点数、2表示要进行比较的序列

3 1 4 2        第二部分是输入的序列                                                    

3 4 1 2        第三部分是后面输入的序列,它们全部都要与第二部分进行对比,判断是否一样

3 2 4 1

2 1

2 1

1 2

0

输出样例

Yes

No

No

求解思路

建两棵二叉树

根据两个序列分别建树,再去递归判别两棵树是否一样。

不建树

例如:

3 1 2 4 对比 3 4 1 2,3都是根结点。

那找出所有比3大的结点和所有比3小的结点,发现:


很显然,我们能看出他们是同一棵二叉搜索树了。

再来对比一组:3  1  2  4、3  2  4  1。

这一组序列并不是同一棵二叉搜索树。

建一棵树

根据结点数来建立一棵二叉搜索树T,再来判别一个序列是否与二叉搜索树T一致。

分为三部分:

  1. 搜索树表示
  2. 建立搜索树T
  3. 判别一序列是否与搜索树T一致

搜索树表示

typedef struct TreeNode* Tree;
struct TreeNode
{
  int v;
  Tree Left, Right;
  int flag;
};

程序框架搭建

int main()

{

   对每组数据

       1.读入N和L

        2.根据第一行序列建树T

       3.依据树T分别判别后面的L个序列是否能与T形成同一搜索树并输出结果。

       return 0;

}


需要设计的主要函数:

  • 读数据建立搜索树T
  • 判别一序列是否与T构成一样的搜索树
int main()
{
  int N, L, i;
  Tree T;
  scanf("%d", &N);
  while (N)
  {
    scanf("%d", &L);
    T = MakeTree(N);
    for (i = 0; i < L; i++)
    {
      if (Judge(T, N))
        printf("Yes\n");
      else
        printf("No\n");
      ResetT(T); /*清除T中的所有标记flag*/
    }
    FreeTree(T);
    scanf("%d", &N);
  }
  return 0;
}

如何建搜索树

Tree MakeTree(int N)
{
  Tree T;
  int i, V;
  scanf("%d", &V);
  T = NewNode(V);
  for (i = 1; i < N; i++)
  {
    scanf("%d", &V);
    T = Insert(T,V);
  }
  return T;
}
Tree Newnode(int V)
{
  Tree T = (Tree*)malloc(sizeof(struct TreeNode));
  T->v = V;
  T->Left = T->Right = NULL;
  T->flag = 0;
  return T;
}
Tree Insert(Tree T, int V)
{
  if (!T)
    T = NewNode(V);
  else
  {
    if (V > T->v)
      T->Right = Insert(T->Right, V);
    else
      T->Left = Insert(T->Left, V);
  }
  return T;
}

如何判别

如何判别序列3  2  4  1是否与树T一致呢?

方法

在树T中按顺序搜索序列3  2  4  1中的每个数:

  • 如果每次搜索所经过的结点在前面均出现过,则一致
  • 否则(某次搜索中遇到前面未出现过的结点),则不一致

查找函数

check函数接受两个参数:一个二叉搜索树T和一个整数V。

函数的返回值为整型。


在二叉搜索树T中查找整数V, 如果找到了,则将该结点的标记flag设为1,并返回1;


如果没有找到,则返回0。


用递归的方式:首先判断当前结点是否被标记,如果被标记,则根据V与当前结点的大小关系,递归地查找左子树或右子树。


如果当前结点未被标记,则判断V是否等于当前结点的值, 如果等于,则将该结点的标记设为1,并返回1;

否则返回0。

int check(Tree T, int V)
{
  if (T->flag)
  {
    if (V < T->v)
    {
      return check(T->Left, V);
    }
    else if (V > T->v)
    {
      return check(T->Right, V);
    }
    else
      return 0;
  }
  else
  {
    if (V == T->v)
    {
      T->flag = 1;
      return 1;
    }
    else
    {
      return 0;
    }
  }
}

判断函数

int Judge(Tree T, int N)
{
  int i, V;
  scanf("%d", &V);
  if (V != T->v)
  {
    return 0;
  }
  else
  {
    T->flag = 1;
  }
  for (i = 1; i < N; i++)
  {
    scanf("%d", &V);
    if (!check(T, V)) 
    return 0;
  }
  return 1;
}1. int J

函数有两个参数:一个是指向树的指针T,另一个是整数N。


首先从输入中读取一个整数V,如果V不等于树T的根结点值,则返回0, 表示输入的第一个数与树T不匹配。


如果V等于树T的根结点值,则将根结点的标记flag设置为1, 表示该节点已经被访问过。


接下来,用一个循环来读取剩余的N-1个整数。


对于每个整数V,函数调用check函数来检查树T中是否存在一个结点的值等于V。


如果不存在这样的节点,则返回0,表示输入的整数与树T不匹配。


如果存在这样的节点,则将该节点的标记flag设置为1, 表示该节点已经被访问过。


最后,如果所有的输入整数都能在树T中找到对应的节点,则返回1,表示输入的整数与树T匹配。


但是这段代码是存在bug的,当发现序列中的某个数与T不一致时,返回0程序结束,而不会把后面的数读完了。


那么就会误把后面的数当成下一组序列来看了,导致序列错乱了。


所以,当发现序列中的某个数与T不一致时,必须把序列后面的数都读完。

据此来改进代码:

int Judge(Tree T, int N)
 
{
  int i, V, flag = 0;
 
  /*flag:0代表目前还一致,1代表已经不一致*/
 
  scanf("%d", &V);
 
  if (V != T->v)flag = 1;
  else T->flag = 1;
  for (i = 1; i < N; i++)
  {
    scanf("%d", &V);
    if ((!flag) && (!check(T,V)))
      flag = 1;
  }
  if (flag) 
    return 0;
  else 
    return 1;
}

输入参数为一个指向二叉树根结点的指针T和一个整数N,表示序列的长度。


函数的返回值为1或0,表示给定的二叉树是否与序列匹配。


首先从输入中读取第一个整数V,表示序列中的第一个元素。


如果V与二叉树根结点的值不相等,则将flag(这里是函数内部的flag标记)标记为1,表示当前已经不一致了;


否则将根节点的flag(这里是结点内的flag标记,表示是否访问过)标记为1,表示已经匹配上了。


再循环读取序列中的剩余元素,每次读取一个整数V。


如果当前已经不一致了(即flag为1),则直接跳过后面的元素。


如果当前还一致,并且当前节点的值等于V,则将当前节点的flag标记为1,表示已经匹配上了;


否则将flag标记为1,表示当前已经不一致了。


循环结束后,如果flag为1,则说明序列与二叉树不匹配,返回0;


否则返回1,表示匹配成功。

其他函数

清除T中各结点的flag标记

void ResetT(Tree T) /*清除T中各结点的flag标记*/
{
  if (T->Left)
    ResetT(T->Left);
  if (T->Right)
    ResetT(T->Right);
  T->flag = 0;
}

先递归处理其左子树,再递归处理其右子树, 最后将该结点的flag标记设为0,表示清除标记。 这样,整个二叉树中所有节点的flag标记都被清除了。

释放T的空间

void FreeTree(Tree T) /*释放T的空间*/
{
  if (T->Left)
    FreeTree(T->Left);
  if (T->Right)
    FreeTree(T->Right);
  free(T);
}

end



目录
相关文章
|
21天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
43 5
|
20天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
49 1
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
29天前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
51 4
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!