以二叉链表作为二叉树的存储结构,读入字符串(如“abcd00e00f00ig00h00”), ①统计二叉树的叶子结点个数。 ②交换二叉树中每个结点的左孩子和右孩子,最后按先序遍历输出。 ③计算二叉树的最大宽度(所有层中结点个数的最大值)。 ④用层次遍历二叉树的方法,统计树中度为 1 的结点个数。
时间: 2024-02-09 21:12:06 浏览: 32
好的,我来回答这个问题。
首先,根据题目给出的字符串“abcd00e00f00ig00h00”,我们可以得到二叉树的结构如下:
```
a
/ \
b h
/ \
i g
/ \
f e
/
d
```
接下来,针对每个问题,我分别给出解答:
1. 统计二叉树的叶子结点个数。
遍历整个二叉树,对于每个结点,如果它没有左右孩子,则认为它是叶子结点。统计所有叶子结点的个数即可。
代码如下:
```python
def count_leaf_node(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_node(root.left) + count_leaf_node(root.right)
```
2. 交换二叉树中每个结点的左孩子和右孩子,最后按先序遍历输出。
遍历整个二叉树,对于每个结点,交换它的左右孩子。然后按照先序遍历的顺序输出整个二叉树。
代码如下:
```python
def exchange_left_right(root):
if not root:
return
root.left, root.right = root.right, root.left
exchange_left_right(root.left)
exchange_left_right(root.right)
def preorder_traversal(root):
if not root:
return
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
```
3. 计算二叉树的最大宽度(所有层中结点个数的最大值)。
使用队列进行层次遍历,对于每一层,统计该层的结点个数,并与一个变量max_width比较,取较大值。最后返回max_width。
代码如下:
```python
from collections import deque
def max_width(root):
if not root:
return 0
q = deque([root])
max_width = 1
while q:
level_size = len(q)
max_width = max(max_width, level_size)
for i in range(level_size):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return max_width
```
4. 用层次遍历二叉树的方法,统计树中度为 1 的结点个数。
使用队列进行层次遍历,对于每个结点,如果它的度为1,则统计个数。最后返回个数即可。
代码如下:
```python
from collections import deque
def count_degree_one_node(root):
if not root:
return 0
q = deque([root])
count = 0
while q:
node = q.popleft()
if (node.left and not node.right) or (node.right and not node.left):
count += 1
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return count
```
希望我的回答能够帮到你。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)