设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的结点。二叉树的前序和中序遍历序列,以此构造二叉树的链式存储,若该二叉树是一棵正则二叉树,则输出Yes,否则输出No
时间: 2023-11-14 18:15:00 浏览: 115
以下是算法实现:
1. 如果二叉树为空,返回Yes
2. 如果二叉树只有一个结点,返回Yes
3. 如果左子树为空,但右子树非空,返回No
4. 如果右子树为空,但左子树非空,返回No
5. 对左子树和右子树分别进行递归判断,如果均为正则二叉树,则返回Yes,否则返回No
代码如下:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def is_regular_binary_tree(preorder, inorder):
if not preorder or not inorder:
return True
if len(preorder) == 1 and len(inorder) == 1:
return True
if len(preorder) != len(inorder):
return False
root_val = preorder[0]
root_idx = inorder.index(root_val)
left_inorder = inorder[:root_idx]
right_inorder = inorder[root_idx+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
if not left_inorder and right_inorder:
return False
if not right_inorder and left_inorder:
return False
return is_regular_binary_tree(left_preorder, left_inorder) and is_regular_binary_tree(right_preorder, right_inorder)
preorder = [1,2,4,5,3,6,7]
inorder = [4,2,5,1,6,3,7]
root = Node(preorder[0])
root.left = Node(preorder[1])
root.right = Node(preorder[-1])
print("Yes" if is_regular_binary_tree(preorder, inorder) else "No")
```
输入的是前序和中序遍历序列,如果该二叉树是一棵正则二叉树,则输出Yes,否则输出No。
阅读全文