编写一个程序,实现二叉树A(B(D,E(H(J,K(L,M(N)))),C(F,G(,I)))的先序遍历、中序遍历和后序遍历的递归和非递归算法,以及层次遍历的算法
时间: 2024-02-04 17:04:33 浏览: 24
二叉树的节点定义如下:
```python
class TreeNode:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
```
先序遍历的递归算法:
```python
def preorder_recursive(root):
if not root:
return
print(root.val, end=' ')
preorder_recursive(root.left)
preorder_recursive(root.right)
```
先序遍历的非递归算法:
```python
def preorder_iterative(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val, end=' ')
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
```
中序遍历的递归算法:
```python
def inorder_recursive(root):
if not root:
return
inorder_recursive(root.left)
print(root.val, end=' ')
inorder_recursive(root.right)
```
中序遍历的非递归算法:
```python
def inorder_iterative(root):
if not root:
return
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.val, end=' ')
node = node.right
```
后序遍历的递归算法:
```python
def postorder_recursive(root):
if not root:
return
postorder_recursive(root.left)
postorder_recursive(root.right)
print(root.val, end=' ')
```
后序遍历的非递归算法:
```python
def postorder_iterative(root):
if not root:
return
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
```
层次遍历的算法:
```python
def levelorder(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
```
完整代码如下:
```python
class TreeNode:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def preorder_recursive(root):
if not root:
return
print(root.val, end=' ')
preorder_recursive(root.left)
preorder_recursive(root.right)
def preorder_iterative(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val, end=' ')
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
def inorder_recursive(root):
if not root:
return
inorder_recursive(root.left)
print(root.val, end=' ')
inorder_recursive(root.right)
def inorder_iterative(root):
if not root:
return
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.val, end=' ')
node = node.right
def postorder_recursive(root):
if not root:
return
postorder_recursive(root.left)
postorder_recursive(root.right)
print(root.val, end=' ')
def postorder_iterative(root):
if not root:
return
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
def levelorder(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.val, end=' ')
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if __name__ == '__main__':
# 构造二叉树
n = TreeNode('N')
m = TreeNode('M', n)
l = TreeNode('L')
k = TreeNode('K', l, m)
j = TreeNode('J')
h = TreeNode('H', j, k)
e = TreeNode('E', h)
i = TreeNode('I')
g = TreeNode('G', None, i)
f = TreeNode('F')
d = TreeNode('D')
b = TreeNode('B', d, e)
c = TreeNode('C', f, g)
a = TreeNode('A', b, c)
# 先序遍历
print('先序遍历:')
preorder_recursive(a)
print()
preorder_iterative(a)
print()
# 中序遍历
print('中序遍历:')
inorder_recursive(a)
print()
inorder_iterative(a)
print()
# 后序遍历
print('后序遍历:')
postorder_recursive(a)
print()
print(postorder_iterative(a))
print()
# 层次遍历
print('层次遍历:')
levelorder(a)
print()
```