(1)构造利用二叉链表存储表示的二叉树; (2)利用先序遍历创建一个二叉树; (3)递归计算二叉树的深度和叶子结点的个数。
时间: 2024-01-23 20:45:21 浏览: 74
下面是Python实现:
```python
# 二叉树的节点类
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 二叉树类
class BinaryTree:
def __init__(self, root=None):
self.root = root
# 构造利用二叉链表存储表示的二叉树
def construct(self, val, left=None, right=None):
node = Node(val, left, right)
if not self.root:
self.root = node
return node
# 利用先序遍历创建一个二叉树
def build(self, preorder):
if not preorder:
return None
val = preorder.pop(0)
if val is None:
return None
node = Node(val)
node.left = self.build(preorder)
node.right = self.build(preorder)
return node
# 递归计算二叉树的深度和叶子结点的个数
def calc_depth_and_leaf_count(self, node):
if not node:
return 0, 0
left_depth, left_leaf_count = self.calc_depth_and_leaf_count(node.left)
right_depth, right_leaf_count = self.calc_depth_and_leaf_count(node.right)
depth = max(left_depth, right_depth) + 1
leaf_count = left_leaf_count + right_leaf_count
if not node.left and not node.right:
leaf_count += 1
return depth, leaf_count
```
使用示例:
```python
# 构造二叉树
bt = BinaryTree()
a = bt.construct('A')
b = bt.construct('B')
c = bt.construct('C')
d = bt.construct('D')
e = bt.construct('E')
f = bt.construct('F')
g = bt.construct('G')
a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g
# 先序遍历创建二叉树
bt2 = BinaryTree()
preorder = ['A', 'B', 'D', None, None, 'E', None, None, 'C', 'F', None, None, 'G', None, None]
bt2.root = bt2.build(preorder)
# 计算深度和叶子节点个数
depth, leaf_count = bt.calc_depth_and_leaf_count(bt.root)
print('深度:', depth)
print('叶子节点个数:', leaf_count)
depth2, leaf_count2 = bt2.calc_depth_and_leaf_count(bt2.root)
print('深度:', depth2)
print('叶子节点个数:', leaf_count2)
```
输出结果:
```
深度: 3
叶子节点个数: 4
深度: 3
叶子节点个数: 4
```
阅读全文