二叉树经典问题——已知中序和前序重建二叉树

- 日理万妓 2022-06-06 13:44 142阅读 0赞

## 运用前序和中序序列重建二叉树及其相关应用\#\# ##

**重建过程**  
1，在二叉树的学习中经常会遇到一类问题，就是给出一棵二叉树的前序和中序序列（后序和中序类似）然后求树的深度、树的后序序列、树的各种遍历等等问题，这个时候如果能根据相关的序列把其代表的二叉树重建出来，那么所有的问题便会迎刃而解。博文的第一部分就给出相关的重建步骤。  
2，重建中最关键的一点是从前序中找根然后在后序中用相应的根把树‘分解’。举个例子：  
![这里写图片描述][format_png]  
上面这个二叉树对应的3种遍历序列如下：

PreOrder: GDAFEMHZ

InOrder: ADEFGHMZ

PostOrder: AEFDHZMG  
1，因为前序遍历的第一个节点一定是一个二叉树的根，所以从前序的第一个数据开始也就是G，把G映射到中序序列中，并记下在中序序列中的位置（这个位置十分重要！这个位置如果不在中序序列的最左端说明：前序序列中G的下一个数据必定是G的左子树），又因为在中序序列中是按照leftChild—root—rightChild的方式遍历的所以在中序中以上面记下的位置为分界，得到以G为根的左右子树（分别是ADEF和HMZ）。（结合上面的图示容易理解）  
2，上面第一步只是把整个二叉树分出左右子树，然后再在前序中找到下一个数据也就是D，再把D在中序中对应的位置记录下来，此时，D的位置并不在中序序列的最左端（最左端是A），也就说明D还可以继续向下‘派生’左子树，那么继续访问前序序列中的下一个元素也就是A。  
3，同样的步骤，A在中序序列中的位置处于最左端（即A的左子树长度为0），这说明A不能够再有左子树，此时便可以把A的左子树置为nullptr，这时候再考虑A的右子树是否存在，因为在中序序列中A的右面是D，但是D是A的父节点（这个地方看代码会更易于理解，因为代码中明确的显示出A的右子树长度也为0），所以A的右子树置为nullptr。  
4，类似的方式再考虑D的右子树存在问题，如果右子树长度不是0，那么就在前序中选出相应的数据……  
5，……  
整体看上述步骤，其实是一个递归的过程（结合下面的代码看上面的解释更能体会出递归的思想），下面结合代码做简要的解释：  
\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lLQughVW-1571447476348)(https://img-blog.csdn.net/20171110120448475?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2VpeGluXzM3ODE4MDgx/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)\]  
理解上面这个递归函数有两种方式，一种是通过编译器的调试功能，辅助你进入整个递归过程（毕竟测试数据长度有限，浪费不了你多长时间），我这里用的是Visual Studio 2013的调试，例如像下面这样：  
![这里写图片描述][format_png 1]  
通过调用堆栈的窗口你可以看到递归具体的过程和细节，递归深度及各个函数的执行顺序，图中的递归深度已经到达3.  
![这里写图片描述][format_png 2]  
通过变量的监视窗口，你可以实时的锁定某个变量当前的状态从而可以验证你的一些猜测与想法。甚至你可以打开某个变量的层级目录，通过层级目录的方式来理解二叉树的指针指向关系。  
上面这几个工具窗口非常实用，尽管我下面要用另一种方式来理解这个递归函数，但是我依旧鼓励你用这种方式来自己总结出递归的真正细节，这是一个极棒的体验！这样你会在之后的递归程序中迅速掌握各种递归过程，而不需要来我这里浪费时间（\_）。  
另一种方式是不深入递归的具体函数、变量调用的过程，就是只看最外层的函数使用。这样会有一个缺点，就是感觉自己不能真正掌控整个程序，有一种模糊的感觉。当然这摆脱了让大脑遭受超强的负荷，更易于理解递归的实现和功能。  
像上面的那个函数，我们只来想**整个二叉树**：  
1）如果二叉树的长度是0，毫无疑问直接返回nullptr。  
2）不是0，我们应该开辟一块节点的内存，并且把前序序列中的第一个数据（必定是根）装进去。  
3）然后我们要通过循环找出这个根数据在中序序列中的位置，并记录在rootIndex里面。  
4）我们终于来到了递归的门口，函数要开始调用他自己了！rootIndex不在中序的最左端，也就是根存在左子树了，我们让node–>leftChild开辟并装入前序序列的根的下一个数据。我才不会继续想他的下一层递归呢！  
5）挺快，**整个二叉树**的左子树我们完成了（你也许感觉有些唐突，那不怪我，我已经在第一种方式中说过），我们接下来要看G的右子树是否存在。注意看  
node->rightChild = CreateBinTreeByPreInOrder(preSeq + rootIndex + 1, InSeq + rootIndex + 1, subStrLen - (rootIndex + 1));  
这个函数的参数，对于整个二叉树来说，rootIndex此时是4（即G在中序序列中的下标），preSeq作为一个头指针加上左子树的长度（即rootIndex + 1），当然是右子树的第一个节点的数据，自然也应该把搜索的区间缩减到只在右子树的部分（即InSeq + rootIndex + 1），最后确定长度，整个序列的长度减去左子树的长度自然是右子树的总长度（即subStrLen - （rootIndex + 1））；这样只要想象每次进入一棵子树他都会像对待整棵树那样对待每一棵子树，那么我们的目的就达到了！  
下面是完整的代码

/*
    *已知前序遍历序列和中序遍历序列建立二叉树
    *并求其后序遍历序列和层序遍历序列
    */
    #include <iostream>
    #include <string>
    #include <queue>
    #include <string.h>
    //二叉树节点结构定义
    struct BIN_NODE {
    	char data;
    	BIN_NODE *leftChild, *rightChild;
    };
    
    //序列存储变量
    //用户输入字符串测试
    //char preSequence[100];
    //char inSequence[100];
    //指定字符串测试
    char *preSequence = "GDAFEMHZ";
    char* inSequence = "ADEFGHMZ";
    //树根定义
    BIN_NODE *tree;
    //存储下一层节点的队列
    std::queue<BIN_NODE *> memoryNextLevel;
    
    //函数声明
    void PrintBinTreeByPostOrder(BIN_NODE *subTree);		//后序打印二叉树数据域
    void PrintBinTreeByLevelOrder(BIN_NODE *subTree);		//层序打印二叉树数据域
    //通过前序、中序序列建立二叉树
    BIN_NODE * CreateBinTreeByPreInOrder(char* preSeq, char* InSeq, int subStrLen);
    
    int main()
    {
    	int groupsAmount = 0;
    	std::cin >> groupsAmount;
    	while (groupsAmount--) {
    		//std::cin >> preSequence >> inSequence;
    		tree = CreateBinTreeByPreInOrder(preSequence, inSequence, strlen(inSequence));
    		PrintBinTreeByPostOrder(tree);
    		std::cout << std::endl;
    		PrintBinTreeByLevelOrder(tree);
    		std::cout << std::endl;
    	}
    
    	return 0;
    }
    
    //函数定义
    
    BIN_NODE * CreateBinTreeByPreInOrder(char* preSeq, char* InSeq, int subStrLen) {
    	if (0 == subStrLen) {
    		return nullptr;
    	}
    	BIN_NODE *node = new BIN_NODE;
    	if (node == nullptr) {
    		std::cerr << "error" << std::endl;
    		exit(1);
    	}
    	node->data = *preSeq;
    	//前序相应元素在中序中的下标索引值
    	int rootIndex = 0;					
    	//求解这个索引值
    	for (; rootIndex < subStrLen; rootIndex ++) {
    		if (InSeq[rootIndex] == *preSeq) {
    			break;
    		}
    	}
    	node->leftChild = CreateBinTreeByPreInOrder(preSeq + 1, InSeq, rootIndex);
    	node->rightChild = CreateBinTreeByPreInOrder(preSeq + rootIndex + 1, 
    		InSeq + rootIndex + 1, subStrLen - (rootIndex + 1));
    	return node;
    }

相信你也觉得我说的相当玄乎（哈哈），但是我的水平也只能讲到这个程度，我没跟你说过你可以用方式一吗？（自力更生的方法）。到此我们便可以重建出这两个序列所代表的二叉树。下面我们来看看有哪些简单的二叉树操作问题在等着我们。  
请看下一遍博文<<<<  
参考及引用出自：http://blog.csdn.net/feliciafay/article/details/6816871

![公众号：Dawo][Dawo]

[format_png]: /images/20220606/801f474f150a49febdc04437ce23bdde.png
[format_png 1]: /images/20220606/af02ac1b0b11400eb7310ff8bb63ad66.png
[format_png 2]: /images/20220606/f06d40eea9b042eea71dc480d63d04a4.png
[Dawo]: /images/20220606/838182fb170d4a1a872628c7d67475bf.png