博客访问： 480591
博文数量： 45
博客积分： 931
博客等级： 准尉
技术积分： 590
注册时间：
分类： C/C++ 17:40:49
今天一个小朋友问到这个问题，顺便复习一下数据结构了。PreOrder(T)=T的根节点+PreOrder(T的左子树)+PreOrder(T的右子树) InOrder(T)=InOrder(T的左子树)+T的根节点+InOrder(T的右子树) PostOrder(T)=PostOrder(T的左子树)+PostOrder(T的右子树)+T的根节点 其中加号表示字符串连接运算例如，对下图所示的二叉树，先序遍历为DBACEGF，中序遍历为ABCDEFG。重建该二叉树：这个算法其实很简单的。
首先你自己要能够根据先序和中序能够手动的建立起来树。
先序串：DBACEGF，先序的第一个节点一定是根节点，这样我们就知道了根节点是D.
再看中序， 在中序串之中，根结点的前边的所有节点都是左子树中，ABCDEFG，所以D节点前面的ABC就是左子树的中序串。再看前续串 DBACEGF， 由于左子树的节点是ABC，我们可以得到左子树的前续周游的串为: BAC. 有了左子树的前序串BAC，和中序串ABC ，我们就可以递归的把左子树给建立起来。 同样，可以建立起右子树。 下面是写的伪代码，（没有编译过）class TreeNode
&&&&char value;
&&&&TreeNode *left;
&&&&TreeNode *right;
&&&&TreeNode(char c): value(c){
&&&&&&&&left = NULL;
&&&&&&&&rigth = NULL;
&&&&~TreeNode() {
&&&&&&&&if(left != NULL) delete left;
&&&&&&&&if(right != NULL) delete right;
};& /**根据前序周游和中序周游，重建一颗二叉树。
&&&* @param pre 前序周游的结果，其中每一个字符表示一个节点的值
&&&* @param mid 中序周游的结果，其中每一个字符表示一个节点的值
&&&* @param n 该树节点总数。
&&&* @return 生成的树的根节点。
&&&&TreeNode* buildTree(char *pre, char *mid, int n)
&&&&&&&&if (n==0) return NULL;
&&&&&&&&char c = pre[0];
&&&&&&&&TreeNode *node = new TreeNode(c); //This is the root node of this tree/sub tree.
&&&&&&&&for(int i=0; i<n && mid[i]!=c; i++);
&&&&&&&&int lenL = i; // the node number of the left child tree.
&&&&&&&&int lenR = n - i -1; // the node number of the rigth child tree.
&&&&&&&&//build the left child tree. The first order for thr left child tree is from
&&&&&&&&// starts from pre[1], since the first element in pre order sequence is the root
&&&&&&&&// node. The length of left tree is lenL.
&&&&&&&&if(lenL > 0) node->left = buildTree(&pre[1], &mid[0], lenL);
&&&&&&&&//build the right child tree. The first order stree of right child is from
&&&&&&&&//lenL + 1(where 1 stands for the root node, and lenL is the length of the
&&&&&&&&// left child tree.)
&&&&&&&&if(lenR > 0) node->right = buildTree(&pre[lenL+1], &mid[lenL+1], lenR);
&&&&&&&&return node;
阅读(15635) | 评论(0) | 转发(0) |
给主人留下些什么吧！~~
请登录后评论。已知中序和后序怎么建立二叉树，求用C语言实现。_百度知道
已知中序和后序怎么建立二叉树，求用C语言实现。
我有更好的答案
//您好，刚写的code//测试通过，如果有疑问，欢迎交流#include&stdio.h&struct&Node{ char& Node&*& Node&*&};//根据中序和后续，创建tree//递归的把后续序列中的最后一个value，当做root节点，并把mid分成两部分，然后back_idx&--//分成两部分后，一定先创建右子树Node*&build_tree(char&*mid,&int&num_pre,&char*&back,&int&&back_idx){ if(back_idx&&&0||num_pre&==&0)
return&NULL; int&i; char&cur_mid&=&back[back_idx]; for(i&=&0;&i&&num_&i++){
if(mid[i]&==&cur_mid)
} if(i&==&num_pre)
return&NULL; else{
Node&*&root&=new&Node();
root-&value&=&cur_
back_idx--;
root-&right&=&build_tree(mid&+&i&+&1,&num_pre&-&i&-&1,&back,&back_idx);
root-&left&=&build_tree(mid,&i,&back,&back_idx);
return& }}Node&*&delete_tree(Node&*&root){&// if(root&!=&NULL){
delete_tree(root-&left);
delete_tree(root-&right);
delete& }}int&main(){ char&mid[10]&=&{&#39;D&#39;,&#39;B&#39;,&#39;G&#39;,&#39;E&#39;,&#39;A&#39;,&#39;C&#39;,&#39;F&#39;}; char&back[10]&=&{&#39;D&#39;,&#39;G&#39;,&#39;E&#39;,&#39;B&#39;,&#39;F&#39;,&#39;C&#39;,&#39;A&#39;}; int&back_idx&=&7&-&1;&//指向当前back中的最后一个元素 Node&*&root&=&build_tree(mid,&7,&back,&back_idx); delete_tree(root); return&0;}
采纳率：75%
来自团队：
为您推荐：
其他类似问题
二叉树的相关知识
&#xe675;换一换
回答问题，赢新手礼包&#xe6b9;
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。LeetCode（106）：从中序与后序遍历序列构造二叉树
时间： 15:07:52
&&&& 阅读：19
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&Medium！
题目描述：
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder =&[9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
解题思路：
这道题要求从中序和后序遍历的结果来重建原二叉树，我们知道中序的遍历顺序是左-根-右，后序的顺序是左-右-根，对于这种树的重建一般都是采用递归来做，可参见http://www.cnblogs.com/grandyang/p/4295245.html，针对这道题，由于后序的顺序的最后一个肯定是根，所以原二叉树的根节点可以知道，题目中给了一个很关键的条件就是树中没有相同元素，有了这个条件我们就可以在中序遍历中也定位出根节点的位置，并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。
C++解法一：
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
<span style="color: # class Solution {
<span style="color: # public:
<span style="color: #
TreeNode *buildTree(vector&int& &inorder, vector&int& &postorder) {
<span style="color: #
return buildTree(inorder, <span style="color: #, inorder.size() - <span style="color: #, postorder, <span style="color: #, postorder.size() - <span style="color: #);
<span style="color: #
<span style="color: #
TreeNode *buildTree(vector&int& &inorder, int iLeft, int iRight, vector&int& &postorder, int pLeft, int pRight) {
<span style="color: #
if (iLeft & iRight || pLeft & pRight) return NULL;
<span style="color: #
TreeNode *cur = new TreeNode(postorder[pRight]);
<span style="color: #
int i = <span style="color: #;
<span style="color: #
for (i = iL i & inorder.size(); ++i) {
<span style="color: #
if (inorder[i] == cur-&val) break;
<span style="color: #
<span style="color: #
cur-&left = buildTree(inorder, iLeft, i - <span style="color: #, postorder, pLeft, pLeft + i - iLeft - <span style="color: #);
<span style="color: #
cur-&right = buildTree(inorder, i + <span style="color: #, iRight, postorder, pLeft + i - iLeft, pRight - <span style="color: #);
<span style="color: #
<span style="color: #
<span style="color: # };
上述代码中需要小心的地方就是递归是postorder的左右index很容易写错，比如 pLeft + i - iLeft - 1, 这个又长又不好记，首先我们要记住 i - iLeft 是计算inorder中根节点位置和左边起始点的距离，然后再加上postorder左边起始点然后再减1。我们可以这样分析，如果根节点就是左边起始点的话，那么拆分的话左边序列应该为空集，此时i - iLeft 为0， pLeft + 0 - 1 & pLeft, 那么再递归调用时就会返回NULL, 成立。如果根节点是左边起始点紧跟的一个，那么i - iLeft 为1， pLeft + 1 - 1 = pLeft，再递归调用时还会生成一个节点，就是pLeft位置上的节点，为原二叉树的一个叶节点。
我们下面来看一个例子, 某一二叉树的中序和后序遍历分别为：
Inorder:　　 　11　　4　　5　　13　　8　　9
Postorder:　　11　　4　　13　　9　　8　　5　　
11　　4　　5　　13　　8　　9　　　　　　=&　　　　　　　　　 5
11　　4　　13　　9　　8　　5　　　　　　　　　　　　　　　　/　　\
11　　4　　 　　13　　&8　　9　　　　　　=&　　　　　　　　　5
11　　4　　　　 13　　9　　8　　 　　　　　　　　　　　　　& /　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8
11　　　　 　　13　　　　9　　　　　　　　=&　　　　　　　　　5
11　　　　　　&13　　　　9　　　　 　　　　　　　　　　　　 & /　　\
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　　8
　　　　　　　　　　　　　　　　　　　　　　　　　　　　/　　　 /&&&& \
　　　　　　　　　　　　　　　　　　　　　　　　　　　11　　& 13　　& 9标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文地址：https://www.cnblogs.com/ariel-dreamland/p/9162452.html
&&国之画&&&& &&&&chrome插件
版权所有 京ICP备号-2
迷上了代码！现在有一个问题，已知二叉树的前序遍历和中序遍历：PreOrder:&&&&&&&& GDAFEMHZInOrder:&&&&&&&&&&& ADEFGHMZ我们如何还原这颗二叉树，并求出他的后序遍历？
我们基于一个事实：中序遍历一定是 { 左子树中的节点集合 }，root，{ 右子树中的节点集合 }，前序遍历的作用就是找到每颗子树的root位置。
算法1输入：前序遍历，中序遍历1、寻找树的root，前序遍历的第一节点G就是root。2、观察前序遍历GDAFEMHZ，知道了G是root，剩下的节点必然在root的左或右子树中的节点。3、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树中的节点，G右侧的HMZ必然是root的右子树中的节点，root不在中序遍历的末尾或开始就说明根节点的两颗子树都不为空。4、观察左子树ADEF，按照前序遍历的顺序来排序为DAFE，因此左子树的根节点为D，并且A是左子树的左子树中的节点，EF是左子树的右子树中的节点。5、同样的道理，观察右子树节点HMZ，前序为MHZ，因此右子树的根节点为M，左子节点H，右子节点Z。
观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了：
从而得到PostOrder:&&&&&& AEFDHZMG改进：更进一步说，其实，如果仅仅要求写后续遍历，甚至不要专门占用空间保存还原后的树。只需要用一个数组保存将要得到的后序，就能实现：
算法2输入：一个保存后序的数组，前序遍历，中序遍历1、确定根,放在数组末尾2、确定左子树的索引范围，放在数组中相同索引的位置。3、确定右子树索引范围，放在数组中对应索引的位置，刚好能放下。4、用左子树的前序遍历和中序遍历，把后序遍历保存在对应索引的位置5、用左子树的前序遍历和中序遍历，把后序遍历保存在对应索引的位置
同样我们可以用中序遍历和后序遍历还原这颗树。
然而，如果是前序遍历和后序遍历，就不能够还原这棵树了，因为无法找到中间点，注意下面这两种情况：
两棵树的前序是相同的，两棵树的后序也是相同的。换句话说，如果有一颗子树，它的根节点的一个子树是空树，那么就无法判定那一个子树是空树。
上算法1和算法2的代码：
#include &iostream&
#include &fstream&
#include &string&
struct TreeNode
struct TreeNode*
struct TreeNode*
TreeNode* BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
if(length == 0)
return NULL;
TreeNode* node = new TreeN
node-&elem = *
int rootIndex = 0;
for(;rootIndex & rootIndex++)
if(inorder[rootIndex] == *preorder)
node-&left = BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
node-&right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
std::cout&&node-&elem&&std::　free(node);
return NULL;
int main(int argc, char** argv){
char* pr="GDAFEMHZ";
char* in="ADEFGHMZ"; BinaryTreeFromOrderings(in, pr, 8); printf("\n"); return 0;}
题目只要求输出后续遍历，可以直接把当前节点的value保存在一个char中。
#include &stdio.h&
#include &stdio.h&
#include &iostream&
using namespace
struct TreeNode
struct TreeNode*
struct TreeNode*
void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
if(length == 0)
//cout&&"invalid length";
char node_value = *
int rootIndex = 0;
for(;rootIndex & rootIndex++)
if(inorder[rootIndex] == *preorder)
BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
cout&&node_value&&
int main(int argc, char* argv[])
printf("Hello World!\n");
char* pr="GDAFEMHZ";
char* in="ADEFGHMZ";
BinaryTreeFromOrderings(in, pr, 8);
printf("\n");
阅读(...) 评论()已解决问题
数据结构中序和后序怎么画二叉树
提问时间： 21:40:14
数据结构中序和后序怎么画二叉树
浏览次数：3919
在数据结构相关信息里，就是对一棵二叉树所有结点的访问前序遵循&根左右&中序遵循&左根右&后序遵循&左右根&根：根节点左：左子女右：右子女如：一棵二叉树 ：A/ \B C/ \ D E前序访问顺序就是：ABDEC（根一定第一个）中序访问顺序就是：DBEAC（根一定在中间）后序访问顺序就是：DEBCA（根一定在最后）。很简单。这也是个递归过程。知道后序，就能找到&根&，是最后一个节点。这样，根节点找出来了，左子数的后序、中序就分离出来了，右子数也分离出来了，这个问题，就化成两个新树的问题。
答案创立者
以企业身份回答&
快速解决你的电商难题
店铺优化排查提升2倍流量
擅长&nbsp 店铺优化
您可能有同感的问题