假设二叉树采用二叉链存储,每个结点值为单个字符,并且所有结点值不相同。编写一个实验程序,由二叉树的中序序列和后序序列构造二叉树,实现查找、求高度、先序遍历、中序遍历、后序遍历算法和层次遍历算法,用相关数据进行测试。
时间: 2024-02-15 18:05:58 浏览: 17
好的,我知道了你的问题。以下是我提供的代码实现:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root = Node(postorder[-1])
inorderIndex = inorder.index(root.data)
root.left = buildTree(inorder[:inorderIndex], postorder[:inorderIndex])
root.right = buildTree(inorder[inorderIndex+1:], postorder[inorderIndex:-1])
return root
def search(root, key):
if root is None or root.data == key:
return root
if root.data < key:
return search(root.right, key)
return search(root.left, key)
def height(root):
if root is None:
return 0
leftHeight = height(root.left)
rightHeight = height(root.right)
return max(leftHeight, rightHeight) + 1
def preorder(root):
if root is not None:
print(root.data, end=' ')
preorder(root.left)
preorder(root.right)
def inorder(root):
if root is not None:
inorder(root.left)
print(root.data, end=' ')
inorder(root.right)
def postorder(root):
if root is not None:
postorder(root.left)
postorder(root.right)
print(root.data, end=' ')
def levelOrder(root):
if root is None:
return
queue = []
queue.append(root)
while queue:
current = queue.pop(0)
print(current.data, end=' ')
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
# 测试
inorder = ['D', 'B', 'E', 'A', 'F', 'C']
postorder = ['D', 'E', 'B', 'F', 'C', 'A']
root = buildTree(inorder, postorder)
print('Search:', search(root, 'B').data)
print('Height:', height(root))
print('Preorder:', end=' ')
preorder(root)
print('\nInorder:', end=' ')
inorder(root)
print('\nPostorder:', end=' ')
postorder(root)
print('\nLevel order:', end=' ')
levelOrder(root))
```
这段代码实现了二叉树的构建、查找、求高度、先序遍历、中序遍历、后序遍历和层次遍历算法。你可以根据需要修改测试数据,来验证代码的正确性。