由中序与后序遍历得到二叉树
程序员文章站
2022-05-20 13:51:44
...
例子:
3 2 1 4 5 7 6 (中序遍历)
3 1 2 5 6 7 4 (后序遍历)
思路:
整体来说就是一个递归分治的思想
重点在后序遍历上,由后序遍历的定义知,后序遍历的最后一项肯定为根结点,然后在中序遍历中找到这一项(假设无重复项)
如:由 3 1 2 5 6 7 4 (后序遍历)知该二叉树的根结点为4,因此将3 2 1 4 5 7 6 (中序遍历) 分割为3 2 1||4||5 7 6,
又由中序遍历的定义知,4左边的为左子树,右边的为右子树。在将每颗子树看为一颗树
------左:3 2 1(中序遍历) 3 1 2(后序遍历)--------右:5 7 6 (中序遍历) 5 6 7(后序遍历)-------
3 2 1 4 5 7 6 (中序遍历)
3 1 2 5 6 7 4 (后序遍历)
思路:
整体来说就是一个递归分治的思想
重点在后序遍历上,由后序遍历的定义知,后序遍历的最后一项肯定为根结点,然后在中序遍历中找到这一项(假设无重复项)
如:由 3 1 2 5 6 7 4 (后序遍历)知该二叉树的根结点为4,因此将3 2 1 4 5 7 6 (中序遍历) 分割为3 2 1||4||5 7 6,
又由中序遍历的定义知,4左边的为左子树,右边的为右子树。在将每颗子树看为一颗树
------左:3 2 1(中序遍历) 3 1 2(后序遍历)--------右:5 7 6 (中序遍历) 5 6 7(后序遍历)-------
以此类推。。。。直到不可分割出现递归出口。
vector<int>inorder;
vector<int>postorder;
struct my_Node
{
int data;
struct my_Node *left_p;
struct my_Node *right_p;
};
struct my_Node* create_tree(int start_inorder, int end_inorder, int start_postorder, int end_postorder)
//传入的四个参数为,中序遍历的开始与结束位,后序遍历的开始与结束位
{
my_Node* root = (my_Node*)malloc(sizeof(my_Node));
root->data = postorder[end_postorder];
if (end_inorder - start_inorder < 2)//递归出口,子树为空
{
root->left_p = NULL;
root->right_p = NULL;
return root;
}
//找出中序遍历中的根结点
int p_temp = start_inorder;
while ((p_temp<=end_inorder)&&(inorder[p_temp]!=postorder[end_postorder]))
{
p_temp++;
}
//左子树
int num_left_tree = p_temp - start_inorder;//左子树大小
if (num_left_tree!=0)
{
root->left_p = create_tree(start_inorder, p_temp-1, start_postorder, start_postorder + (num_left_tree)-1);
}
else
{
root->left_p = NULL;
}
//右子树
int num_right_tree = end_inorder - p_temp;
if (num_right_tree!=0)
{
root->right_p = create_tree(p_temp + 1, end_inorder, end_postorder - num_right_tree, end_postorder - 1);
}
else
{
root->right_p = NULL;
}
return root;
}
上一篇: 判断一个数组是不是排序二叉树后序遍历
下一篇: 二叉树的创建及前中后序遍历和层次遍历
推荐阅读
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
C++实现LeetCode(889.由先序和后序遍历建立二叉树)
-
C++实现LeetCode(106.由中序和后序遍历建立二叉树)
-
二叉树的先序遍历、中序遍历、后序遍历