以二叉链表作为二叉树的存储结构,编写以下算法: 1.统计二叉树的叶结点个数。 2.判别两棵树是否相等。 3.交换二叉树每个结点的左孩子和右孩子。 4.设计二叉树的双序遍历算法。的运算截图
时间: 2024-03-14 17:47:11 浏览: 109
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
抱歉,作为语言模型的我无法提供运算截图,但是我可以为您提供相应的算法实现代码,您可以在本地运行并查看结果。
1. 统计二叉树的叶结点个数
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
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)
```
2. 判别两棵树是否相等
```python
def is_same_tree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
```
3. 交换二叉树每个结点的左孩子和右孩子
```python
def invert_tree(root):
if not root:
return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return root
```
4. 设计二叉树的双序遍历算法
```python
def morris_traversal(root):
curr = root
while curr:
if not curr.left:
print(curr.val)
curr = curr.right
else:
pre = curr.left
while pre.right and pre.right != curr:
pre = pre.right
if not pre.right:
pre.right = curr
curr = curr.left
else:
pre.right = None
print(curr.val)
curr = curr.right
```
阅读全文