/**
* 问题描述:
* 根据一颗二叉树的前序和中序遍历结果,重构这颗二叉树并输出后序遍历结果
*/
#include <iostream>
using namespace std;
typedef struct node {
int value;
struct node *left;
struct node *right;
}NODE;
NODE *root;
//节点分配函数
NODE *malloc_NODE(int value){
NODE *p = NULL;
p = (NODE *)malloc(sizeof(NODE));
p->value = value;
p->right = NULL;
p->left = NULL;
return p;
}
/**
* 每次递归根节点已经创建好,我们的任务就是递归创建左子树和右子树
* 从图中可以看到:
* 左子树的前序和中序的起始指针很容易找到,但是右子树的
* 前序和中序的起始指针需要知道左子树的长度才行。
* 此外我们还需要维护一个子树的长度tLen,以便知道当前递归是否应该结束。
*/
void rebuild_tree(NODE *root, //当前子树根节点
int *pre, //当前子树先序序列起始指针
int *in, //当前子树中序序列起始指针
int tLen) //当前子树长度(节点个数)
{
/**
* 首先根据中序序列求出"左子树的长度"和"右子树的长度"
*
* Then:
* 左子树"前序起始点" = 当前前序序列起始点 + 1;
* 左子树"中序起始点" = 当前中序序列起始点;
*
* 右子树"前序起始点" = 当前前序序列起始点 + 左子树长度 + 1;
* 右子树"中序起始点" = 当前中序起始点 + 左子树长度 + 1;
*/
//求出根节点在中序序列中的索引(根据这个索引值求左右子树长度)
int root_value = *pre;
int root_index = 0;
int *p = in;
for(int i=0;i<tLen;i++){
if(*p++ == root_value) break;
root_index++;
}
//求解左子树和右子树的长度
int lLen = root_index;
int rLen = tLen-root_index-1;
//递归左子树
if(lLen != 0){
root->left = malloc_NODE(pre[1]);
rebuild_tree(root->left, pre+1, in, lLen);
}
else{
root->left = NULL;
}
//递归右子树
if(rLen != 0){
root->right = malloc_NODE(pre[lLen+1]);
rebuild_tree(root->right, pre+lLen+1, in+lLen+1, rLen);
}else{
root->right = NULL;
}
}
//前序遍历输出
void printBST(NODE *node){
if(node != NULL){
cout<<node->value<<endl;
printBST(node->left);
printBST(node->right);
}
}
#define M 5
int main(){
int pre[M] = {1,2,4,5,3};
int in[M] = {4,2,5,1,3};
root = malloc_NODE(pre[0]);
//以root为根节点,按照pre和in两个序列重构二叉树
rebuild_tree(root, pre, in, M);
printBST(root);
return 0;
}
分享到:
相关推荐
根据前序序列和中序序列构建二叉树并输出图形等 采用MFC实现,能够输出图形 单独用前序序列构建,需要在没有孩子的地方加上#号
快速二叉树重构。THU dsa OJ,二叉树重构问题源码
分析写一个简单但不失一般性的例子进行分析:返回二叉树:一步递归:前序序列的第一个元素为当前根结点,create根结点。返回值:本级递归创建根结点后,左右孩子指针
C语言实现二叉树的重建,VC环境下调试,完整源码
真二叉树重构
1、 利用先序遍历和层次遍历的结果建立二叉树 2、 统计二叉树叶子结点的个数(递归)。 3、 给定二叉树的先序和中序遍历结果,重构二叉树。
之前发布的单独c文件,太大,不可重用,所以我把它重构了,打散成.h和.c文件,加入了Makefile进行编译。 用tar命令解压后,就可以make 运行了。详情请看readme,之前发布的单独文件也在里面
二叉树的基本操作:先、中、后和层次遍历,递归和非递归遍历,二叉树的重构.......
c++二叉树的常用算法的实现,包括二叉树重构以及二叉树的一些基本算法
重构二叉树 图 dfs && bfs 会一点 最小生成树 写不出来但是理解 prim 失败 记录一下没做出来的题 这里有很多做不出的啊啊 2021年4月14日12:32:16 2021年4月14日12:36:20 更新 2021年4月17日12:18:38 2021年4月16日15...
C++实现类模板 包括二叉树、搜索二叉树、AVL树及它们的各种算法实现(包括建立、输出、前序遍历、中序遍历、后序遍历、插入、删除、搜索、重构、求树高、统计叶子总数等等)
利用java写了两个案例是关于二叉树和平衡树的分别为数组的和链式的。 功能: 1.三种历遍方式的输出。 2.平衡树的重构。 3.节点的添加以及删除。 4.平均查找长度的计算。
本文实例讲述了Python实现重建二叉树的三种方法。分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串...
基于该方法,一颗具有N个结点的满二叉树中序序列仅需要线性时间复杂度O(N)即可遍历,相关计算过程可嵌入在可重构系统中形成可重构计算单元。还给出了算法的C++实现过程及可重构系统的设计方案。
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。 请设计一个算法来实现...
BAT完整面试笔记:一面: 给定一个先序序列,重构完全二叉树,如果是一般二叉树能不能重构,为什么?
二叉树的序列化与反序列化信息卡片时间: 2020-3-24难度:困难题目描述:序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储
针对传统支持向量机分类方法在脑电信号处理中存在分类正确率低的问题,将聚类思想与二叉树支持向量机结合构造多类SVM分类器。实验以“BCICompetition2005”中的DatasetⅢa为例,先对采集的4类运动想象脑电信号应用小波...
关于层次聚类(hierarchical clustering)的基本步骤: 1、假设每个样本为一类,计算每个...这个计算的过程,相当于重构一个二叉树,只是这个过程,是从树叶-->树枝-->树干的构建过程 本资源详细介绍层次聚类的算法
终于重构好代码了,使用模式:模板模式、策略模式、建造者模式、单一职责,弄一个余弦定理、simhash文本查重代码,并使用二叉排序树和平衡二叉树(待测试)来优化查询。百万数据查重秒查