刷题：二叉树的遍历方式及根据遍历结果还原二叉树

小鱼儿 2022-02-22 04:36 135阅读 0赞

### 二叉树的遍历方式及根据遍历结果还原二叉树 ###

*  1. 二叉树的遍历方式
 *  2. 根据遍历结果还原二叉树
 *   *  2.1 已知先序遍历和中序遍历还原二叉树
     *  2.2 已知后序遍历和中序遍历还原二叉树
 *  实验代码：

# 1. 二叉树的遍历方式 #

二叉树有三种遍历方式：先序遍历、中序遍历、后序遍历。  
**先序遍历**： a、访问根节点；b、前序遍历左子树；c、前序遍历右子树。  
**中序遍历**： a、中序遍历左子树；b、访问根节点；c、中序遍历右子树。  
**后序遍历**：a、后序遍历左子树；b、后续遍历右子树；c、访问根节点。

# 2. 根据遍历结果还原二叉树 #

**已知先序遍历和中序遍历，可以还原二叉树；  
已知中序遍历和后序遍历，可以还原二叉树；  
已知先序遍历和后序遍历，不可以还原二叉树**。

## 2.1 已知先序遍历和中序遍历还原二叉树 ##

思路：  
1）、根据先序遍历结果确定根节点。  
先序遍历的第一个节点为根节点。  
2）、在中序遍历结果中找到根节点，根节点左侧的部分为左子树节点，根节点右侧的部分为右子树节点。  
3）、将中序遍历的结果按根节点分为两部分，迭代的执行第一步和第二步，直到还原整个二叉树。

例如：已知先序遍历的结果为：ABDHIEJKCFLMGNO，中序遍历的结果为：HDIBJEKALFMCNGO。则二叉树为以下结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70_pic_center]  
其后序遍历结果为：HIDJKEBLMFNOGCA

## 2.2 已知后序遍历和中序遍历还原二叉树 ##

思路：  
1）、根据后序遍历结果确定根节点。  
后序遍历的最后一个节点为根节点。  
2）、在中序遍历结果中找到根节点，根节点左侧的部分为左子树节点，根节点右侧的部分为右子树节点。  
3）、将中序遍历的结果按根节点分为两部分，迭代的执行第一步和第二步，直到还原整个二叉树。

例如：已知后序遍历的结果为：HIDJKEBLMFNOGCA，中序遍历的结果为：HDIBJEKALFMCNGO。则二叉树为以下结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70_pic_center 1]  
其先序遍历结果为：ABDHIEJKCFLMGNO

**已知前序和中序，后序和中序遍历序列之后，可以唯一确定一棵二叉树。但是，只知道前序和后序遍历序列，是无法知道哪个结点是左子树还算右子树。**

# 实验代码： #

#include <iostream>
    #include <vector>
    #include "Tree.h"
    using namespace std;
    //************************************     
    // 函数名称：CreateBinaryTree  
    // 函数功能：构建二叉树
    // 返 回 值：无
    // 参    数：二叉树根节点引用、元素指针的引用，元素个数的引用 
    // 函数说明：该函数根据一组元素数据构建二叉树。由于仅仅利用利用一组数据不能推断二叉树的结构，
    //           因此需要在元素数组中加入#来表示某个空节点。此外该函数以先序遍历的方式构建二叉树。
    //           由于该函数需要递归调用并且需要改变参数的值，因此参数均为引用的形式。
    //************************************  /
    void CreateBinaryTree(BiTree &T, ElementPtr &p ,int &num)
    {
    	
    	if ('#' == *p || num == 0)             //当遇到#时，令树的根节点为NULL，从而结束该分支的递归
    	{
    		T = NULL;
    		num--; p++;
    	}	
    	else
    	{
    		T = new TreeNode;
    		T->data = *p;
    		num--;	p++;
    		CreateBinaryTree(T->Lchild, p, num);
    		CreateBinaryTree(T->Rchild, p, num);
    	}
    	
    }
    //************************************     
    // 函数名称：CreateBinaryTree   
    // 函数功能：构建二叉树
    // 返 回 值： 无
    // 参    数：二叉树根节点引用、先序遍历数组引用、中序遍历数组引用 
    // 函数说明：该函数根据先序遍历结果和中序遍历结果构建二叉树
    //************************************  /
    void CreateBinaryTree(BiTree &T,vector<ElementType> & PreOrder, vector<ElementType> & MidOrder)
    {
    	if (PreOrder.size() == 0 || MidOrder.size() == 0)
    	{
    		T = NULL;
    		return;
    	}
    	if (PreOrder.size() != MidOrder.size())
    	{
    		T = NULL;
    		return;
    	}
    
    	vector<ElementType> PreOrder_L, PreOrder_R, MidOrder_R, MidOrder_L;
    	int root_index;
    	int len = PreOrder.size();
    
    	T = new TreeNode;
    	T->data = PreOrder[0];
    	
    
    	for (int i = 0; i < len; ++i)
    	{
    		if (MidOrder[i] == PreOrder[0])
    		{
    			root_index = i;
    			break;
    		}
    	}
    
    	for (int i = 0; i < root_index; ++i)
    	{
    		MidOrder_L.push_back(MidOrder[i]);
    		PreOrder_L.push_back(PreOrder[i + 1]);
    	}
    	for (int i = root_index + 1; i < len; ++i)
    	{
    		MidOrder_R.push_back(MidOrder[i]);
    		PreOrder_R.push_back(PreOrder[i]);
    	}
    
    	 CreateBinaryTree(T->Lchild ,PreOrder_L, MidOrder_L);
         CreateBinaryTree(T->Rchild,PreOrder_R, MidOrder_R);
    
    }
    //************************************     
    // 函数名称：BiTreeDepth   
    // 函数功能：计算二叉树深度
    // 返 回 值： 无
    // 参    数：二叉树根节点
    // 函数说明：计算二叉树深度，递归调用
    //************************************  /
    int BiTreeDepth(BiTree T)
    {
    	int Ldepth, Rdepth;
    	if (T == NULL)
    		return 0;
    	else
    	{
    		Ldepth = BiTreeDepth(T->Lchild);
    		Rdepth = BiTreeDepth(T->Rchild);
    	}
    	return Ldepth > Rdepth ? Ldepth + 1 : Rdepth + 1;
    
    }
    //************************************     
    // 函数名称：PreTraverse 
    // 函数功能：先序遍历
    // 返 回 值：无 
    // 参    数：二叉树根节点
    // 函数说明：二叉树的先序遍历
    //************************************  /
    void PreTraverse(BiTree T)
    {
    	if (T)
    	{
    		cout << T->data << " ";
    		PreTraverse(T->Lchild);
    		PreTraverse(T->Rchild);
    	}
    }
    //************************************     
    // 函数名称：MidTraverse   
    // 函数功能：中序遍历
    // 返 回 值： 无
    // 参    数：二叉树根节点
    // 函数说明：二叉树的中序遍历
    //************************************  /
    void MidTraverse(BiTree T)
    {
    	if (T)
    	{
    		MidTraverse(T->Lchild);
    		cout << T->data << " ";
    		MidTraverse(T->Rchild);
    	}
    }
    //************************************     
    // 函数名称：PostTracerse  
    // 函数功能：后序遍历
    // 返 回 值： 无
    // 参    数：二叉树根节点
    // 函数说明：二叉树的后序遍历
    //************************************  /
    void PostTracerse(BiTree T)
    {
    	if (T)
    	{
    		PostTracerse(T->Lchild);
    		PostTracerse(T->Rchild);
    		cout << T->data << " ";
    	}
    }
    
    //主函数
    int main()
    {
    	//根据一组元素数据构建二叉树
    	BiTree Root;
    	ElementType src[] = { 'A','B','D','G','#','#','H','#','#','#','C','E','#','I','#','#','F','#','#' };
    	int num = sizeof(src);
    	ElementType* p = src;
    	CreateBinaryTree(Root,p,num);//构建完二叉树后p会改变，该问题待优化
    	
    	cout << "PreTraverse： ";
    	PreTraverse(Root);
    	cout << endl;
    	cout << "MidTraverse： ";
    	MidTraverse(Root);
    	cout << endl;
    	cout << "PostTracerse：";
    	PostTracerse(Root);
    	cout << endl;
    	cout << "The Tree Depth: " << BiTreeDepth(Root) <<endl<<endl;
    
    	//根据先序遍历结果和中序遍历结果构建二叉树
    	BiTree Root2;
    	vector<ElementType> Pre = { 'A','B','D','G','H','C','E','I','F' };
    	vector<ElementType> Mid = { 'G','D','H','B','A','E','I','C','F' };
        CreateBinaryTree(Root2,Pre, Mid);
    	cout << "PreTraverse： ";
    	PreTraverse(Root2);
    	cout << endl;
    	cout << "MidTraverse： ";
    	MidTraverse(Root2);
    	cout << endl;
    	cout << "PostTracerse：";
    	PostTracerse(Root2);
    	cout << endl;
    	cout << "The Tree Depth: " << BiTreeDepth(Root2) << endl << endl;
    
    	//根据一组元素数据构建二叉树对象
    	p = src;
    	int num2 = sizeof(src);
    	BinaryTree tree(p, num2);
    	cout << "PreTraverse： ";
    	tree.PreTraverse();
    	cout << endl;
    	cout << "MidTraverse： ";
    	tree.MidTraverse();
    	cout << endl;
    	cout << "PostTracerse：";
    	tree.PostTracerse();
    	cout << endl;
    	cout << "The Tree Depth: " << tree.TreeDepth() << endl<<endl;
    
    	//根据先序遍历结果和中序遍历结果构建二叉树对象
    	BinaryTree tree2(Pre,Mid);
    	cout << "PreTraverse： ";
    	tree2.PreTraverse();
    	cout << endl;
    	cout << "MidTraverse： ";
    	tree2.MidTraverse();
    	cout << endl;
    	cout << "PostTracerse：";
    	tree2.PostTracerse();
    	cout << endl;
    	cout << "The Tree Depth: " << tree.TreeDepth() << endl << endl;
    
    	return 0;
    }

实验结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220222/60fd8ff4f51947f8a1028f1b2d84517f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220222/c72988cc309f4a1d8ad0fea1e659734f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3MDk3NjA_size_16_color_FFFFFF_t_70]: /images/20220222/02903e26690348298cddf770426b6fda.png