已知一个二叉树的先序和中序序列,能否唯一确定一棵二叉树?请举例说明.
可以啊，先序(根左右)ABDCE，中序（左根右）：BDAEC
根据先序可以知道根结点为A，
根据中序可知道从A分开，BD为左子树，CE为右子树
左子树：根据先序可知道B为BD子树的根结点，在结合中序可知道D为B的右子树
右子树：根据先序可知C是右子树的根结点，根据中序EC可知道E是C的左子树
很简单，还是一个递归过程。在函数中以先序遍历的第一个结点在中序遍历中为界把中序遍历分为两半，再分别把左一半和右一半作为这个结点的左子树和右子树进行递归。只是完成递归之后不用打印该结点即可。结束递归的条件是左子树或右子树没有结点。还加了一个简单打印二叉树的printTree实现。
#include
struct TreeNode
{
char c;
struct TreeNode *pLeft, *pRight;
};
void createTree(struct TreeNode *r, char *rflist, char *rmlist)
{
char *rmLeftNodes, *rmRightNodes, *pRoot;
int lenLeft;
r->c = *rflist++;
rmLeftNodes = rmlist;
pRoot = strchr(rmlist, r->c);
*pRoot = '\0';
lenLeft = strlen(rmLeftNodes);
if (!lenLeft)
{
r->pLeft = NULL;
}
else
{
r->pLeft = (struct TreeNode *)malloc(sizeof(struct TreeNode));
createTree(r->pLeft, rflist, rmLeftNodes);
}
rmRightNodes = ++pRoot;
if (rmRightNodes && !strlen(rmRightNodes))
{
r->pRight = NULL;
}
else
{
r->pRight = (struct TreeNode *)malloc(sizeof(struct TreeNode));
createTree(r->pRight, rflist+lenLeft, rmRightNodes);
}
}
int main(int argc, char *argv[])
{
struct TreeNode root = {NULL, NULL, NULL};
createTree(&root, argv[1], argv[2]);
}
分析思路。
1、先序就是根左右，中序就是左根右。所以在先序中a在前即为根。在中序中找到a，则dbe为其左子树，fc为其右子树。
2、dbe左子树在先序中b在前说明b为根，则中序中d为b左子树，e为b右子树。
3、同理fc在先序中c在前说明c为根，中序中f在c前，说明f为c的左子树。
即得如下图
a
/ \
b c
/ \ /
d e f
已知二叉树的先序序列,怎么建立二叉树并求其叶子结点和深度???~_百度...
二叉树的建立与遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述 已知一个按先序序列输入的字符序列,如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树,最后求出叶子节点个数和二叉树深度。 输入 输入一个... 展开 kate...
二叉树的先序、中序、后序是如何确定的?
二叉树的先序，中序，后序确定的方法如下：1、根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。2、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是r0ot的左子树，G右侧的HMZ必然是root的右子树。3、观察左子树ADEF，左子树的中的根节点必然是大树的root的left...
为什么已知一棵二叉树的前序遍历和后序遍历序列,不能唯一确定这棵二叉树...
例如：已知一棵二叉树的前序遍历和后序遍历序列分别为ABC和CBA，则以下四棵二叉树均符合要求：A A A A \\ \\ \/ \/ B B B B \\ \/ \/ \\ C C C C
若二叉树的先序遍历序列与中序遍历序列相同且树中结点数大于1,则该...
【答案】：D 本题考查二叉树基本运算。先序遍历二叉树时，先访问根结点，然后先序遍历根的左子树，最后遍历根的右子树。因此，二叉树的先序遍历序列中第一个结点是树根结点。中序遍历二叉树时，首先中序遍历根结点的左子树，然后访问根结点，最后中序遍历根的右子树。因此，若已知二叉树的根结点，则...
已知一棵二叉树的先序和中序序列,能否唯一确定一棵二叉树?并举例
可以啊，先序(根左右)ABDCE，中序（左根右）：BDAEC 根据先序可以知道根结点为A，根据中序可知道从A分开，BD为左子树，CE为右子树 左子树：根据先序可知道B为BD子树的根结点，在结合中序可知道D为B的右子树 右子树：根据先序可知C是右子树的根结点，根据中序EC可知道E是C的左子树 ...
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中,所有叶子结 ...
（1）先序遍历（D L R）：访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历（L D R）：中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历（L R D）：后序遍历左子树；后序遍历右子树；访问根结点。一棵二叉树不论哪种遍历算法，有以下要点：①所有叶子节点先后顺序不...
已知二叉树的先序序列:cbhegaf,中序序列:hbgeacf,请画出所对应的二叉...
首先根据先序序列，确定该树的根节点为C 再根据中序序列，得出其左子树相关结点为 hbgea，右子树只有一个节点f 再根据先序序列，得出左子树的根节点为b。。。以此类推，可得到整棵树的形状
已知二叉树的前序序列为ABCDEFG,中序序列为DBCAFEG,则后序序列为
继续分析，原序列先序被分为两组，BCD和EFG，中序分别为DBC和FEG，先序BCD，中序DBC这棵以A为根的树的左子树，其根为B，用上面方法可知，D在B前面，即D是B的左子树，C在B的后面，即为右子树，(此时，先序应该为BDC，和题目冲突，中序应该为CDBAFEG就对了，或者把先序改一下也可以。)同理...
证明:由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树
因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的.
【紧急求助】某二叉树的前序序列为ABCD,中序序列为DCBA,则后序序列为...
详解为：前序序列的顺序是根、左、右，序列ABCD第一个一定是根结点，A是根节点。中序序列顺序是左、根、右，因为A是根节点，所以DCB位于A左侧，A右侧没有结点，B是DCB三个结点中的根。前序序列是中左右，根结点为A；中序序列是左中右，左子树BCD；遵循遍历序列的规则排列出二叉树，得出后序遍...
乜信维血： 完全可以.例如:先序abdecf,中序dbeafc. 分析思路. 1、先序就是根左右,中序就是左根右.所以在先序中a在前即为根.在中序中找到a,则dbe为其左子树,fc为其右子树. 2、dbe左子树在先序中b在前说明b为根,则中序中d为b左子树,e为b右子树. 3、同理fc在先序中c在前说明c为根,中序中f在c前,说明f为c的左子树. 即得如下图a/ \b c/ \ / d e f
当阳市14782285006： 已知一棵二叉树的先序和中序序列,能否唯一确定一棵二叉树?并举例 - ？
乜信维血： 可以啊,先序(根左右)ABDCE,中序(左根右):BDAEC根据先序可以知道根结点为A, 根据中序可知道从A分开,BD为左子树,CE为右子树 左子树:根据先序可知道B为BD子树的根结点,在结合中序可知道D为B的右子树 右子树:根据先序可知C是右子树的根结点,根据中序EC可知道E是C的左子树
当阳市14782285006： 已知一个二叉树的先序和中序序列,能否唯一确定一棵二叉树?请举例说明.提示:给出先序和中序序列,再画出对应的树! - ？
乜信维血：[答案] 完全可以.例如:先序abdecf,中序dbeafc.分析思路.1、先序就是根左右,中序就是左根右.所以在先序中a在前即为根.在中序中找到a,则dbe为其左子树,fc为其右子树.2、dbe左子树在先序中b在前说明b为根,则中序中d为b左子树,...
当阳市14782285006： 已知二叉树的前序和中序,构造该二叉树的方法是什么 - ？
乜信维血： 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根...
当阳市14782285006： 1、已知某二叉树的先序和中序遍历序列分别是: 先序:XYDEHCF 中序:DYHEXFC 画出这棵二叉树. - ？
乜信维血： 这个是错的,中序遍历是左子树的节点和右子树的结点混乱了,比如XY是左子树的,而HE是右子树的,不可能出现YHEX的情况
当阳市14782285006： 已知二叉树的先序序列和中序序列怎么求后序序列?不是基于C++的,要在TC环境下能运行的,各位能人帮帮忙吧 - ？
乜信维血： /* 树中已知先序和中序求后序. 如先序为:abdc,中序为:bdac . 则程序可以求出后序为:dbca .此种题型也为数据结构常考题型. 算法思想:先序遍历树的规则为中左右,则说明第一个元素必为树的根节点,比如上例 中的a就为根节点,由...
当阳市14782285006： 已知一颗二叉树的先序序列与中序序列,请画出此二叉树:先序序列:ABCDEFGHIJ;中序序列:CBEDAGHFJI - ？
乜信维血：[答案] a b f c d g i e h j a 的左右孩子结点 分别为 b fb的左右 c dc 无孩子d只有左 ef左右 g ig 只有 右 hi 只有左 j...
当阳市14782285006： 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是什么? - ？
乜信维血： 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA. 前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点.中序遍历的根节点前面的节点均为左子树的节点,所以左子树上...
