二叉树先知道后序和中序,求先序
确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。
递归求解树。将左子树和右子树分别看成一棵二叉树,重复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楼的都回答的很正确
呵呵,这么多高手关注你一定能学好这门课的。加油!
二叉树先、中、后序的简单理解
此外,还有一个命题:给定了二叉树的任何一种遍历序列,都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意的另一种遍历序列,就可以唯一地确定二叉树。例子1:已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba)。(1)中序...
怎么用中序和后续生成二叉树?我只会用前序
已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下:1.根据后序序列的最后一个元素建立根结点;2.在中序序列中找到该元素,确定根结点的左右子树的中序序列;3.在后序序列中确定左右子树的后序序列;4.由左子树的后序序列和中序序列建立左子树;5.由右子树的后序序列和中序序列...
二叉树的前序、中序和后序遍历序列分别是什么?
则该二叉树的前序遍历序列为ABDECF,中序遍历序列为DBEAFC,后序遍历序列为DEBFCA。先序遍历二叉树规则:根-左-右 1、访问根结点;2、先序遍历左子树;3、先序遍历右子树。中序遍历二叉树规则:左-根-右 1、先中序遍历左子树;2、再访问根节点;3、最后访问中序遍历右子树。后序遍历二叉树...
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列...
然后再看中序遍历,e前面只有一个d,所以d是e的左孩子节点,d的位置得到;剩下的b和a就在e的右子树。然后再看后序遍历,dabec,d是一个叶子节点,那么就还有一个叶子节点,那么这个节点就一定是a,那么b就是e的右孩子节点,最后再结合中序遍历就可得出所表示得二叉树。(如果这步没看懂,可以在...
对于二叉树,知道其先序遍历,后序遍历,可不可以求出中序遍历
智力题呀,没几个人会的。答案:不能得到中序的。只用三个节点ABC做试验就可举出反例。如果 先序: ABC, 后序: CBA 生成的二叉树会有四种情况出现。图正在验证,要长时间才能出现 ,请等待
已知二叉树的中序序列,后序序列,怎么求前序序列
确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。递归求解树。将左子树和右...
二叉树的先序、中序和后序遍历序列有什么特点?
【答案】先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是:“左子树—右子树―根”,根据以上原则,解答如下:1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。2)若中序序列与后序序列相同,则或为空树,或为任一结点至...
【小白学算法】8.二叉树的遍历,前序、中序和后序
前序遍历:先输出父节点,再遍历左子树,然后遍历右子树。中序遍历:先遍历左子树,再输出父节点,然后遍历右子树。后序遍历:先遍历左子树,再遍历右子树,最后输出父节点。如图所示的二叉树,它的前中后输出顺序分别就是:前序:1易大师、2寒冰射手、3盲僧、4盖伦 中序:2寒冰射手、1易大师、3...
知道二叉树先序,中序,后序其中的两个顺序列,如何画出二叉树
同样,也可确定右子树的中序和先序序列。 按照上面方法对左子树和右子树可确定各自的根。继续下去即构造出二叉树。(3)由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。设后序序列为:a2,……,an , a1; 中序序列为:ap1,…,api, a1, …,apn 。则 a1为根结点;ap1,…,api...
已知二叉树的中序序列和后序序列,怎么求前序序列
1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。2、求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。3、递归求解树。将左...
沃侮来弗: /* 树中已知中序和后序求先序.如中序为: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