-
已知二叉树的前序与中序遍历序列,求重建后的二叉树(即是二叉树的重建)
2016-07-27 11:13:12如果已知某二叉树的前序遍历结果为{1,2,4,7,3,5,6,8},中序遍历序列为{4,7,2,1,5,3,8,6},求此重建后的二叉树。 1、实现思路: 我们都知道前序遍历是先访问根节点,然后是左子树,接着是右子树,因此在前序遍历...关于二叉树的概念,想必大家基本上都已经很清楚了,那么在这里我就不再一一赘述了。那么请看下面这道题:如果已知某二叉树的前序遍历结果为{1,2,4,7,3,5,6,8},中序遍历序列为{4,7,2,1,5,3,8,6},求此重建后的二叉树。1、实现思路:我们都知道前序遍历是先访问根节点,然后是左子树,接着是右子树,因此在前序遍历序列中,第一个节点值就是根结点的值。但是在中序遍历中根节点是处在序列的中间,左子树的节点的值是位于根节点的左边,右子树的节点的值位于根结点值的右边,因此我们可以通过扫描中序遍历的序列来确定根节点的值和它的右子树和左子树。分析过程如下图所示:具体的代码实现如下图所示:#include<iostream>using namespace std;//结点信息struct BinaryTreeNode{int _value;BinaryTreeNode* _left;BinaryTreeNode* _right;};BinaryTreeNode* RebuiltTree(int * preorder, int* inorder , int length){//判空if(preorder == NULL || inorder == NULL || length <= 0){return NULL ;}return _RebuiltTree(preorder , preorder + length - 1, inorder , inorder + length - 1);}//重建二叉树--->传入前序遍历序列的头指针与尾指,中序遍历序列的头指针与尾指针针BinaryTreeNode* _RebuiltTree(int * startpreorder, int* endpreorder ,int* startinorder,int * endinorder){int rootvalue = startpreorder [0];//前序遍历序列的第一个值为重建后二叉树的根节点的值BinaryTreeNode* root = new BinaryTreeNode(); //创建一个指针,并为它申请一块空间,并且这个指针有此二叉树每个节点应有的全部内容//将根结点的值赋给root->_value,并且将root->_left 与 root->_right都赋为空root->_value = rootvalue;root->_left = root->_right = NULL;//在前序遍历序列中找根节点if (startpreorder == endpreorder){if (startinorder == endinorder && * startpreorder == *startinorder)//如果此条件满足,则找到根结点的值{return root;}else{cout<< "非法输入" <<endl;}}//在中序遍历中找到根结点的值,然后将中序遍历序列划分为两个区间,一个是根节点左边的左子树区间,一个是根节点右边的右子树区间int* _startinorder = startinorder ;//让_startinorder指向startinorder,以防后面改变startinorder,从而在后面无法确定左子树的区间。//在中序遍历序列中查找根结点的值while (_startinorder <= endinorder && *_startinorder != rootvalue){++_startinorder;}//_startinorder与endinorder相等,并且*_startinorder != rootvalue说明中序遍历序列中没有根节点。if (_startinorder == endinorder && *_startinorder != rootvalue){cout << "非法输入" << endl;}//走到这里说明_startinorder指针已经走到根结点的位置int leftlength = _startinorder - startinorder ;//求出左子树的长度及结点个数int* leftpreorderEnd = startpreorder + leftlength;if (leftlength > 0){//构建左子树root->_left = _RebuiltTree( startpreorder + 1, leftpreorderEnd, startinorder , _startinorder - 1);}if (leftlength < endpreorder - startpreorder){//构建右子树root->_right = _RebuiltTree(leftpreorderEnd + 1, endpreorder, _startinorder+1, endinorder );}return root;}void Test(){BinaryTreeNode* ret = NULL ;int preorder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };int inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };ret = RebuiltTree(preorder, inorder, 8);cout << "ret=" << ret << endl;} -
【算法】满二叉树,已知其先序序列求后续序列 C++实现
2020-09-05 17:29:42正常来说只是知道一个二叉树的先序遍历是无法确定一颗二叉树的,但是作为一棵满二叉树,树的形态确定了,先序遍历的顺序固定为“根左右”的条件下,二叉树也就得以确定。  ...分析
正常来说只是知道一个二叉树的先序遍历是无法确定一颗二叉树的,但是作为一棵满二叉树,树的形态确定了,先序遍历的顺序固定为“根左右”的条件下,二叉树也就得以确定。
那么在满二叉树的情况下,如何通过先序遍历得到后续遍历呢?让我们先进行下面的分析实例分析
以上图二叉树作为例子:
其先序遍历为:abdecfg(根左右)
后续遍历为: debfgca (左右根)通常情况下,我们进先序遍历,一定是从根出发,于是这个根便是整个序列中的“头部”:
a | bdecfg
去掉“头部”以后,剩下的部分由左右两个子树构成。因为先序是根左右的次序,观察&思索也可以发现——剩下的部分从中间等分刚好可以得到这颗树的左右两个子树部分:
bde | cfg
化分出来的两个子序列也是子树的先序遍历:
b | de c | fg于是就形成一个“套娃”。然后首先会做出的反应就是递归。
实现思路
既然已经确定使用递归了,现在的关键就是:怎么递归、在哪里使用递归、递归做什么以及递归结束的条件(也就是寻找最小的子问题)。
通过上述实例的分析,整个满二叉树先序遍历的序列可以的流程为:根->左子树->右子树;每颗子树的流程也是:根->左子树->右子树。现在要获取的是后续遍历,在不耗费额外空间时间重构整棵树的条件下,把这个过程改为:左子树->右子树->根。
在先序序列中如何体现 左子树->右子树->根 的流程呢?不妨在草稿纸上用刚刚的实例看看:
先序拆解:
a | bde | cfg
a | (b| de) | (c| fg)后序(左右根):((de) b)->((fg)c)-> a
可以发现实际上就是把序列分成:头部、左部、右部,然后按照:左部——右部——头部 的顺序输出。头部只有一个字符,左右部本身视作一个新的先序序列再次划分三部。
划到后面,左右部只剩下三个字符组成的先序,此时最后一次化分,可以得到只有头部的先序序列,只需要输出头部就可以了,然后逐步回代,因为子树的头输出过了,组成大树以后,其左右子树也就已经完成的输出,也只需要输出头部即可。于是就有:
化分函数(树先序序列 ){
if(序列数量大于一个){
化分函数(左子树先序序列);
化分函数(右子树先序序列);
}
输出根(头部序列);
}代码实现
#include <iostream> //#include<cmath> using namespace std; #define GET_ARRAY_LEN(array, len) { len = sizeof(array)/sizeof(array[0]);} //获取数组长度宏 /** * @a 目标数组 * @begin 子树开始的下标 * @end 子树结束的下标 **/ void preToPost(char a[], int begin, int end ) { char root = a[begin]; //暂存根,子树遍历完后最后输出 if (begin + 1 <= end) { begin = begin + 1;//左端+1(把根节点独立出来) //此时左子树从begin+1位开始,到(begin+end)/2)结束 preToPost(a, begin,((begin+end)/2)); //左子树 //此时右子树从((begin+end)/2) + 1)位开始,到end结束 preToPost(a, (((begin+end)/2) + 1), end); //右子树 } cout << root; //输出根 } void main() { //测试数据 //char a[] = { 'a','b','d','h','i','e','j','k','c','f','l','m','g','n','o' }; char a[] = { 'a','b','d','e','c','f','g' }; int length; //字符数组长度 /* 这里可以添加一个判断序列数量是否满足满二叉树的判定 if ( ) { cout<<"输出数据不满足满二叉树条件"<<endl; return ;// 判断是否满足满二叉树的条件 }*/ GET_ARRAY_LEN(a, length); //调用写好的宏得到数组长度 //测试数据输出 cout<<"先序遍历为:"<<endl; for (int i = 0;i < length;i++) cout << a[i]; cout << endl; cout<<"后序遍历为:"<<endl; preToPost(a, 0, length - 1); cout << endl << endl << endl << endl; }
测试结果
运行环境:Windows10 家庭版、Visual Studio 2019 -
树、森林和二叉树的转换
2020-02-02 09:57:06树的先根序列对应二叉树的先序遍历 树的后根序列对应二叉树的中序遍历 从树的二叉链表表示的定义可知,任何一棵和数对应的二叉树,其右子树必为空。 都遵循这样一个规律:左孩子右兄弟(也就是说,在二叉树转换...树、森林和二叉树的转换
树转换为二叉树:
树的先根序列对应二叉树的先序遍历
树的后根序列对应二叉树的中序遍历
从树的二叉链表表示的定义可知,任何一棵和数对应的二叉树,其右子树必为空。
都遵循这样一个规律:左孩子右兄弟(也就是说,在二叉树转换为树或者是森林的时候,左孩子是左孩子,右孩子是左孩子的兄弟)
下面请IGN
森林转换为二叉树
(1)把每棵树转换为二叉树。
(2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。
-
二叉树及其遍历 树的遍历 && 还原二叉树 (25 分)
2021-02-25 14:51:01下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出为一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 本题主要分成两个...4-1-1 && 4-1-4 二叉树及其遍历 树的遍历 && 还原二叉树 (25 分)
4-1-4 二叉树及其遍历 还原二叉树 (25 分)
给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。
输入格式:
输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。
输出格式:
输出为一个整数,即该二叉树的高度。
输入样例:
9 ABDFGHIEC FDHGIBEAC
输出样例:
5
本题主要分成两个部分:根据先序和中序遍历序列建树、求高度
(中 + 先/后 -> 后/先)(即必须包含中序遍历序列)
根据先序和中序遍历序列建树:先序序列第一个是根节点,根据根节点在中序序列的位置可以确定左子树和右子树的元素,然后开始递归建左右子树
求高度:递归实现
//中 + 先 -> 后 #include<iostream> using namespace std; #define MAXN 55 struct Tree { char ch; struct Tree* left; struct Tree* right; }; typedef struct Tree* PTree; PTree BuildTree(char* pre, char* in, int n) { if (n == 0)return NULL; int m;//找到头结点在中序序列中的位置 for (m = 0; in[m] != pre[0]; m++); PTree T = new Tree; T->ch = pre[0]; T->left = BuildTree(pre + 1, in, m);//建立左子树 T->right = BuildTree(pre + m + 1, in + m + 1, n - m - 1);//建立右子树 return T; } int GetHeight(PTree T) { if (T == NULL) return 0; int m = GetHeight(T->left); int n = GetHeight(T->right); return max(m + 1, n + 1); } int main() { int n; cin >> n; char preorder[MAXN], inorder[MAXN]; for (int i = 0; i < n; i++) cin >> preorder[i];//先序 for (int i = 0; i < n; i++) cin >> inorder[i];//中序 PTree T = BuildTree(preorder, inorder, n); cout<< GetHeight(T); return 0; }
思考:如何根据后序遍历序列和中序遍历序列建树?
4-1-1 二叉树及其遍历 树的遍历 (25 分)
给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例:
7 2 3 1 5 7 6 4 1 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2
#include<iostream> #include<queue> using namespace std; #define MAXN 35 typedef struct Tree* pTree; struct Tree { int data; pTree left; pTree right; }; pTree BuildTree(int* post, int *in, int n) { if (n == 0)return NULL; int m; for (m = n - 1; in[m] != post[n - 1]; m--); pTree T = new Tree; T->data = post[n - 1]; T->left = BuildTree(post, in, m); T->right = BuildTree(post + m, in + m + 1, n - m - 1); return T; } void Levelorder(pTree T) { int flag = 0; queue<pTree>q; q.push(T); while (!q.empty()) { pTree temp = q.front(); q.pop(); if (flag++)cout << " "; cout << temp->data; if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); } } int main() { int postorder[MAXN], inorder[MAXN]; int n; cin >> n; for (int i = 0; i < n; i++) cin >> postorder[i]; for (int i = 0; i < n; i++) cin >> inorder[i]; pTree T = BuildTree(postorder, inorder, n); Levelorder(T); return 0; }
-
有4个节点可以构造出 二叉树_构造二叉树和二叉树遍历
2021-01-29 21:57:41一、构造二叉树①:在数据结构中,我们一般都会有...下面直接用例子讲最通俗易懂的了:例:前序和中序,构造二叉树下面还有两个例子,你们可以尝试做一下:1、已知一棵二叉树的前序序列为:A,B,D,G,J,E,H,C,F,I,K,L... -
PTA 还原二叉树
2020-08-19 22:06:36下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出为一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 先看怎么恢复... -
在平衡二叉树中的每个结点中增设一个域lsize,存储以该结点为根的左子树中的结点个数加1.确定树中第k(k>=1)...
2020-08-26 17:56:53二叉排序树中第k个结点,即为二叉排序树中序序列中顺序号为k的结点,根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点,先需将k与根结点的顺序号进行比较,若相等,则找到;若k小于根结点的... -
前序中序后序遍历_构造二叉树和二叉树遍历
2020-12-06 14:50:33一、构造二叉树①:在数据结构中,我们一般都会有...下面直接用例子讲最通俗易懂的了:例:前序和中序,构造二叉树下面还有两个例子,你们可以尝试做一下:1、已知一棵二叉树的前序序列为:A,B,D,G,J,E,H,C,F,I,K,L... -
7-23 还原二叉树 (25 分)
2018-11-01 20:29:16给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。 输入格式: 输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别... -
中根遍历二叉查找树所得序列一定是有序序列_二叉搜索树(BST)
2020-12-03 08:12:47前面我们介绍了树的基本概念,并引出了...下面,我们先来看一看二叉搜索树。BST(BinarySearchTree,二叉搜索树)可以提高查找的性能,二叉搜索树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,平均为O(lo... -
剑指offer-28:对称二叉树
2019-05-04 16:03:32首先定义一种前序遍对称的算法,先遍历一棵二叉树的根结点,再遍历它的右子结点,最后遍历它的左子结点。 以下面两棵树为例: 对于树A,可以图中看出它明显对称。它的前序遍历序列为{1,2,3,4,2,4,3},前序对称遍历... -
数据结构与算法——7-23 还原二叉树 (25分)
2020-07-24 21:28:29下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出为一个整数,即该二叉树的高度。 思路:根据前序遍历和中序遍历来确定左右子树,先找到树根即前序... -
由前序遍历和中序遍历重建二叉树
2017-07-29 12:57:56由前序遍历和中序遍历重建二叉树(前序序列:1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5)今天Val来分享如何利用一个前序遍历和中序遍历来重建...下面以图中二叉树为例子讲解:由前序遍历结果我们可以知道每次遍历的根节 -
练习(8-29)
2019-08-29 21:51:03答:一棵树的先根遍历与其对应二叉树的先序遍历结果相同,树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。 由于二叉树表示的先序遍历和中序遍历棵唯一确定一棵二叉树。因此给定一棵树的先根遍历序列和后跟... -
选择排序—堆排序(Heap Sort)
2020-05-10 17:05:54堆的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆 性质:每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆;每个... -
数据结构 树 思考题3
2020-03-17 12:48:08题目1:给出下面这棵树的中序遍历结果 根据中序遍历的程序: 我们可以看到它先不断往左遍历,然后在分叉处到根...题目2:非递归方法中序遍历下面这颗二叉树,其堆栈操作序列(P代表为push,O代表为pop)是什么?... -
考研数据结构——排序(二)堆排序、简单选择排序、基数排序
2020-09-09 15:33:03(1)先把序列按照完全二叉树的排列方法写出来。 (2)从下往上、从左往右找到第一个非叶子结点开始,进行堆调整。如果父结点大于子结点,则不用调整;如果父结点小于子结点,则把父结点和子结点中较大的一个交换。... -
数据结构(C++)有关练习题
2008-01-02 11:27:182、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、... -
pat根据中序遍历和先序遍历_PAT甲题题解-1119. Pre- and Post-order Traversals (30)-(根据前序、后序求...
2021-01-12 09:11:22已知前序遍历和后序遍历序列,是无法确定一棵二叉树的,原因在于如果只有一棵子树可能是左孩子也有可能是右孩子。由于只要输出其中一个方案,所以假定为左孩子即可。下面就是如何根据前序和后序划分出根节点和左右... -
计算机二级公共基础知识
2011-04-30 14:00:09例如,长度为8的线性表关键码序列为:[6,13,27,30,38,46,47,70],被查元素为38,首先将与线性表的中间项比较,即与第4个数据元素30相比较,38大于中间项30的值,则在线性表[38,46,47,70]中继续查找;... -
PAT甲题题解-1119. Pre- and Post-order Traversals (30)-(根据前序、后序求中序)
2016-12-04 16:12:00已知前序遍历和后序遍历序列,是无法确定一棵二叉树的,原因在于如果只有一棵子树可能是左孩子也有可能是右孩子。由于只要输出其中一个方案,所以假定为左孩子即可。下面就是如何根据前序和后序划分出根节点和左右... -
数据结构实验
2012-04-13 09:55:47例如:当n=8,m=4,i=1时,得到的新序列为: 4,8,5,2,1,3,7,6 编写程序选择循环队列作为存储结构模拟整个过程,并依次输出出列的各人的编号。 实验4:矩阵的压缩存储及相关操作 (第11周星期三7、8节) 一 、... -
计算机二级C语言考试题预测
2010-06-08 18:29:34(53) 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(A) 注:P38,前提要掌握三种遍历的方法 A. cedba B. acbed C. decab D. deabc (54) 在下列几种排序方法中,要求内存量最大的是(D) 注... -
导师计划--数据结构和算法系列(上)
2020-12-09 04:46:22它应该满足下面的特征: <ul><li>集合中必存在唯一的一个“第一个元素”</li><li>集合中必存在唯一的一个“最后的元素”</li><li>除最后一元素之外,其它数据元素均有唯一的“后继”</li><li>除第一个... -
oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串
2017-05-06 20:26:521. 层次结构模型: 层次结构模型实质上是一种有根结点的定向有序树,IMS(Information Manage-mentSystem)是其典型代表。 2. 网状结构模型:按照网状数据结构建立的数据库系统称为网状数据库系统,其典型代表是DBTG...
-
用微服务spring cloud架构打造物联网云平台
-
企业数字化升级之路百家企业数字化转型发展分析报告.pdf
-
华为1+X认证——网络系统建设与运维(初级)
-
numpy基本操作
-
VMware vSphere ESXi 7 精讲/VCSA/VSAN
-
MHA 高可用 MySQL 架构与 Altas 读写分离
-
MMM 集群部署实现 MySQL 高可用和读写分离
-
【Python-随到随学】FLask第二周
-
零基础一小时极简以太坊智能合约开发环境搭建并开发部署
-
浙江科技学院《C语言程序设计》两套期末考试试卷(含答案).pdf
-
IDE---Intellij 创建maven工程没有提示SpringConfig的xml文件
-
Vue——解决退出登陆后返回上一页问题
-
中国近现代史纲要课后习题答案及备考题库.pdf
-
浙江科技学院《结构力学》题库.pdf
-
注解与反射
-
hibernate5.0.2Set.rar
-
行政法与行政诉讼法--期末复习资料.pdf
-
LVS + Keepalived 实现 MySQL 负载均衡与高可用
-
【布道者】Linux极速入门
-
2021-03-02任务