首页C语言已知二叉树的先序遍历和中序遍历求后序遍历

C语言已知二叉树的先序遍历和中序遍历求后序遍历

时间: 2025-02-09 15:15:16 浏览: 64

在C语言中，给定一棵已知的二叉树的先序遍历（根节点 -> 左子树 -> 右子树）和中序遍历（左子树 -> 根节点 -> 右子树），我们可以通过递归的方式求得后序遍历（左子树 -> 右子树 -> 根节点）。这是因为前序、中序和后序遍历之间存在一定的关联： 1. **后序遍历**的根节点在最后，所以我们可以通过以下步骤找到它： - 当遍历到当前节点时，如果它是先序遍历的第一个元素，那么它就是根节点。 - 接着，我们在中序遍历中查找该节点的位置。由于中序遍历根节点位于左右子树之间，所以我们可以找到从当前开始的剩余部分，这部分就是中序遍历剩下的左子树和右子树。 - 对这个剩余部分分别进行后序遍历即可得到完整的后序遍历序列。下面是递归实现的伪代码示例： ```c struct TreeNode *findRoot(struct TreeNode *root, int preorder[], int size) { // 先序遍历第一个元素即为根节点 if (preorder[0] == root->val) return root; // 中序遍历找到根节点的位置 for (int i = 1; i < size; i++) { if (preorder[i] == root->val) { return findRoot(root->left, inorder, size); } } } void postorderTraversal(struct TreeNode *root, int inorder[], int size) { if (root == NULL) return; postorderTraversal(root->left, inorder, size); postorderTraversal(root->right, inorder, size); // 将找到的根节点添加到后序序列的末尾 insertAtEnd(postorder, root->val); // 假设insertAtEnd()是一个函数用于将值追加到数组末尾 } ``` 这里假设`inorder[]`数组保存了中序遍历的结果，并且`postorder[]`数组用于存储最终的后序遍历结果。你需要根据实际情况调整这些操作。

阅读全文