假设二叉树采用二叉链存储,每个结点值为单个字符,并且所有结点值不相同。编写一个实验程序,由二叉树的中序序列和后序序列构造二叉树,实现查找、求高度、先序遍历、中序遍历、后序遍历算法和层次遍历算法,用相关数据进行测试。
时间: 2024-02-03 20:12:23 浏览: 24
下面是基于Python 3实现的代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self, inorder, postorder):
self.root = self.construct_tree(inorder, postorder)
def construct_tree(self, inorder, postorder):
if not inorder:
return None
root_value = postorder[-1]
root = Node(root_value)
index = inorder.index(root_value)
root.left = self.construct_tree(inorder[:index], postorder[:index])
root.right = self.construct_tree(inorder[index+1:], postorder[index:-1])
return root
def search(self, value):
def search_helper(node, value):
if not node:
return False
if node.value == value:
return True
if value < node.value:
return search_helper(node.left, value)
else:
return search_helper(node.right, value)
return search_helper(self.root, value)
def height(self):
def height_helper(node):
if not node:
return 0
left_height = height_helper(node.left)
right_height = height_helper(node.right)
return max(left_height, right_height) + 1
return height_helper(self.root)
def preorder(self):
def preorder_helper(node, result):
if node:
result.append(node.value)
preorder_helper(node.left, result)
preorder_helper(node.right, result)
result = []
preorder_helper(self.root, result)
return result
def inorder(self):
def inorder_helper(node, result):
if node:
inorder_helper(node.left, result)
result.append(node.value)
inorder_helper(node.right, result)
result = []
inorder_helper(self.root, result)
return result
def postorder(self):
def postorder_helper(node, result):
if node:
postorder_helper(node.left, result)
postorder_helper(node.right, result)
result.append(node.value)
result = []
postorder_helper(self.root, result)
return result
def levelorder(self):
result = []
queue = [self.root]
while queue:
node = queue.pop(0)
if node:
result.append(node.value)
queue.append(node.left)
queue.append(node.right)
return result
```
我们可以根据以下步骤测试代码:
1. 构造一个二叉树,使用中序序列为`[D, B, E, A, F, C]`,后序序列为`[D, E, B, F, C, A]`。
2. 测试查找方法,分别查找存在和不存在的值。
3. 测试求高度方法。
4. 测试先序、中序、后序和层次遍历方法。
下面是测试代码:
```python
# 构造二叉树
binary_tree = BinaryTree(['D', 'B', 'E', 'A', 'F', 'C'], ['D', 'E', 'B', 'F', 'C', 'A'])
# 测试查找方法
print(binary_tree.search('A')) # True
print(binary_tree.search('Z')) # False
# 测试求高度方法
print(binary_tree.height()) # 3
# 测试遍历方法
print(binary_tree.preorder()) # ['A', 'B', 'D', 'E', 'C', 'F']
print(binary_tree.inorder()) # ['D', 'B', 'E', 'A', 'F', 'C']
print(binary_tree.postorder()) # ['D', 'E', 'B', 'F', 'C', 'A']
print(binary_tree.levelorder()) # ['A', 'B', 'C', 'D', 'E', 'F']
```
输出结果:
```
True
False
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']
```
阅读全文