用递归非递归以二叉链表示二叉树,程序
时间: 2024-03-01 14:52:05 浏览: 21
以下是用递归方式和非递归方式以二叉链表示二叉树的程序:
```python
# 定义二叉树节点类
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# 递归方式构建二叉树
def recursive_build_tree():
data = input("请输入节点值(输入None表示为空节点):")
if data == "None":
return None
node = Node(data)
node.left = recursive_build_tree()
node.right = recursive_build_tree()
return node
# 非递归方式构建二叉树
def iterative_build_tree():
root = None
node_stack = []
data = input("请输入根节点值:")
if data == "None":
return None
root = Node(data)
node_stack.append(root)
while len(node_stack) > 0:
curr_node = node_stack.pop()
left_data = input("请输入节点" + curr_node.data + "的左子节点值(输入None表示为空节点):")
if left_data != "None":
left_node = Node(left_data)
curr_node.left = left_node
node_stack.append(left_node)
right_data = input("请输入节点" + curr_node.data + "的右子节点值(输入None表示为空节点):")
if right_data != "None":
right_node = Node(right_data)
curr_node.right = right_node
node_stack.append(right_node)
return root
```
使用方式:
```python
# 递归方式构建二叉树
root = recursive_build_tree()
# 非递归方式构建二叉树
root = iterative_build_tree()
```