根据前序中序序列构建二叉树

2024-06-22 22:48

本文主要是介绍根据前序中序序列构建二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  

  

  问题描述:

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

  思路:

  在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列,才能找到根结点的值。

  如下图所示,前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列,就能确定根结点的值的位置。根据中序遍历特点,在根结点的值1前面的3个数字都是左子树结点的值,位于1后面的数字都是右子树结点的值。

 

 

  

  同样,在前序遍历的序列中,根结点后面的3个数字就是3个左子树结点的值,再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中,分别找到了左右子树对应的子序列。

  既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列,我们可以用同样的方法分别去构建左右子树。也就是说,接下来的事情可以用递归的方法去完成。
  完整的代码示例如下,方式一使用数组存储前序遍历序列和中序遍历序列;方式二使用容器存储。

/*
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
*//*
思路:
先序遍历的第一个元素为根节点,在中序遍历中找到这个根节点,从而可以将中序遍历分为左右两个部分,
左边部分为左子树的中序遍历,右边部分为右子树的中序遍历,进而也可以将先序遍历除第一个元素以外的剩余部分分为两个部分,
第一个部分为左子树的先序遍历,第二个部分为右子树的先序遍历。
由上述分析结果,可以递归调用构建函数,根据左子树、右子树的先序、中序遍历重建左、右子树。
*/
/*
Time:2016年9月9日11:57:07
Author:CodingMengmeng
*//*
方式一:数组+递归
*/
#include <iostream>
using namespace std;//树结点结构体
struct BinaryTreeNode
{int                    m_nValue;BinaryTreeNode*        m_pLeft;BinaryTreeNode*        m_pRight;};//打印树结点
void PrintTreeNode(BinaryTreeNode *pNode)
{if (pNode != NULL){printf("value of this node is : %d\n", pNode->m_nValue);if (pNode->m_pLeft != NULL)printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);elseprintf("left child is null.\n");if (pNode->m_pRight != NULL)printf("value of its right childe is : %d.\n", pNode->m_pRight->m_nValue);elseprintf("right child is null.\n");}else{printf("this node is null.\n");}printf("\n");
}
void PrintTree(BinaryTreeNode *pRoot)
{PrintTreeNode(pRoot);//   if (pRoot != NULL){if (pRoot->m_pLeft != NULL)PrintTree(pRoot->m_pLeft);if (pRoot->m_pRight != NULL)PrintTree(pRoot->m_pRight);}
}/*
preorder 前序遍历
inorder 中序遍历*/BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);
BinaryTreeNode *Construct(int *preorder, int *inorder, int length)//输入前序序列,中序序列和序列长度
{if (preorder == NULL || inorder == NULL || length <= 0)return NULL;return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);}// startPreorder 前序遍历的第一个节点  
// endPreorder   前序遍历的最后后一个节点  
// startInorder  中序遍历的第一个节点  
// startInorder  中序遍历的最后一个节点  BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
{// 前序遍历序列的第一个数字是根结点的值  int rootValue = startPreorder[0];BinaryTreeNode *root = new BinaryTreeNode();root->m_nValue = rootValue;root->m_pLeft = root->m_pRight = NULL;// 只有一个结点if (startPreorder == endPreorder){if (startInorder == endInorder && *startPreorder == *startInorder)return root;elsethrow std::exception("Invalid input.");}//有多个结点// 在中序遍历中找到根结点的值  int *rootInorder = startInorder;while (rootInorder <= endInorder && *rootInorder != rootValue)++rootInorder;if (rootInorder == endInorder && *rootInorder != rootValue)throw std::exception("Invalid input");//  int leftLength = rootInorder - startInorder;    //中序序列的左子树序列长度int *leftPreorderEnd = startPreorder + leftLength;    //左子树前序序列的最后一个结点if (leftLength > 0){// 构建左子树  root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);}if (leftLength < endPreorder - startPreorder)    //(中序序列)若还有左子树,则左子树序列长度应等于当前前序序列的长度//若小于,说明已无左子树,此时建立右子树{// 构建右子树  root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);}//  return root;
}// 测试代码  
void Test(char *testName, int *preorder, int *inorder, int length)
{if (testName != NULL)printf("%s Begins:\n", testName);printf("The preorder sequence is: ");for (int i = 0; i < length; ++i)printf("%d ", preorder[i]);printf("\n");printf("The inorder sequence is:");for (int i = 0; i < length; ++i)printf("%d ", inorder[i]);printf("\n");try{BinaryTreeNode *root = Construct(preorder, inorder, length);PrintTree(root);}catch (std::exception &expection){printf("Invalid Input.\n");}
}// 普通二叉树  
//              1  
//           /     \  
//          2       3    
//         /       / \  
//        4       5   6  
//         \         /  
//          7       8  
void Test1()
{const int length = 8;int preorder[length] = { 1, 2, 4, 7, 3, 5, 6, 8 };int inorder[length] = { 4, 7, 2, 1, 5, 3, 8, 6 };Test("Test1", preorder, inorder, length);
}int main()
{Test1();  system("pause");return 0;
}/*
输出结果:
----------------------------------------------------------------
Test1 Begins:
The preorder sequence is: 1 2 4 7 3 5 6 8
The inorder sequence is:4 7 2 1 5 3 8 6
value of this node is : 1
value of its left child is: 2.
value of its right childe is : 3.value of this node is : 2
value of its left child is: 4.
right child is null.value of this node is : 4
left child is null.
value of its right childe is : 7.value of this node is : 7
left child is null.
right child is null.value of this node is : 3
value of its left child is: 5.
value of its right childe is : 6.value of this node is : 5
left child is null.
right child is null.value of this node is : 6
value of its left child is: 8.
right child is null.value of this node is : 8
left child is null.
right child is null.请按任意键继续. . .
----------------------------------------------------------------*//*
方式二:容器+递归
*/#include <iostream>
#include <vector>
using namespace std;// Definition for binary tree
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};/* 先序遍历第一个位置肯定是根节点node,中序遍历的根节点位置在中间p,在p左边的肯定是node的左子树的中序数组,p右边的肯定是node的右子树的中序数组另一方面,先序遍历的第二个位置到p,也是node左子树的先序子数组,剩下p右边的就是node的右子树的先序子数组把四个数组找出来,分左右递归调用即可*/class Solution {public:struct TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) {int in_size = in.size();//获得序列的长度if (in_size == 0)return NULL;//分别存储先序序列的左子树,先序序列的右子树,中序序列的左子树,中序序列的右子树vector<int> pre_left, pre_right, in_left, in_right;int val = pre[0];//先序遍历第一个位置肯定是根节点node,取其值//新建一个树结点,并传入结点值TreeNode* node = new TreeNode(val);//root node is the first element in pre//p用于存储中序序列中根结点的位置int p = 0;for (p; p < in_size; ++p){if (in[p] == val) //Find the root position in in break;        //找到即跳出for循环}for (int i = 0; i < in_size; ++i){if (i < p){//建立中序序列的左子树和前序序列的左子树in_left.push_back(in[i]);//Construct the left pre and in pre_left.push_back(pre[i + 1]);//前序第一个为根节点,+1从下一个开始记录}else if (i > p){//建立中序序列的右子树和前序序列的左子树in_right.push_back(in[i]);//Construct the right pre and in pre_right.push_back(pre[i]);}}//取出前序和中序遍历根节点左边和右边的子树//递归,再对其进行上述所有步骤,即再区分子树的左、右子子数,直到叶节点node->left = reConstructBinaryTree(pre_left, in_left);node->right = reConstructBinaryTree(pre_right, in_right);return node;}};
    #include <stdlib.h> #include <stdio.h> typedef struct TNode { int value; TNode* lchild; TNode* rchild; }TNode,*BTree;  //根据先序遍历、中序遍历构建二叉树 BTree rebuild(int preOrder[],int startPre,int endPre,int inOrder[],int startIn,int endIn) { //先序遍历和中序遍历长度应相等 if (endPre - startPre != endIn - startIn) return NULL; //起始位置不应大于末尾位置 if (startPre > endPre) return NULL; //先序遍历的第一个元素为根节点 BTree tree = (BTree)malloc(sizeof(TNode)); tree->value = preOrder[startPre]; tree->lchild = NULL; tree->rchild = NULL; //先序遍历和中序遍历只有一个元素时,返回该节点 if (startPre == endPre) return tree; //在中序遍历中找到根节点 int index,length; for (index=startIn;index<=endIn;index++) { if (inOrder[index] == preOrder[startPre]) break; } //若未找到,返回空 if (index > endIn) return NULL; //有左子树,递归调用构建左子树 if (index > startIn)  { length = index-startIn; tree->lchild = rebuild(preOrder,startPre+1,startPre+1+length-1,inOrder,startIn,startIn+length-1); } //有右子树,递归调用构建右子树 if (index < endIn)  { length = endIn - index; tree->rchild = rebuild(preOrder,endPre-length+1,endPre,inOrder,endIn-length+1,endIn); } return tree; } //后序遍历二叉树 void postTraverse(BTree tree) { if (tree->lchild != NULL) postTraverse(tree->lchild); if (tree->rchild != NULL) postTraverse(tree->rchild); printf("%d ",tree->value); } int main() { int preOrder[] = {1,2,4,5,3,6}; int inOrder[] = {4,2,5,1,6,3}; BTree tree = rebuild(preOrder,0,5,inOrder,0,5); postTraverse(tree); printf("\n"); return 0; } 



这篇关于根据前序中序序列构建二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085629

相关文章

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI(简称 RVC)模型是一个基于 VITS(Variational Inference with adversarial learning for end-to-end Text-to-Speech)的简单易用的语音转换框架。 具有以下特点 简单易用:RVC 模型通过简单易用的网页界面,使得用户无需深入了

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

maven 编译构建可以执行的jar包

💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」👈,「stormsha的知识库」👈持续学习,不断总结,共同进步,为了踏实,做好当下事儿~ 专栏导航 Python系列: Python面试题合集,剑指大厂Git系列: Git操作技巧GO

嵌入式Openharmony系统构建与启动详解

大家好,今天主要给大家分享一下,如何构建Openharmony子系统以及系统的启动过程分解。 第一:OpenHarmony系统构建      首先熟悉一下,构建系统是一种自动化处理工具的集合,通过将源代码文件进行一系列处理,最终生成和用户可以使用的目标文件。这里的目标文件包括静态链接库文件、动态链接库文件、可执行文件、脚本文件、配置文件等。      我们在编写hellowor

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

利用命令模式构建高效的手游后端架构

在现代手游开发中,后端架构的设计对于支持高并发、快速迭代和复杂游戏逻辑至关重要。命令模式作为一种行为设计模式,可以有效地解耦请求的发起者与接收者,提升系统的可维护性和扩展性。本文将深入探讨如何利用命令模式构建一个强大且灵活的手游后端架构。 1. 命令模式的概念与优势 命令模式通过将请求封装为对象,使得请求的发起者和接收者之间的耦合度降低。这种模式的主要优势包括: 解耦请求发起者与处理者

Jenkins构建Maven聚合工程,指定构建子模块

一、设置单独编译构建子模块 配置: 1、Root POM指向父pom.xml 2、Goals and options指定构建模块的参数: mvn -pl project1/project1-son -am clean package 单独构建project1-son项目以及它所依赖的其它项目。 说明: mvn clean package -pl 父级模块名/子模块名 -am参数

JAVA用最简单的方法来构建一个高可用的服务端,提升系统可用性

一、什么是提升系统的高可用性 JAVA服务端,顾名思义就是23体验网为用户提供服务的。停工时间,就是不能向用户提供服务的时间。高可用,就是系统具有高度可用性,尽量减少停工时间。如何用最简单的方法来搭建一个高效率可用的服务端JAVA呢? 停工的原因一般有: 服务器故障。例如服务器宕机,服务器网络出现问题,机房或者机架出现问题等;访问量急剧上升,导致服务器压力过大导致访问量急剧上升的原因;时间和