算法之二叉树中序前序序列(或后序)求解树
这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的。<1>已知二叉树的前序序列和中序序列，求解树。1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点边和右边都为空，则根节点已经为叶子节点。3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。<2>、已知二叉树的后序序列和中序序列，求解树。1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点边和右边都为空，则根节点已经为叶子节点。3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。测试用例：<1>先序 中序 求 后序输入：先序序列：ABCDEGF中序序列：CBEGDFA输出后序：CGEFDBA代码：[cpp]/*PreIndex: 前序序列字符串中子树的第一个节点在PreArray[]中的下标InIndex: 中序序列字符串中子树的第一个节点在InArray[]中的下标subTreeLen: 子树的字符串序列的长度PreArray： 先序序列数组InArray：中序序列数组*/void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){//subTreeLen < 0 子树为空if(subTreeLen <= 0){T = NULL;return;}else{T = (BiTree)malloc(sizeof(BiTNode));//创建根节点T->data = PreArray[PreIndex];//找到该节点在中序序列中的位置int index = strchr(InArray,PreArray[PreIndex]) - InArray;//左子树结点个数int LenF = index - InIndex;//创建左子树PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);//右子树结点个数(总结点 - 根节点 - 左子树结点)int LenR = subTreeLen - 1 - LenF;//创建右子树PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);}}/*PreIndex: 前序序列字符串中子树的第一个节点在PreArray[]中的下标InIndex: 中序序列字符串中子树的第一个节点在InArray[]中的下标subTreeLen: 子树的字符串序列的长度PreArray： 先序序列数组InArray：中序序列数组*/void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){//subTreeLen < 0 子树为空if(subTreeLen <= 0){T = NULL;return;}else{T = (BiTree)malloc(sizeof(BiTNode));//创建根节点T->data = PreArray[PreIndex];//找到该节点在中序序列中的位置int index = strchr(InArray,PreArray[PreIndex]) - InArray;//左子树结点个数int LenF = index - InIndex;//创建左子树PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);//右子树结点个数(总结点 - 根节点 - 左子树结点)int LenR = subTreeLen - 1 - LenF;//创建右子树PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);}}主函数调用：[cpp]BiTree T;PreInCreateTree(T,0,0,strlen(InArray));PostOrder(T);BiTree T;PreInCreateTree(T,0,0,strlen(InArray));PostOrder(T);<2>中序 后序 求先序输入：中序序列：CBEGDFA后序序列：CGEFDBA输出先序：ABCDEGF代码：[cpp]/*PostIndex: 后序序列字符串中子树的最后一个节点在PreArray[]中的下标InIndex: 中序序列字符串中子树的第一个节点在InArray[]中的下标subTreeLen: 子树的字符串序列的长度PostArray： 后序序列数组InArray：中序序列数组*/void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){//subTreeLen < 0 子树为空if(subTreeLen <= 0){T = NULL;return;}else{T = (BiTree)malloc(sizeof(BiTNode));//创建根节点T->data = PostArray[PostIndex];//找到该节点在中序序列中的位置int index = strchr(InArray,PostArray[PostIndex]) - InArray;//左子树结点个数int LenF = index - InIndex;//创建左子树PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);//右子树结点个数(总结点 - 根节点 - 左子树结点)int LenR = subTreeLen - 1 - LenF;//创建右子树PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);}}/*PostIndex: 后序序列字符串中子树的最后一个节点在PreArray[]中的下标InIndex: 中序序列字符串中子树的第一个节点在InArray[]中的下标subTreeLen: 子树的字符串序列的长度PostArray： 后序序列数组InArray：中序序列数组*/void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){//subTreeLen < 0 子树为空if(subTreeLen <= 0){补充：软件开发 , C++ ,上一个：结构体计算两人生日相差几天
下一个：结构体输出今天是今年的第几天？
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊
