单选题
选择题题解
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; }
