用递归的方法实现以下算法。 (1)以二叉链表表示二叉树,建立一棵二叉树; (2)输出二叉树的后序遍历结果;
时间: 2023-12-01 22:00:29 浏览: 159
好的,针对您的问题,我可以给出以下代码实现:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 递归建立二叉树
def create_binary_tree():
val = input("请输入节点的值:")
if val == '#':
return None
node = TreeNode(int(val))
node.left = create_binary_tree()
node.right = create_binary_tree()
return node
# 递归后序遍历二叉树
def postorder_traversal(node):
if node is None:
return
postorder_traversal(node.left)
postorder_traversal(node.right)
print(node.val, end=' ')
# 测试代码
if __name__ == '__main__':
root = create_binary_tree()
print("后序遍历结果为:")
postorder_traversal(root)
```
在上面的代码中,我们首先定义了一个二叉树节点类,包含节点值、左右子树指针。然后我们使用递归的方式建立二叉树,输入节点的值,如果是 # 表示该节点为空,否则创建一个节点,递归创建左子树和右子树,最后返回该节点。接着我们使用递归的方式进行后序遍历,先递归遍历左子树和右子树,最后输出当前节点的值。最后在测试代码中,我们创建二叉树并输出后序遍历结果。
阅读全文