根据前序和中序遍历建立二叉树，并输出后序遍历

太过爱你忘了你带给我的痛 2023-02-28 15:26 27阅读 0赞

这类问题利用递归比较方便  
首先我们需要了解前序和中序遍历的结构，例如  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70][]  
图中二叉树的前序遍历为：ABDGCEF,  
中序遍历为：DGBAECF  
根据前序遍历，我们可以确定该二叉树的根节点为A，再通过中序遍历中A的位置，可以确定DGB为该二叉树的左子树，ECF为右子树  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 1][]  
根据这个逻辑，每次在前序遍历中读取一个节点，再在中序遍历中找到他所在的位置，便可以确定该子树的左子树和右子树及其节点数。  
下面是具体的代码：

#include<iostream>
    #include<string.h>
    using namespace std;
    
    const int MAX = 100;
    struct Binode
    {
        
    	char data;
    	Binode* rchild;
    	Binode* lchild;
    };
    /* Preb,Pree分别表示前序遍历的起点和终点，
    Inb,Ine表示后续遍历的起点和终点*/
    Binode* createBTree(int Preb,int Pree,int Inb,int Ine,char Preorder[], char Inorder[])
    {
        
    	if (Preb > Pree || Preb < 0)
    		return NULL;
    	Binode* Node = new Binode;
    	Node->data = Preorder[Preb];//每找到一个根节点便将其数据存入需建立的树中
    	Node->lchild = NULL;
    	Node->rchild = NULL;
    	int k = 0;//k记录每个根节点的下标（这里的根节点可以指整棵树的根节点，也可指左右子树的根节点）
    	for (int i = Inb; i < Ine + 1; i++)//通过该循环查找根节点在中序遍历中的位置，从而划分左右子树并确定左右子树元素个数
    	{
        
    		if (Preorder[Preb] == Inorder[i])
    		{
        
    			k = i;
    			break;
    		}
    	}
    	Node->lchild = createBTree(Preb + 1, Preb + k - Inb, Inb, k - 1, Preorder, Inorder);//这里的k-Inb可以看做以Inorder[k]为根节点的左子树的节点数，所以Preb+1~Preb+k-Inb即为该左子树在前序中对应的区段，其他的可以依此推断。
    	Node->rchild = createBTree(Preb + k - Inb + 1, Pree, k + 1, Ine, Preorder, Inorder);
    	return Node;
    }
    void Postorder(Binode* Node)
    {
        
    	if (Node == NULL)
    		return;
    	Postorder(Node->lchild);
    	Postorder(Node->rchild);
    	cout << Node->data;
    }
    void destroy(Binode* root)
    {
        
    	if (root != NULL)
    	{
        
    		destroy(root->lchild);
    		destroy(root->rchild);
    		delete root;
    	}
    }
    int main()
    {
        
    	Binode *root=NULL;
    	char Preorder[MAX];
    	char Inorder[MAX];
    	cout << "请输入前序遍历:";
    	cin >> Preorder;
    	cout << "请输入中序遍历:";
    	cin >> Inorder;
    	int len = strlen(Preorder)-1;
    	root=createBTree(0, len, 0, len, Preorder, Inorder);
    	cout << "该二叉树的后续遍历为:";
    	Postorder(root);
    	destroy(root);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70]: /images/20230209/c8b33c72012749678d33a1189868df36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 1]: /images/20230209/c24650d69edf4088ab20f4d388ed602c.png