完全二叉树和正则二叉树
时间: 2023-07-24 12:07:03 浏览: 110
完全二叉树是一种特殊的二叉树,其中除了最后一层,其他层的节点都是满的,最后一层的节点都靠左排列。正则二叉树是一种特殊的二叉树,其中每个节点要么没有子节点,要么有两个子节点。
完全二叉树和正则二叉树的区别在于,完全二叉树可以有只有一个子节点的节点,而正则二叉树不可以。另外,完全二叉树的高度可以是 $log_2(n)$,其中 $n$ 是节点数,而正则二叉树的高度可以是 $n$,其中 $n$ 是节点数。
需要注意的是,完全二叉树和正则二叉树并不是互斥的概念。例如,一个只有根节点的二叉树既是完全二叉树,也是正则二叉树。
相关问题
以二叉链表为二叉树的存储结构,设计一个算法判断一棵二叉树是否是正则二叉树。正则二叉树是指在二叉树中不存在度为1的结点。
以下是判断一棵二叉树是否是正则二叉树的Python算法:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 判断一棵二叉树是否是正则二叉树
def is_regular_binary_tree(root):
if not root:
return True
if not root.left and not root.right:
return True
if not root.left or not root.right:
return False
return is_regular_binary_tree(root.left) and is_regular_binary_tree(root.right)
# 测试代码
# 创建一棵正则二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(is_regular_binary_tree(root)) # 输出:True
# 创建一棵非正则二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
print(is_regular_binary_tree(root)) # 输出:False
```
设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的结点。 【输入说明】二叉树的前序和中序遍历序列,以此构造二叉树的链式存储
算法思路:
对于一个节点,如果其左子树或右子树为空,则其子树个数为1,不满足正则二叉树的定义。否则,递归判断其左右子树是否为正则二叉树。
具体实现:
1. 根据前序遍历序列和中序遍历序列构造二叉树。
2. 编写一个函数判断当前节点的子树是否为正则二叉树,若是,则返回子树中节点数量,否则返回-1。
3. 在判断根节点是否为正则二叉树时,若其左右子树都为正则二叉树且子树节点数量都不为1,则该树为正则二叉树。
完整代码如下:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
return root
def isRegularBT(self, root):
if not root:
return 0
left_cnt = self.isRegularBT(root.left)
right_cnt = self.isRegularBT(root.right)
if left_cnt == -1 or right_cnt == -1:
return -1
if left_cnt == 1 and not root.left or right_cnt == 1 and not root.right:
return -1
return left_cnt + right_cnt + 1
def isRegularBinaryTree(self, preorder, inorder):
root = self.buildTree(preorder, inorder)
if self.isRegularBT(root) == -1:
return False
else:
return True
```
例如,对于二叉树的前序遍历序列为[1, 2, 4, 5, 3, 6, 7],中序遍历序列为[4, 2, 5, 1, 6, 3, 7]的二叉树,可以使用以下代码进行判断:
```python
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
s = Solution()
print(s.isRegularBinaryTree(preorder, inorder))
```
输出结果为True,说明该二叉树是正则二叉树。