通过先序遍历和中序遍历建立二叉树

电玩女神 2023-03-04 06:32 12阅读 0赞

在对二叉树进行操作之前，建树是必须要做的。假设现在有某二叉树的先序遍历和中序遍历，我们应该如何建树？

## 基本思路： ##

1.  分别求得根节点的左子树和右子树的先序遍历序列与中序遍历序列
2.  分别以左子树和右子树为新树进行第一步操作
3.  直至没有子树为止

**那么我们这么实现呢？**

根据我们对二叉树遍历的学习，可以知道：

*  先序遍历序列中的第一个节点为根节点
 *  一个节点的左右子节点分别位于中序遍历序列中该节点的两侧

**举个例子：**  
![举例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQxMzY4OQ_size_16_color_FFFFFF_t_70]

对于图中二叉树，其先序遍历序列与中序遍历序列如右侧所示，每个序列共6个字母（此二叉树共有6个节点）。

1.  对于整棵树的先序遍历中第一个节点“A”（根节点），其在中序遍历序列中第4个位置，这就说明A的左子树应有3个节点，右子树应有2个节点。
2.  对于左子树的先序遍历中第一个节点“B”，其在中序遍历中第2个位置，说明其左子树有1个节点，右子树有1个节点（“左子树”共3个节点）
3.  对于右子树的第一个节点“C”，其在中序遍历中第2个位置，说明其左子树有一个节点，右子树有0个节点（“右子树”共2个节点）
4.  递归进行，直至当前处理的“树”没有其他子树（即此节点为叶子节点）为止

--------------------

接下来，我们来做最重要的一步：

## 讲上述逻辑转化为计算机语言 ##

（以C++语言，用二叉链表存树为例）

现有两个序列：

*  先序遍历序列：preorderList
 *  中序遍历序列：inorderList

用于标记序列长度的四个变量：

*  先序遍历序列的第一个字母的位置：preBegin
 *  先序遍历序列的最后一个字母的位置：preEnd
 *  中序遍历序列的第一个字母的位置：inBegin
 *  中序遍历序列的最后一个字母的位置：inEnd

设当前处理的节点在中序遍历中的位置为index  
则其左子树节点个数为index-inBegin  
所以可以得到：

*  左子树先序遍历序列区间为\[preBegin+1, preBegin+index-inBegin\]，中序遍历序列区间为\[inBegin, index -1\]
 *  右子树先序遍历序列区间为\[preBegin+index-inBegin+1, preEnd\]，中序遍历序列区间为\[index+1, inEnd\]

**结束条件：“当前节点为叶子节点”**  
如果当前节点为叶子节点，即preBegin == preEnd时需要返回一个“node”；preBegin > preEnd时返回NULL，同样可以说明已经到了叶子节点，这里我们选择后者（叶子节点的类型依然为node，需要将其对子节点的指针设为NULL）。

--------------------

### 节点类型： ###

struct node{
        
    	char data;
    	node *lchild;
    	node *rchild;
    };

### 核心：buildTree函数 ###

node *buildTree(int preBegin, int preEnd, int inBegin, int inEnd, string preorderList, string inorderList){
        
    	if (preBegin > preEnd){
        
    		return NULL;
    	}
    	
    	node *Node = new node;
    	int index = 0;
    	
    	Node -> data = preorderList[preBegin];
    	/*通过遍历中序遍历序列的方式寻得index*/
    	for (int i = inBegin; i < inEnd+1; i++){
        
    		if (preorderList[preBegin] == inorderList[i]){
        
    			index = i;
    			break;
    		}
    	}
    	
    	/*分别对左右子树进行递归操作*/
    	Node -> lchild = buildTree(preBegin+1, preBegin+index-inBegin, inBegin, index-1, preorderList, inorderList);
    	Node -> rchild = buildTree(preBegin+index-inBegin+1, preEnd, index+1, inEnd, preorderList, inorderList);
    
    	return Node;
    }

附完整代码：

#include <iostream>
    #include <string>
    using namespace std;
    
    struct node{
        
    	char data;
    	node *lchild;
    	node *rchild;
    };
    
    node *buildTree(int preBegin, int preEnd, int inBegin, int inEnd, string preorderList, string inorderList){
        
    	if (preBegin > preEnd){
        
    		return NULL;
    	}
    	
    	node *Node = new node;
    	int index = 0;
    	
    	Node -> data = preorderList[preBegin];
    	for (int i = inBegin; i < inEnd+1; i++){
        
    		if (preorderList[preBegin] == inorderList[i]){
        
    			index = i;
    			break;
    		}
    	}
    	
    	Node -> lchild = buildTree(preBegin+1, preBegin+index-inBegin, inBegin, index-1, preorderList, inorderList);
    	Node -> rchild = buildTree(preBegin+index-inBegin+1, preEnd, index+1, inEnd, preorderList, inorderList);
    
    	return Node;
    }
    
    int main (){
        
    	string preorderList;
    	string inorderList;
    	int preBegin, preEnd, inBegin, inEnd;
    	node *root = new node;	
    	
    	cin >> preorderList;
    	cin >> inorderList;
    	
    	preBegin = 0;
    	inBegin = 0;
    	preEnd = preorderList.length() - 1;
    	inEnd = inorderList.length() - 1;
    	
    	root = buildTree(preBegin, preEnd, inBegin, inEnd, preorderList, inorderList);
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQxMzY4OQ_size_16_color_FFFFFF_t_70]: /images/20230208/56eedb8fc5124ee695cc9033bb7011a7.png