本篇内容介绍了“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://bjjierui.cn/article/gphopd.html