本篇内容介绍了“Java二叉树怎么根据前序和中序推出后续”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联公司专注于垣曲网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供垣曲营销型网站建设，垣曲网站制作、垣曲网页设计、垣曲网站官网定制、重庆小程序开发服务，打造垣曲网络公司原创品牌,更为您提供垣曲网站排名全网营销落地服务。
根据前序跟中序 => 后序
#include
#include
#include
using namespace std;
struct BTreeNode
{
int _value;
BTreeNode*_left;
BTreeNode*_right;
};
//解法一
BTreeNode* RebuildCode(int * PreStart, int *PreEnd, int *InStart, int *InEnd)
{
BTreeNode *root = new BTreeNode();
//新建节点root保存前序第一个节点为根结点
root->_value = PreStart[0];
root-> _left = NULL;
root->_right = NULL;
if(InStart == InEnd && *InStart == *InEnd)
{
return root;
}
//据此节点找到中序遍历此节点的位置
int *rootIn = InStart;
while(*PreStart != *rootIn)
{
rootIn++;
}
//左子树的长度
int leftlen = rootIn-InStart;
//重建左子树
if(leftlen > 0)
{
root->_left = RebuildCode( PreStart+1, PreStart+leftlen, InStart,InStart+leftlen-1);
}
//重建右子树
if(InStart+leftlen < InEnd)
{
root->_right = RebuildCode( PreStart+leftlen+1, PreEnd,InStart+leftlen+1, InEnd);
}
return root;
}
BTreeNode* RebuildTree(int *PreOrder, int *InOrder, int len)
{
//首先判断边界条件
if(PreOrder == NULL || InOrder == NULL || len <= 0)
{
return NULL;
}
else
{
return RebuildCode(PreOrder, PreOrder+len-1, InOrder, InOrder+len-1);
}
}
//后序遍历输出二叉树序列
void PostOrder(BTreeNode *root)
{
if(root->_left != NULL)
{
PostOrder(root->_left);
}
if(root->_right != NULL)
{
PostOrder(root->_right);
}
if(root != NULL)
{
cout<_value<<" ";
}
}
int main()
{
int PreOrder[8] = {1,2,4,7,3,5,6,8};
int InOrder[8] = {4,7,2,1,5,3,8,6};
PostOrder(RebuildTree(PreOrder, InOrder, 8));
cout<
根据后序跟中序 =>前序
#include
#include
#include
using namespace std;
struct BTreeNode
{
int _value;
BTreeNode*_left;
BTreeNode*_right;
};
//解法一
BTreeNode* RebuildCode(int * PostStart, int *PostEnd, int *InStart, int *InEnd)
{
BTreeNode *root = new BTreeNode();
//新建节点root保存前序第一个节点为根结点
root->_value = PostEnd[0];
root-> _left = NULL;
root->_right = NULL;
if(InStart == InEnd && *InStart == *InEnd)
{
return root;
}
//据此节点找到中序遍历此节点的位置
int *rootIn = InStart;
while(*PostEnd != *rootIn)
{
rootIn++;
}
//左子树的长度
int leftlen = rootIn-InStart;
//重建左子树
if(leftlen > 0)
{
root->_left = RebuildCode( PostStart, PostStart+leftlen-1, InStart,InStart+leftlen-1);
}
//重建右子树
if(InStart+leftlen < InEnd)
{
root->_right = RebuildCode( PostStart+leftlen, PostEnd-1, InStart+leftlen+1, InEnd);
}
return root;
}
BTreeNode* RebuildTree(int *PostOrder, int *InOrder, int len)
{
//首先判断边界条件
if(PostOrder == NULL || InOrder == NULL || len <= 0)
{
return NULL;
}
else
{
return RebuildCode(PostOrder, PostOrder+len-1, InOrder, InOrder+len-1);
}
}
//后序遍历输出二叉树序列
void PreOrder(BTreeNode *root)
{
if(root != NULL)
{
cout<_value<<" ";
}
if(root->_left != NULL)
{
PreOrder(root->_left);
}
if(root->_right != NULL)
{
PreOrder(root->_right);
}
}
int main()
{
int PostOrder[8] = {7,4,2,5,8,6,3,1};
int InOrder[8] = {4,7,2,1,5,3,8,6};
PreOrder(RebuildTree(PostOrder, InOrder, 8));
cout<“Java二叉树怎么根据前序和中序推出后续”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
当前题目：Java二叉树怎么根据前序和中序推出后续
标题路径：http://cdkjz.cn/article/gphopd.html
