编写算法判别给定二叉树是否为2x排序数是此二叉数以二叉链表为存储结构且树中节点的关键词均不同
时间: 2024-03-23 22:42:59 浏览: 91
判断一棵二叉树是否为2x排序树,需要满足以下条件:
1. 左子树中所有节点的关键词均小于根节点的关键词;
2. 右子树中所有节点的关键词均大于根节点的关键词;
3. 左子树和右子树都是2x排序树。
因此,可以采用递归的方式进行判断。具体实现过程如下:
1. 如果当前节点为空,则返回true;
2. 如果当前节点左子树或右子树不是2x排序树,则返回false;
3. 如果当前节点左子树中存在关键词大于等于当前节点的关键词,则返回false;
4. 如果当前节点右子树中存在关键词小于等于当前节点的关键词,则返回false;
5. 否则,返回true。
具体的代码实现如下:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_bst(root):
if root is None:
return True
if root.left is not None and root.left.val >= root.val:
return False
if root.right is not None and root.right.val <= root.val:
return False
return is_bst(root.left) and is_bst(root.right)
def is_2x_bst(root):
if root is None:
return True
if root.left is not None and not is_bst(root.left):
return False
if root.right is not None and not is_bst(root.right):
return False
return is_2x_bst(root.left) and is_2x_bst(root.right)
# 测试
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.left = Node(12)
root.right.right = Node(20)
print(is_2x_bst(root)) # True
```
阅读全文