在数据结构中,以二叉链表作为二叉树的存储结构,设计以下算法。 统计二叉树的叶结点个数 判别两棵树是否相等 交换二叉树每个结点的左孩子和右孩子。
时间: 2024-12-14 16:04:55 浏览: 5
在数据结构中,使用二叉链表作为二叉树的存储结构,可以实现以下算法:
1. **统计二叉树的叶节点个数**:
- 定义一个辅助函数,接受当前节点和已遍历过的叶节点计数器`leafCount`作为参数。
- 如果当前节点为空,返回`leafCount`;如果当前节点是叶子节点(即左右子节点均为空),将`leafCount`加一并递归地检查其父节点。
- 否则,分别对左右子节点进行上述操作。
```python
def countLeaves(root):
if root is None:
return 0
elif root.left is None and root.right is None:
return 1 + countLeaves(root.parent) # 如果是叶子节点,加上自身
else:
return countLeaves(root.left) + countLeaves(root.right)
```
2. **判别两棵树是否相等**:
- 使用深度优先搜索(DFS)或广度优先搜索(BFS)的方式比较两个树的节点值、结构和大小。
- 遍历两个树,若节点值不同或任一方先遍历完,则返回False;否则继续向下对比。
```python
def areTreesEqual(tree1, tree2):
stack1 = [(tree1.root, tree2.root)]
while stack1:
node1, node2 = stack1.pop()
if node1 is None and node2 is None:
continue
elif (node1 is not None and node2 is None) or (node1 is None and node2 is not None):
return False
elif node1.val != node2.val:
return False
stack1.extend([(node1.left, node2.left), (node1.right, node2.right)])
return True
```
3. **交换二叉树每个结点的左孩子和右孩子**:
- 这是一个递归过程,首先处理根节点,然后递归地交换左右孩子的值。
```python
def swapChildren(root):
if root is None:
return
root.left, root.right = root.right, root.left
swapChildren(root.left)
swapChildren(root.right)
```
阅读全文