由中序序列和前序序列确定一棵二叉树
2023-09-14 08:56:53 时间
1、先序序列确定根节点
2、后序序列区分左右子树
#include<iostream> #include<algorithm> #include<vector> #include<math.h> #include<stdio.h> #include<string.h> #include<map> #include<queue> #include<utility> #define ll long long #define maxn 1005 using namespace std; int in[maxn];//中序序列 int pre[maxn];//先序序列 struct node { int data; node* lchild; node* rchild; }; int N,M; node* create(int preL,int preR,int inL,int inR) { if(preL > preR)//当二叉树没有左右节点的时候,说明是叶子节点,即空子树时递归结束 return NULL; node* root = new node; root->data = pre[preL];//将pre的preL值放入到结构体中,这里是确定二叉树的根,即先序遍历的第一个节点 int i ; for(i = inL; i <= inR;i++)//在中序序列中区分左子树和右子树 { if(in[i] == pre[preL]) break; } int numLeft = i - inL;//看左边是否还有节点 //注意这里没有对numLeft的数目进行判断!! root->lchild = create(preL+1,preL+numLeft,inL,i-1); root->rchild = create(preL+numLeft+1,preR,i+1,inR); return root; } //inOrder void inOrder(node* root)//以中序序列输出 { if(root->lchild != NULL ) //输出左节点 inOrder(root->lchild); cout << root->data << " ";//输出根节点 if(root->rchild != NULL ) inOrder(root->rchild);//输出右节点 } void preOrder(node* root)//以先序序列输出 { cout << root->data << " ";//根 if(root->lchild!=NULL) preOrder(root->lchild);//左 if(root->rchild!=NULL) preOrder(root->rchild);//右 } void houOrder(node* root) { if(root->lchild!=NULL)//左 houOrder(root->lchild); if(root->rchild!=NULL)//右 houOrder(root->rchild); cout << root->data << " ";//根 } int main() { cin >> N; int i; for(i = 0;i< N;i++) cin >> in[i]; for(i = 0;i< N;i++) cin >> pre[i]; node* root; root = create(0,N-1,0,N-1); houOrder(root); } // 8 // 7 2 3 4 6 5 1 8 中序 // 5 3 7 2 6 4 8 1 先序 // 2 7 4 6 3 1 8 5 后序
相关文章
- Java实现 LeetCode 659 分割数组为连续子序列 (哈希)
- Java实现 LeetCode 152 乘积最大子序列
- R语言实现金融数据的时间序列分析及建模
- (剑指Offer)面试题41:和为s的连续正数序列
- 【二叉树】106. 从中序与后序遍历序列构造二叉树 【中等】
- python3元组和序列
- leetcode 105. 从前序与中序遍历序列构造二叉树
- ML之FE:特征工程中常用的五大数据集划分方法(留1法/留p法、随机划分法、K折交叉验证法、自定义分割法、特殊类型数据分割法【时间序列数据】、自助采样法)理论讲解及其代码实现
- LSTM对比Bi-LSTM的电力负荷时间序列预测(Matlab)
- LSTM对比Bi-LSTM的电力负荷时间序列预测(Matlab)
- 数学建模学习(38):时间序列和灰色预测模型原理与大概实现
- 106. 从中序与后序遍历序列构造二叉树
- 2-10 出栈序列的合法性
- python 找出序列中出现次数最多的元素方法
- YAML块序列
- 刷题记录:牛客NC20279[SCOI2010]序列操作
- 【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
- 由后序遍历序列和中序遍历序列,构建二叉树【C++版】
- 由先序和中序序列构建一棵二叉树【C++版】