设计二叉树,输入完全二叉树的先序序列;2、建立二叉树 3、求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。
时间: 2024-05-15 16:12:28 浏览: 14
以下是基于Python语言的实现:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 先序遍历建立二叉树
def build_tree(preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
if len(preorder) == 1:
return root
mid = (len(preorder) + 1) // 2
root.left = build_tree(preorder[1:mid])
root.right = build_tree(preorder[mid:])
return root
# 先序遍历
def preorder_traversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
# 中序遍历
def inorder_traversal(root):
if not root:
return []
res = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
# 后序遍历
def postorder_traversal(root):
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
# 层次遍历
def level_order_traversal(root):
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
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_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)
# 求节点总数
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
# 测试
preorder = [1, 2, 4, 5, 3, 6, 7]
root = build_tree(preorder)
print(preorder_traversal(root)) # [1, 2, 4, 5, 3, 6, 7]
print(inorder_traversal(root)) # [4, 2, 5, 1, 6, 3, 7]
print(postorder_traversal(root)) # [4, 5, 2, 6, 7, 3, 1]
print(level_order_traversal(root)) # [[1], [2, 3], [4, 5, 6, 7]]
print(count_leaves(root)) # 4
print(count_nodes(root)) # 7
```
以上代码中,我们定义了一个二叉树节点的类 `TreeNode`,包含节点的值、左右子节点,然后使用先序遍历的方式建立了完全二叉树。接着,我们分别实现了先序、中序、后序和层次遍历,并使用递归的方式求出叶子节点数量和节点总数。最后,我们对代码进行测试,输出结果符合预期。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)