已知中序遍历和后序遍历如何画二叉树
时间: 2024-04-29 13:04:29 浏览: 314
画二叉树的步骤如下:
1. 从后序遍历中找到根节点,该节点是最后一个元素。
2. 在中序遍历中找到根节点的位置,该位置左侧的元素为左子树的节点,右侧的元素为右子树的节点。
3. 根据中序遍历的结果,确定左子树和右子树的节点数量。
4. 在后序遍历中,左子树的节点在根节点之前,右子树的节点在根节点之后。
5. 根据左子树和右子树的节点数量,在后序遍历中确定左子树和右子树的边界。
6. 递归地重复以上步骤,画出左子树和右子树。
举例说明,假设中序遍历为[4, 2, 5, 1, 6, 3, 7],后序遍历为[4, 5, 2, 6, 7, 3, 1],则根节点为1。在中序遍历中,1的位置为第4个元素,因此左子树有3个节点,右子树有3个节点。在后序遍历中,左子树的节点为[4, 5, 2],右子树的节点为[6, 7, 3]。递归地画出左子树和右子树,最终得到以下二叉树:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
相关问题
已知一个二叉树的前序遍历和中序遍历 求后序遍历
根据二叉树的前序遍历和中序遍历可以唯一确定一棵二叉树,因此可以通过这两个遍历序列构建出这棵二叉树,然后再进行后序遍历。
具体步骤如下:
1. 根据前序遍历序列确定根节点,假设为root。
2. 在中序遍历序列中找到根节点root的位置,将中序遍历序列分为左子树和右子树两部分,分别对左右子树递归进行步骤1和步骤2,直到序列为空或者只有一个节点。
3. 对于每个节点,先遍历它的左子树,再遍历它的右子树,最后遍历它本身,即可得到后序遍历序列。
下面是Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
root.left = buildTree(preorder[1:root_index+1], inorder[:root_index])
root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:])
return root
def postorderTraversal(root):
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
postorder = postorderTraversal(root)
print(postorder) # 输出:[4, 5, 2, 6, 7, 3, 1]
```
已知中序遍历和后序遍历如何构造二叉树,需要代码模板
使用中序遍历和后序遍历构造二叉树的代码模板如下:// 中序遍历序列和后序遍历序列构造二叉树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
if (inorder.empty() || postorder.empty())
return nullptr; // 后序遍历的最后一个结点就是根结点
TreeNode* root = new TreeNode(postorder.back()); // 找到根结点在中序遍历中的位置
auto rootPos = find(inorder.begin(), inorder.end(), postorder.back()); // 构建左子树
vector<int> left_inorder(inorder.begin(), rootPos);
vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
root->left = buildTree(left_inorder, left_postorder); // 构建右子树
vector<int> right_inorder(rootPos + 1, inorder.end());
vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end() - 1);
root->right = buildTree(right_inorder, right_postorder); return root;
}
阅读全文