1. 输入完全二叉树的先序序列,用 # 代表虚结点(空指针), 如 ABD###CE##F###建立二叉树,实现先序、中序和后序以及按层次遍历 序列 求所有叶子及结点总数
时间: 2024-02-12 16:07:17 浏览: 68
建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数
好的,我可以为您提供相关的代码实现。
首先,我们需要定义一个二叉树的节点结构体,包括节点值和左右子节点指针。代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
```
接下来,我们可以根据输入的先序序列构建二叉树。具体代码如下:
```python
def build_tree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == '#':
return None
root = TreeNode(val)
root.left = build_tree(preorder)
root.right = build_tree(preorder)
return root
```
然后,我们可以实现二叉树的先序、中序和后序遍历算法。具体代码如下:
```python
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
```
最后,我们可以实现二叉树的按层次遍历算法以及计算叶子节点和总节点数的算法。具体代码如下:
```python
from collections import deque
def level_order_traversal(root):
if not root:
return []
queue = deque([root])
res = []
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
def count_nodes_and_leaves(root):
if not root:
return 0, 0
if not root.left and not root.right:
return 1, 1
left_nodes, left_leaves = count_nodes_and_leaves(root.left)
right_nodes, right_leaves = count_nodes_and_leaves(root.right)
nodes = left_nodes + right_nodes + 1
leaves = left_leaves + right_leaves
return nodes, leaves
```
最终,我们可以按照以下方式调用上述函数来实现题目要求:
```python
preorder = list('ABD###CE##F###')
root = build_tree(preorder)
print('先序遍历序列:', preorder_traversal(root))
print('中序遍历序列:', inorder_traversal(root))
print('后序遍历序列:', postorder_traversal(root))
print('按层次遍历序列:', level_order_traversal(root))
nodes, leaves = count_nodes_and_leaves(root)
print('节点总数:', nodes)
print('叶子节点数:', leaves)
```
希望这个代码实现能够帮助到您!
阅读全文