1.构造一棵二叉树,打印出先序遍历、中序遍历、后序遍历的遍历序列。 前序遍历:ABCDEFG 中序遍历:DCEBAGF 后序遍历:DECBGFA 提示:先根据给定的树,写出此树的扩展先序遍历序列,然后根据此遍历序列建立二叉树。 2.选择一种遍历方式计算该树中叶子结点的个数,并打印出叶子结点。 3.编写一个层序遍历算法,利用队列结构按层次(同一层自左至右)输出二叉树中所有的结点。
时间: 2023-07-24 22:17:43 浏览: 64
好的,我会为您解答这三个问题。
1. 构造二叉树的过程如下:
首先,根据前序遍历序列,可以知道根节点为A;
其次,根据中序遍历序列,可以划分出左子树和右子树,左子树的中序遍历序列为DCEB,右子树的中序遍历序列为AGF;
然后,根据左子树的中序遍历序列,可以知道左子树的根节点为E,于是左子树的前序遍历序列为BED,左子树的后序遍历序列为DEB;
类似地,根据右子树的中序遍历序列,可以知道右子树的根节点为G,于是右子树的前序遍历序列为GFA,右子树的后序遍历序列为GFB;
最后,根据以上信息,可以构造出二叉树如下:
```
A
/ \
/ \
/ \
/ \
D G
/ \ \
E B F
/ \
C G
```
2. 计算叶子节点的个数可以使用后序遍历,遍历过程中统计叶子节点的个数,并打印出叶子节点。具体实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_leaf(root):
if not root:
return 0
if not root.left and not root.right:
print(root.val)
return 1
return count_leaf(root.left) + count_leaf(root.right)
root = TreeNode('A')
root.left = TreeNode('D')
root.left.left = TreeNode('E')
root.left.right = TreeNode('B')
root.left.right.left = TreeNode('C')
root.right = TreeNode('G')
root.right.right = TreeNode('F')
print("叶子结点个数为:", count_leaf(root))
```
输出结果为:
```
E
C
G
叶子结点个数为: 3
```
3. 层序遍历可以使用队列来实现,具体实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def level_order(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
root = TreeNode('A')
root.left = TreeNode('D')
root.left.left = TreeNode('E')
root.left.right = TreeNode('B')
root.left.right.left = TreeNode('C')
root.right = TreeNode('G')
root.right.right = TreeNode('F')
print("层序遍历序列为:")
level_order(root)
```
输出结果为:
```
层序遍历序列为:
A
D
G
E
B
F
C
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)