C++实现利用前序序列和中序序列构建二叉树

红太狼 2023-07-20 13:35 86阅读 0赞

### 前言：已知一个二叉树的中序序列和前序序列，或者中序序列和后序序列就可以唯一确定一个二叉树（必须知道中序序列），只知道前序和后序不能创建唯一的二叉树。 ###

# 1.引例 #

已知下列某二叉树(8个结点)的两个序列，如何确定一棵唯一的二叉树呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]  
①**前序序列**的第一个结点，就是**根结点**  
②在**中序序列**中，找到根结点，记录**根结点前的结点**，即为**左子树结点**，图中为3(4,7,2)，**根结点后的结点，即为右子树结点**，图中为(5,3,8,6)  
③在前序序列中，根结点往后对应数量的结点，就是左子树的前序序列(2,4,7)  
④现在左子树的前序(2,4,7)和中序序列(4,7,2)都有了，再重复步骤①-③,就完成了左子树的创建  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]  
⑤找到右子树的前序序列(3,5,6,8),中序序列(5,3,8,6),再重复步骤①-③,就完成了右子树的创建  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 2]

# 2.具体代码实现 #

其实引例中描述的"重复步骤①-③"，就是递归的思想，下面是具体代码  
解释：  
Formdata和Middledata是前序和中序数组的指针  
num是二叉树的结点总数

Bintree_Node* Build(int* Formerdata, int* Middledata, int num)
    {
        
    	if (Formerdata == NULL || Middledata == NULL || num <= 0)
    		return NULL;
    	//先序遍历，第一个值就是根结点
    	Bintree_Node* root = new Bintree_Node;
    	root->data = Formerdata[0];
    	root->left = root->right = NULL;
    	//如果只有一个结点
    	if (num == 1 && *Former == *Middledata)
    		return root;
    
    	//在中序序列中找到根结点
    	int left_num = 0;//左子树的结点总数
    	int* middle_root = Middledata;//中序序列中的根结点
    	//第二个条件：循环要在Middledata中进行
    	while (*middle_root != Formerdata[0]&&middle_root <= (Middledata + num - 1))
    	{
        
    		middle_root++;
    		left_num++;
    	}
    	if (*middle_root != Formerdata[0])//未找到根结点，输入错误
    	{
        
    		cout << "未找到根结点，输入错误" << endl;
    		return NULL;
    	}
        //创建左子树
    	if (left_num > 0)
    		root->left = Build(Formerdata + 1, Middledata, left_num);//Formerdata+1即为左子树的前序序列的开始
    	//创建右子树
    	if (num - left_num - 1 > 0)
    		root->right = Build(Formerdata + left_num + 1, Middledata+left_num+1, num - left_num - 1);
    	return root;
    }

测试

void main()
    {
        
    	int Former[] = {
         1,2,4,7,3,5,6,8 };
    	int Middle[] = {
         4,7,2,1,5,3,8,6 };
    	Bintree_Node* root=Build(Former, Middle, 8);
    	Show(root);//前序遍历
    }

![在这里插入图片描述][20200401213818846.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]: /images/20230528/2b969cd7a7794f3ca8a27c3ae09fcaa4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]: /images/20230528/2f64017cdd5241f9979be8cdc8e14a22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 2]: /images/20230528/2d515f59438a45c7b221914d24646bca.png
[20200401213818846.png]: /images/20230528/f2866a18272a4dc490b8b801dc38fd4d.png