假设二叉树采用二叉链存储,每个结点值为单个字符,并且所有结点值不相同。编写一个实验程序,由二叉树的中序序列和后序序列构造二叉树,实现查找、求高度、先序遍历、中序遍历、后序遍历算法和层次遍历算法,用相关数据进行测试。python
时间: 2023-07-16 13:14:55 浏览: 48
以下是实现该二叉树的代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def build_tree(inorder, postorder):
if not inorder or not postorder:
return None
root_val = postorder[-1]
root = Node(root_val)
inorder_index = inorder.index(root_val)
root.left = build_tree(inorder[:inorder_index], postorder[:inorder_index])
root.right = build_tree(inorder[inorder_index+1:], postorder[inorder_index:-1])
return root
def find_node(root, value):
if not root:
return None
if root.value == value:
return root
left = find_node(root.left, value)
if left:
return left
right = find_node(root.right, value)
if right:
return right
return None
def height(root):
if not root:
return 0
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
def preorder_traversal(root):
if not root:
return []
result = [root.value]
result += preorder_traversal(root.left)
result += preorder_traversal(root.right)
return result
def inorder_traversal(root):
if not root:
return []
result = inorder_traversal(root.left)
result += [root.value]
result += inorder_traversal(root.right)
return result
def postorder_traversal(root):
if not root:
return []
result = postorder_traversal(root.left)
result += postorder_traversal(root.right)
result += [root.value]
return result
def level_order_traversal(root):
if not root:
return []
queue = [root]
result = []
while queue:
current = queue.pop(0)
result.append(current.value)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return result
```
可以通过以下代码进行测试:
```python
inorder = ['D', 'B', 'E', 'A', 'F', 'C']
postorder = ['D', 'E', 'B', 'F', 'C', 'A']
root = build_tree(inorder, postorder)
print(find_node(root, 'A').value)
print(height(root))
print(preorder_traversal(root))
print(inorder_traversal(root))
print(postorder_traversal(root))
print(level_order_traversal(root))
```
输出结果为:
```
A
3
['A', 'B', 'D', 'E', 'C', 'F']
['D', 'B', 'E', 'A', 'F', 'C']
['D', 'E', 'B', 'F', 'C', 'A']
['A', 'B', 'C', 'D', 'E', 'F']
```