数据结构——二叉搜索树PTA习题

简介: 数据结构——二叉搜索树PTA习题

单选题


image.png


选择题题解


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


7、 如下图8 是根节点,6 是左子节点



9、例如B选项:则以28为根的子树,它的左子树上既有18又有36、35.所以弃选.

C,D同理 只有A符合



函数题


6-1 是否二叉搜索树 (25分)


本题要求实现函数,判断给定二叉树是否二叉搜索树。


函数接口定义:


bool IsBST ( BinTree T );


其中BinTree结构定义如下:


typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};


函数IsBST须判断给定的T是否二叉搜索树,即满足如下定义的二叉树:


定义:一个二叉搜索树是一棵二叉树,它可以为空。如果不为空,它将满足以下性质:


非空左子树的所有键值小于其根结点的键值。


非空右子树的所有键值大于其根结点的键值。


左、右子树都是二叉搜索树。


如果T是二叉搜索树,则函数返回true,否则返回false。


输入样例1:如下图



输出样例1:


Yes


输入样例2:如下图



输出样例2:


No


代码


#include <stdio.h>
#include <stdlib.h>
typedef enum { false, true } bool;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
BinTree BuildTree(); /* 由裁判实现,细节不表 */
bool IsBST ( BinTree T );
int main()
{
    BinTree T;
    T = BuildTree();
    if ( IsBST(T) ) printf("Yes\n");
    else printf("No\n");
    return 0;
}
/* 你的代码将被嵌在这里 */
bool IsBST(BinTree T)
{
  BinTree p;
  if (!T)   // 树为空
    return true;
  if (!T->Left && !T->Right)  // 只有根节点
    return true;
  p = T->Left;  // 先向左查
  if (p)
  {
    while (p->Right)//左子树的最大值在右下角
      p = p->Right;
    if (p->Data > T->Data)
      return false;
  }
  p = T->Right; // 再向左查
  if (p)
  {
    while (p->Left)//右子树的最小值在左下角
      p = p->Left;
    if (p->Data < T->Data)
      return false;
  }
  return 
    IsBST(T->Left) && IsBST(T->Right);  // 运用递归再查每个左右子树
}


编程题


7-1 是否同一棵二叉搜索树 (25分)


给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。


输入格式:


输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L,分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列。最后L行,每行给出N个插入的元素,属于L个需要检查的序列。


简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。


输出格式:


对每一组需要检查的序列,如果其生成的二叉搜索树跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。


输入样例:


4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0


输出样例:


Yes
No
No


代码


#include<iostream>
#include<queue>
using namespace std;
struct BSTNode {
  //数据域
  int val;
  //指针域
  BSTNode *left,
    *right;
  //节点的构造
  BSTNode(int v)
  {
    val = v;
    left = NULL;
    right = NULL;
  }
};
//BST的数据结构
class BST {
private:
  BSTNode *root;
public:
  BST() { root = NULL; }
  //通过插入函数构造BST
  void insert(int n);
  //比较另一棵BST与本树是否相同
  bool jugde(BST t);
};
void BST::insert(int n)
{
  BSTNode *p = root,
       *pp = NULL;
  while (p != NULL)
  {
    pp = p;
    if (p->val>n) p = p->left;
    else p = p->right;
  }
  BSTNode *t = new BSTNode(n);
  if (root != NULL)
    if (pp->val > n) pp->left = t;
    else pp->right = t;
  else root = t;
}
//通过层序遍历,对比
bool BST::jugde(BST t)
{
  BSTNode*t1 = root,
    *t2 = t.root;
  queue<BSTNode*>q1,q2;
  while (t1 != NULL && t2 != NULL)
  {
    if (t1->val != t2->val) return false;
    if ((t1->left != NULL && t2->left == NULL) || (t1->left == NULL && t2->left != NULL)|| (t1->right != NULL && t2->right == NULL) || (t1->right == NULL && t2->right != NULL)) return false;
    if ((t1->left != NULL && t2->left != NULL)) { q1.push(t1->left); q2.push(t2->left); }
    if ((t1->right != NULL && t2->right != NULL)) { q1.push(t1->right); q2.push(t2->right); }
    if (q1.size() != 0 && q2.size() != 0)
    {
      t1 = q1.front(); t2=q2.front();
      q1.pop(); q2.pop();
    }
    else t1 = NULL;
  }
  return true;
}
int main()
{
  int n, m;
  while (cin>>n,cin>>m)
  {
    BST bst;
    for (int i = 0; i < n; i++)
    {
      int num; cin >> num;
      bst.insert(num);
    }
    for (int i = 0; i < m; i++)
    {
      BST t;
      for(int j=0;j<n;j++)
      {
        int num; cin >> num;
        t.insert(num);
      }
      if (bst.jugde(t)) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}
相关文章
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
3月前
|
存储 Java Serverless
【数据结构】哈希表&二叉搜索树详解
本文详细介绍了二叉搜索树和哈希表这两种数据结构。二叉搜索树是一种特殊二叉树,具有左子树节点值小于根节点、右子树节点值大于根节点的特点,并且不允许键值重复。文章给出了插入、删除和搜索等方法的具体实现。哈希表则通过哈希函数将键名映射为数组下标,实现快速查找,其插入、删除和查找操作时间复杂度理想情况下为O(1)。文中还讨论了哈希函数的设计原则、哈希冲突的解决方法及哈希表的实现细节。
60 8
【数据结构】哈希表&二叉搜索树详解
|
2月前
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现(三)
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现
|
2月前
|
存储
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现(二)
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现
|
2月前
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现(一)
【高阶数据结构】深度探索二叉树进阶:二叉搜索树概念及其高效实现
|
2月前
【数据结构】二叉搜索树的功能实现详解
【数据结构】二叉搜索树的功能实现详解
29 0
|
6月前
数据结构学习记录——判断是否为同一颗二叉搜索树(题意理解、求解思路、程序搭建框架、具体函数的实现)
数据结构学习记录——判断是否为同一颗二叉搜索树(题意理解、求解思路、程序搭建框架、具体函数的实现)
56 2
|
6月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
79 1
|
6月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
48 1