二叉树先知道后序和中序，求先序

已知二叉树的中序序列和后序序列，怎么求前序序列？~

确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点。

扩展资料：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
参考资料来源：百度百科--二叉树

确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点。

扩展资料：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
参考资料来源：百度百科--二叉树

后序DABEC 中序DEBAC；由后序最后一个字母知：整个树的开始结点为C；由中序C的位置知：C前面的为结点C的左子树；C后面的为结点C的右子树；所以经过第一次推理，C为根结点，DEBA为其左子树；然后去掉C，考虑下面的左子树。

后序DABE 中序DEBA由后序最后一个字母知：整个左子树的开始结点为E；由中序E的位置知：E前面的为结点E的左子树；E后面的为结点E的右子树；所以经过第一次推理，E为开始结点，D为E的左结点。BA为E的右结点。

然后去掉DE，考虑下面E的右子树；后序AB 中序BA易知：B为根结点，A为其右结点；所以整个树为：C(E(D，B(，A)))；先序：CEDBA。

扩展资料：

二叉树类型：

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

后序DABEC 中序DEBAC
由后序最后一个字母知:整个树的开始结点为C;
由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树;
所以经过第一次推理,C为根结点,DEBA为其左子树;
然后去掉C,考虑下面的左子树;
后序DABE 中序DEBA
由后序最后一个字母知:整个左子树的开始结点为E;
由中序E的位置知:E前面的为结点E的左子树;E后面的为结点E的右子树;
所以经过第一次推理,E为开始结点,D为E的左结点.BA为E的右结点.
然后去掉DE,考虑下面E的右子树;
后序AB 中序BA
易知:B为根结点,A为其右结点.
所以整个树为:C(E(D,B(,A)));
先序:CEDBA

感觉最佳答案的B和A反了

呵呵，又看到你问这种题，你学什么专业啊？最近是不是学《数据结构》这门课啊？我去年才学过
1楼和2楼的都回答的很正确
呵呵，这么多高手关注你一定能学好这门课的。加油！

---

船营区15117423055： 二叉树的已知后序中序求先序算法 - ？
沃侮来弗： /* 树中已知中序和后序求先序.如中序为:bdac 后序为:dbca则程序可以求出先序为:abdc .此种题型为数据结构常考题型. 算法思想:后序遍历树的规则为左右中,则说明最后一个元素必为树的根节点,比如上例 中的a就为根节点,由于...

船营区15117423055： 二叉树先知道后序和中序,求先序 - ？
沃侮来弗： 后序DABEC 中序DEBAC 由后序最后一个字母知:整个树的开始结点为C; 由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树; 所以经过第一次推理,C为根结点,DEBA为其左子树; 然后去掉C,考虑下面的左子树; 后序DABE 中序DEBA 由后序最后一个字母知:整个左子树的开始结点为E; 由中序E的位置知:E前面的为结点E的左子树;E后面的为结点E的右子树; 所以经过第一次推理,E为开始结点,D为E的左结点.BA为E的右结点. 然后去掉DE,考虑下面E的右子树; 后序AB 中序BA 易知:B为根结点,A为其右结点. 所以整个树为:C(E(D,B(,A))); 先序:CEDBA

船营区15117423055： 已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列 - ？
沃侮来弗： 首先理解概念: 前序遍历:访问根结点的操作发生在遍历其左右子树之前. 中序遍历:访问根结点的操作发生在遍历其左右子树之中(间). 后序遍历:访问根结点的操作发生在遍历其左右子树之后. eg:后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历(网上例子) 解:首先 看后序遍历DBCEFGHA,A为总根节点然后 寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝;重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...最后得到AECDBHGF,再自己验证即可...

船营区15117423055： 已知二叉树中序和后序遍历怎么求前序遍历遍历啊? - ？
沃侮来弗： 自己写个stack 我给你写的前后中写法吧. 前MyStack<TreeNode *> stack;while(true){while (lpCurNode){if (lpfun!=NULL){(this->*lpfun)(lpCurNode);stack.Push(lpCurNode);}lpCurNode=lpCurNode->m_lpLeft;}if (!stack.Pop(lpCurNode))...

船营区15117423055： 已知二叉树的后序和中序怎么求前序 - ？
沃侮来弗： 根据所给两条序列找出根结点,再根据此两序列画出示意图,自然可以写出前序序列

船营区15117423055： 二叉树先序中序问题 - ？
沃侮来弗： 后序最后一个是A,所以A是先序的第一个得到: 先序序列 ABC_EF__ 中序序列 BDE_AG_H 后序序列 _DC_GH_A _____________(A)____________ ____________/___\___________ ________(BDE_)_(G_H)________先序的第二个元素是...

船营区15117423055： 根据下图给出的二叉树,求出先序遍历、中序遍历和后序遍历的结点序列 a / \ b c / / d e \ f - ？
沃侮来弗： 先序遍历abdcef 中序遍历dbaefc 后序遍历dbfeca 其实这种问题的解法很简单,你绕着二叉树从根节点左边画一条线绕过整个2叉树然后回到根节点,先序遍历就是线经过左边的时候的顺序,中序遍历就是线经过下面的时候的顺序,后续遍历就是经过右边的时候的顺序,掌握方法了终身都不用问别人了!见下图

船营区15117423055： 数据结构二叉树已知中序遍历,后序遍历,求先序遍历??? - ？
沃侮来弗： 通过分段来解决,找到根节点(通过后序),然后将中序序列分成两段,左右子树,然后递归进行,分的时候可以利用求中序的左右子树的结点个数来确定后序序列的每段...

船营区15117423055： 二叉树的中序遍历和前序遍历知道怎样求后序遍历 - ？
沃侮来弗： 从前序的第一个结点开始确定根,中序决定左子树和右子树,如第一个结点A,根据中序可知,A的左子树是DBE,右子树是FC,再从前序中确定第二个根B,根据中序可知B的左子树是D,右子树为E,依次重复执行,直到遍历完所有结点.所以后序遍历DEBFCA

船营区15117423055： 已知二叉树后序遍历是dabec,中序遍历是debac,求前序遍历 - ？
沃侮来弗： 由后序(左子树,右子树,根节点)dabec知道根节点为c,再通过中序(左子树,根节点,右子树)知道右子树为空 接着由dabe知道其根节点为e,所以在中序deba中左子树为d右子树为ba 再来,后序ab,中序ba,b为节点,a为右子树 前序遍历序列为cedba ----c ---/ --e -/--\ d ----b -------\ ---------a