根据前序(后序)和中序遍历创建二叉树

爱被打了一巴掌 2022-05-08 15:48 270阅读 0赞

1.  根据前序和中序遍历创建二叉树
2.  根据后序和中序遍历创建二叉树

**注：如果仅仅知道三种遍历中的任何一种是无法准确还原一颗二叉树的**

## 前序和中序创建二叉树 ##

例如：  
![在这里插入图片描述][70]  
对于这样的一颗二叉树，其相应的前序和中序遍历分别是：

DataType preorder[] = { 1, 2, 4, 7, 3, 5, 6 };
    DataType inorder[] = { 4, 7, 2, 1, 5, 3, 6 };

那么如何还原二叉树？  
第一步：根据先序遍历找到二叉树的根节点  
第二步：在中序遍历找到这个根节点，就把左子树和右子树分开了  
第三步：把左子树看成是一颗二叉树，再按照上述步骤做，右子树也是这样

**递推公式：**  
    如果创建了根节点，左子树和右子树都创建好了，只需要将  
    root->left = 左子树; root->right = 右子树;  
**终止条件：**  
    size == 0；//size表示这课二叉树的结点个数，因为我们是通过数  
               组来创建二叉树的，也就是树组元素的个数  
![在这里插入图片描述][70 1]  
**代码如下：**

typedef int DataType;
    
    	typedef struct BNode
    	{
    		DataType data;
    		struct BNode *left;
    		struct BNode *right;
    	}BNode;
    	
    	BNode* CreateNewBNode(DataType data)
    	{
    		BNode *newBNode = (BNode *)malloc(sizeof(BNode));
    		newBNode->data = data;
    		newBNode->left = NULL;
    		newBNode->right = NULL;
    		return newBNode;
    	}
    	BNode *CreateBinaryTree(DataType preorder[], DataType inorder[], int size)
    	{
    		//终止条件
    		if (0 == size)
    		{
    			return NULL;
    		}
    		DataType rootValue = preorder[0];
    		int i = 0;
    		//找中序遍历中根节点的位置
    		for (i = 0; i < size; i++)
    		{
    			if (inorder[i] == rootValue)
    			{
    				break;
    			}
    		}
    		//创建根节点
    		BNode *root = CreateNewBNode(rootValue);
    		//左子树
    		BNode *Tleft = CreateBinaryTree(preorder + 1, inorder, i);
    		root->left = Tleft;
    		//右子树
    		BNode *Tright = CreateBinaryTree(preorder + i + 1, inorder + i + 1, size - 1 - i);
    		root->right = Tright;
    		return root;
    	}
    	
    	void test()
    	{
    		DataType preorder[] = { 1, 2, 4, 7, 3, 5, 6 };
    		DataType inorder[] = { 4, 7, 2, 1, 5, 3, 6 };
    		int size = sizeof(preorder) / sizeof(preorder[0]);
    		BNode *root = CreateBinaryTree(preorder, inorder, size);
    	}

## 后序和中序创建二叉树 ##

对于上面的二叉树，后序和中序遍历分别为：

DataType postorder[] = { 7, 4, 2, 5, 6, 3, 1 };
    	DataType inorder[] = { 4, 7, 2, 1, 5, 3, 6 };

其实后序和中序遍历创建二叉树和前序二和中序创建二叉树在思想上是一样的，唯一不同的就是递归的函数参数  
![在这里插入图片描述][70 2]  
**代码如下：**

BNode *CreateBinaryTree(DataType postorder[], DataType inorder[], int size)
    	{
    		if (0 == size)
    		{
    			return NULL;
    		}
    		DataType rootValue = postorder[size - 1];
    		int i = 0;
    		for (i = 0; i < size; i++)
    		{
    			if (inorder[i] == rootValue)
    			{
    				break;
    			}
    		}
    		BNode *root = CreateNewBNode(rootValue);
    		BNode *Tleft = CreateBinaryTree(postorder, inorder, i);
    		root->left = Tleft;
    		BNode *Tright = CreateBinaryTree(postorder + i, inorder + i + 1, size - 1 - i);
    		root->right = Tright;
    		return root;
    	}
    	
    	void test1()
    	{
    		DataType postorder[] = { 7, 4, 2, 5, 6, 3, 1 };
    		DataType inorder[] = { 4, 7, 2, 1, 5, 3, 6 };
    		int size = sizeof(postorder) / sizeof(postorder[0]);
    		BNode *root = CreateBinaryTree(postorder, inorder, size);
    	}
    	
    	int main()
    	{
    		test1();
    		return 0;
    	}

**在二叉树中，我们经常用到递归，再用递归的时候，经常会用到：递推公式，终止条件  
递推公式：如果左子树和右子树都有了，按照这个二叉树有三个结点往下操作  
终止条件：递归一般都必须有终止条件，按照二叉树的五种基本形态考虑终止条件会比较简单一点  
最后就是要考虑递归函数中的参数会不会发生改变**

[70]: /images/20220506/0cf737223f6148a0816e3bb0bfa52973.png
[70 1]: /images/20220506/478eb897a8a7453680411e540f01868f.png
[70 2]: /images/20220506/da76e49c8b4e477ebbebe82310f3d9d1.png