假设二叉树采用顺序存储结构存储,每个结点值为单个字符并且所有结点值不相等，如何让二叉树的中序序列和后序序列构造二叉树，然后实现查找、求高度、先序通历、中序遍历、后序遍历和层次遍历算法
顺序存储，就是每个节点i的子节点为i2+1和i2+2，而对于i节点，其父节点为i-1//2
别的和链式存储的没啥区别了。
构造：
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(inorder, postorder):
if not inorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
root_idx = inorder.index(root_val)
left_inorder = inorder[:root_idx]
right_inorder = inorder[root_idx+1:]
left_postorder = postorder[:len(left_inorder)]
right_postorder = postorder[len(left_inorder):-1]
root.left = build_tree(left_inorder, left_postorder)
root.right = build_tree(right_inorder, right_postorder)
return root
查找：
def search(root, val):
if not root or root.val == val:
return root
if val < root.val:
return search(root.left, val)
else:
return search(root.right, val)
求高度：
def height(root):
if not root:
return 0
return max(height(root.left), height(root.right)) + 1
先序遍历：
def preorder(root):
if not root:
return
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
中序遍历：
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
后序遍历：
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
print(root.val, end=' ')
层次遍历：
from collections import deque
def level_order(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
如果答案对您有帮助，望采纳。
class TreeNode:
def __init__(self, value):
self.value = value
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:
return None
# 后序遍历的最后一个节点是当前子树的根节点
root_val = postorder.pop()
root = TreeNode(root_val)
# 在中序遍历中找到根节点的位置，划分左右子树
inorder_index = inorder.index(root_val)
left_inorder = inorder[:inorder_index]
right_inorder = inorder[inorder_index+1:]
# 根据中序序列的划分，划分后序序列
left_postorder = postorder[:len(left_inorder)]
right_postorder = postorder[len(left_inorder):]
# 递归构建左右子树
root.left = self.buildTree(left_inorder, left_postorder)
root.right = self.buildTree(right_inorder, right_postorder)
return root
def find(self, value):
# 查找节点是否存在
node = self.root
while node:
if node.value == value:
return True
elif node.value > value:
node = node.left
else:
node = node.right
return False
def height(self, root):
# 求树的高度
if not root:
return 0
left_height = self.height(root.left)
right_height = self.height(root.right)
return max(left_height, right_height) + 1
def preorderTraversal(self, root):
# 先序遍历
if not root:
return []
return [root.value] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
def inorderTraversal(self, root):
# 中序遍历
if not root:
return []
return self.inorderTraversal(root.left) + [root.value] + self.inorderTraversal(root.right)
def postorderTraversal(self, root):
# 后序遍历
if not root:
return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.value]
def levelOrderTraversal(self, root):
# 层次遍历
if not root:
return []
queue = [root]
res = []
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.pop(0)
level_nodes.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_nodes)
return res