C++基于先序、中序遍历结果重建二叉树的方法
本文实例讲述了C++基于先序、中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下:
题目:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
实现代码:
#include#include #include usingnamespacestd; structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; //创建二叉树算法 TreeNode*reConstructBinaryTree(vector pre,vector mid) { intnodeSize=mid.size(); if(nodeSize==0) returnNULL; vector leftPre,leftMid,rightPre,rightMid; TreeNode*phead=newTreeNode(pre[0]);//第一个当是根节点 introotPos=0;//根节点在中序遍历中的位置 for(inti=0;i rootPos) { rightMid.push_back(mid[i]); rightPre.push_back(pre[i]); } } phead->left=reConstructBinaryTree(leftPre,leftMid); phead->right=reConstructBinaryTree(rightPre,rightMid); returnphead; } //打印后续遍历顺序 voidprintNodeValue(TreeNode*root) { if(!root){ return; } printNodeValue(root->left); printNodeValue(root->right); cout< val<<""; } intmain() { vector preVec{1,2,4,5,3,6}; vector midVec{4,2,5,1,6,3}; cout<<"先序遍历序列为124536"< 运行结果:
先序遍历序列为124536 中序遍历序列为425163 后续遍历序列为452631 请按任意键继续...希望本文所述对大家C++程序设计有所帮助。
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下