以二叉链表作为二叉树的存储结构,在键盘上输入一个字符串 ①统计二叉树的叶子结点个数。 ②交换二叉树中每个结点的左孩子和右孩子,最后按先序遍历输出。 ③计算二叉树的最大宽度(所有层中结点个数的最大值)。 ④用层次遍历二叉树的方法,统计树中度为 1 的结点个数。
时间: 2024-02-11 17:05:05 浏览: 25
好的,我会尽力回答你的问题。让我们逐个解答。
1. 统计二叉树的叶子结点个数
统计二叉树的叶子结点个数可以使用递归的方法实现。具体步骤如下:
- 如果当前节点为空,则返回0
- 如果当前节点为叶子节点(即左右子树都为空),则返回1
- 否则,递归地计算左子树和右子树的叶子节点个数,将它们相加并返回结果。
下面是一个示例代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
```
2. 交换二叉树中每个结点的左孩子和右孩子,最后按先序遍历输出
交换二叉树中每个结点的左孩子和右孩子可以使用递归的方法实现。具体步骤如下:
- 如果当前节点为空,则返回None
- 否则,交换当前节点的左右子树,递归地交换左子树和右子树。
下面是一个示例代码:
```python
def swap_tree(root):
if not root:
return None
root.left, root.right = root.right, root.left
swap_tree(root.left)
swap_tree(root.right)
return root
# 先序遍历输出交换后的结果
def preorder_traversal(root):
if not root:
return
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
# 示例代码的使用
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
preorder_traversal(swap_tree(root))
```
3. 计算二叉树的最大宽度
计算二叉树的最大宽度可以使用层次遍历的方法实现。具体步骤如下:
- 定义一个队列,将根节点加入队列中
- 当队列不为空时,遍历队列中的所有节点,并统计当前层的节点个数
- 将当前层的所有非空节点的左右子树加入队列中
- 更新最大宽度的值
下面是一个示例代码:
```python
def max_width(root):
if not root:
return 0
queue = [root]
max_width = 1
while queue:
level_size = len(queue)
max_width = max(max_width, level_size)
for i in range(level_size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return max_width
# 示例代码的使用
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
print(max_width(root))
```
4. 用层次遍历二叉树的方法,统计树中度为 1 的结点个数
用层次遍历二叉树的方法,统计树中度为1的结点个数可以使用和计算最大宽度类似的方法实现。具体步骤如下:
- 定义一个队列,将根节点加入队列中
- 当队列不为空时,遍历队列中的所有节点,并统计当前节点的度数
- 将当前节点的非空子节点加入队列中
下面是一个示例代码:
```python
def count_degree_1_nodes(root):
if not root:
return 0
queue = [root]
count = 0
while queue:
node = queue.pop(0)
degree = 0
if node.left:
degree += 1
queue.append(node.left)
if node.right:
degree += 1
queue.append(node.right)
if degree == 1:
count += 1
return count
# 示例代码的使用
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(count_degree_1_nodes(root))
```
希望这些答案能够帮助到你,如果你还有其他问题,欢迎继续询问。