好资源导航 » 文章资讯 » C++基于先序、中序遍历结果重建二叉树的方法

C++基于先序、中序遍历结果重建二叉树的方法

2024-02-24 02:57:03 49

本文实例讲述了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(vectorpre,vectormid)
{
intnodeSize=mid.size();
if(nodeSize==0)
returnNULL;
vectorleftPre,leftMid,rightPre,rightMid;
TreeNode*phead=newTreeNode(pre[0]);//第一个当是根节点
introotPos=0;//根节点在中序遍历中的位置
for(inti=0;irootPos)
{
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()
{
vectorpreVec{1,2,4,5,3,6};
vectormidVec{4,2,5,1,6,3};
cout<<"先序遍历序列为124536"<
运行结果：
先序遍历序列为124536
中序遍历序列为425163
后续遍历序列为452631
请按任意键继续...


希望本文所述对大家C++程序设计有所帮助。

返回顶部
514930285
czq8825@qq.com

C++基于先序、中序遍历结果重建二叉树的方法

热门推荐

随机推荐