给定二叉树判断是否为二叉排序树代码
时间: 2023-08-28 07:03:37 浏览: 73
以下是判断二叉树是否为二叉排序树(BST)的代码,其中假设二叉树中不包含重复的节点值:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_bst(root):
def dfs(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
if node.val <= lower or node.val >= upper:
return False
return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper)
return dfs(root)
```
该算法使用深度优先搜索(DFS)遍历二叉树,同时维护每个节点的上下界,判断每个节点是否在其对应的上下界范围内。如果二叉树中的所有节点都满足该条件,则该二叉树为二叉排序树。
注意,该算法的时间复杂度为O(n),其中n为二叉树中的节点数。
相关问题
判别给定二叉树是否为二叉排序树的算法
判断给定二叉树是否为二叉排序树的算法如下:
1. 如果二叉树为空,则返回 true。
2. 如果二叉树不为空,则判断其左子树是否为二叉排序树,如果不是,则返回 false。
3. 判断当前节点是否大于其左子树的最大值,如果不是,则返回 false。
4. 判断当前节点是否小于其右子树的最小值,如果不是,则返回 false。
5. 判断其右子树是否为二叉排序树,如果不是,则返回 false。
6. 如果以上条件都满足,则返回 true。
其中,判断一个二叉树是否为二叉排序树,需要用到中序遍历,即先遍历左子树,再遍历根节点,最后遍历右子树。如果遍历的结果是一个递增的序列,则该二叉树为二叉排序树。
c++判定给定二叉树是否为二叉排序树
判断给定二叉树是否为二叉排序树的方法如下:
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;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)