c++判定给定二叉树是否为二叉排序树
时间: 2023-11-20 07:11:39 浏览: 52
判断给定二叉树是否为二叉排序树的方法如下:
1. 对于每个节点,其左子树所有节点的值都小于该节点的值,右子树所有节点的值都大于该节点的值。
2. 对于整棵树,每个节点都满足上述条件。
可以采用中序遍历的方法依次比较每个节点的值,如果中序遍历的结果是单调递增的,则该树为二叉排序树。以下是基于此方法的 C++ 代码实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树结点定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 中序遍历二叉树
void inorderTraversal(TreeNode* root, vector<int>& v) {
stack<TreeNode*> s;
TreeNode* p = root;
while (p != NULL || !s.empty()) {
while (p != NULL) {
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
s.pop();
v.push_back(p->val);
p = p->right;
}
}
}
// 判断二叉树是否为二叉排序树
bool isBST(TreeNode* root) {
if (root == NULL) return true;
vector<int> v;
inorderTraversal(root, v);
for (int i = 1; i < v.size(); i++) {
if (v[i] <= v[i-1]) return false;
}
return true;
}
// 测试
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(6);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(4);
root->right->right = new TreeNode(7);
if (isBST(root)) {
cout << "该二叉树是二叉排序树" << endl;
} else {
cout << "该二叉树不是二叉排序树" << endl;
}
return 0;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)