假设二叉树采用二叉链存储,每个结点值为单个字符,并且所有结点值不相同。编写一个实验程序,由二叉树的中序序列和后序序列构造二叉树,实现查找、求高度、先序遍历、中序遍历、后序遍历算法和层次遍历算法,用相关数据进行测试。
时间: 2024-02-17 22:05:31 浏览: 19
好的,我理解了你的问题。这是一个关于二叉树的问题,需要编写一个实验程序进行实现。下面是我为你提供的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinaryTree:
def __init__(self, inorder, postorder):
self.root = self.buildTree(inorder, postorder)
def buildTree(self, inorder, postorder):
if not inorder or not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = self.buildTree(inorder[:idx], postorder[:idx])
root.right = self.buildTree(inorder[idx+1:], postorder[idx:-1])
return root
def find(self, val):
node = self.root
while node:
if node.val == val:
return True
elif node.val < val:
node = node.right
else:
node = node.left
return False
def height(self):
return self.getHeight(self.root)
def getHeight(self, node):
if not node:
return 0
left_height = self.getHeight(node.left)
right_height = self.getHeight(node.right)
return max(left_height, right_height) + 1
def preorderTraversal(self):
res = []
self.preorder(self.root, res)
return res
def preorder(self, node, res):
if not node:
return
res.append(node.val)
self.preorder(node.left, res)
self.preorder(node.right, res)
def inorderTraversal(self):
res = []
self.inorder(self.root, res)
return res
def inorder(self, node, res):
if not node:
return
self.inorder(node.left, res)
res.append(node.val)
self.inorder(node.right, res)
def postorderTraversal(self):
res = []
self.postorder(self.root, res)
return res
def postorder(self, node, res):
if not node:
return
self.postorder(node.left, res)
self.postorder(node.right, res)
res.append(node.val)
def levelOrderTraversal(self):
res = []
if not self.root:
return res
queue = [self.root]
while queue:
level = []
for _ in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
这个程序包含了二叉树的构建、查找、求高度、先序、中序、后序和层次遍历算法,你可以用相关数据进行测试。