大家好，又见面了，我是全栈君。
一、已知先序遍历和中序遍历。求后序遍历。
1、先序遍历序列的第一个元素必然是根节点，能够由此获取二叉树的根节点。
2、依据根节点，在中序遍历序列中查找该节点。由中序遍历的性质可知。中序遍历中该根节点左边的序列必然在根节点的左子树中，而根节点右边的序列必然在右子树中。由此能够知道先序遍历中左子树以及右子树的起止位置。
3、分别对左子树和右子树反复上述的过程，直至全部的子树的起止位置相等时。说明已经到达叶子节点，遍历完成。
实现代码：
#include<cstdio>#include<cstring>#include<cstdlib>struct Node{ char value; Node *left, *right;};Node *build_new_node(char ch){ Node *p = (Node*)malloc(sizeof(Node)); p->value = ch; p->left = p->right = NULL; return p;}Node *Rebuild(char *pre, char *in, int n){ if(n == 0) return NULL; char ch = pre[0]; Node *p = build_new_node(ch); int i; for(i = 0; i < n && in[i] != ch; i++); int l_len = i; int r_len = n - i - 1; if(l_len > 0) p->left = Rebuild(pre+1, in, l_len); if(r_len > 0) p->right = Rebuild(pre+l_len+1, in+l_len+1, r_len); return p;}void PostOrder(Node *p){ if(p == NULL) return ; PostOrder(p->left); PostOrder(p->right); printf("%c",p->value);}int main(){ char PreOrder[100], inOrder[100]; while(~scanf("%s%s",PreOrder, inOrder)) { Node *root = Rebuild(PreOrder,inOrder,strlen(PreOrder)); PostOrder(root); printf("\n"); } return 0;}二、已知中序遍历和后序遍历，求先序遍历。
http://acm.nyist.net/JudgeOnline/problem.php?pid=756
依据中序遍历和后序遍历还原二叉树的主要思想：
1、后序遍历序列的最后一个元素必然是根节点，能够由此获取二叉树的根节点。
2、依据根节点，在中序遍历序列中查找该节点，由中序遍历的性质可知，中序遍历中该根节点左边的序列必然在根节点的左子树中，而根节点右边的序列必然在右子树中。
由此能够知道后序遍历中左子树以及右子树的起止位置。
3、分别对左子树和右子树反复上述的过程，直至全部的子树的起止位置相等时，说明已经到达叶子节点。遍历完成。
实现代码：
#include<cstdio>#include<cstring>#include<cstdlib>struct Node{ char value; Node *left, *right;};Node *build_new_node(char ch){ Node *p = (Node*)malloc(sizeof(Node)); p->value = ch; p->left = p->right = NULL; return p;}Node *Rebuild(char *post, char *in, int n){ if(n == 0) return NULL; char ch = post[n-1]; Node *p = build_new_node(ch); int i; for(i = 0; i < n && in[i] != ch; i++); int l_len = i; int r_len = n - i - 1; if(l_len > 0) p->left = Rebuild(post, in, l_len); if(r_len > 0) p->right = Rebuild(post + l_len, in+l_len+1, r_len); return p;}void PreOrder(Node *p){ if(p == NULL) return ; printf("%c",p->value); PreOrder(p->left); PreOrder(p->right);}int main(){ char PostOrder[100], InOrder[100]; while(~scanf("%s%s",PostOrder, InOrder)) { Node *root = Rebuild(PostOrder,InOrder,strlen(PostOrder)); PreOrder(root); printf("\n"); } return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116630.html原文链接：https://javaforall.net
