参考:
如先序为:abdc,中序为:bdac .
则程序可以求出后序为:dbca 。此种题型也为数据结构常考题型。
算法思想:先序遍历树的规则为中左右,则说明第一个元素必为树的根节点,比如上例
中的a就为根节点,由于中序遍历为:左中右,再根据根节点a,我们就可以知道,左子树包含
元素为:db,右子树包含元素:c,再把后序进行分解为db和c(根被消去了),然后递归的
进行左子树的求解(左子树的中序为:db,后序为:db),递归的进行右子树的求解(即右
子树的中序为:c,后序为:c)。如此递归到没有左右子树为止。
关于“已知先序和后序求中序”的思考:该问题不可解,因为对于先序和后序不能唯一的确定
中序,比如先序为 ab,后序为ba,我只能知道根节点为a,而并不能知道b是左子树还是右子树,
#include <stdio.h>
typedef struct _Node{
char data;
struct _Node *lchild;
struct _Node *rchild;
} Node;
Node * CreateTree()
{ /* 生成二叉树的普通方法
* 按先序次序输入二叉树中结点的值
* 构造二叉链表表示的二叉树T。输入空格表示空子树。 */
char ch;
scanf("%c",&ch);
Node *T;
if(ch==' ') /* 空 */
return NULL;
else
{
T=(Node *)malloc(sizeof(Node));
if(!T)
exit(0);
T->data=ch; /* 生成根结点 */
T->lchild = CreateTree(); /* 构造左子树 */
T->rchild = CreateTree(); /* 构造右子树 */
}
return T;
}
/* 由先根序列和中根序列生成二叉树
* 递归法。pre 是先跟序列,in是中根序列
* pre_s是先根序列的起始,pre_e是先跟序列的结束
* in_s是中根序列的起始,in_e是中根序列的结束
*/
Node *Convert(char pre[], int pre_s, int pre_e,
char in [], int in_s , int in_e )
{
if(in_s > in_e)return NULL;
int i = in_s;
for(i=in_s;i<in_e&&in[i]!=pre[pre_s];i++);
Node *p = (Node *)malloc(sizeof(Node));
p->data = pre[pre_s];
p->lchild = Convert(pre, pre_s+1, pre_s+i-in_s,
in, in_s,i-1);
p->rchild = Convert(pre, pre_s+i-in_s+1,pre_e,
in, i+1,in_e);
return p;
}
void PreTranverse(Node *head)
{
if(!head)return ;
printf("%c\t",head->data);
PreTranverse(head->lchild);
PreTranverse(head->rchild);
return;
}
void InTranverse(Node *head)
{
if(!head)return ;
PreTranverse(head->lchild);
printf("%c\t",head->data);
PreTranverse(head->rchild);
return;
}
void BackTranverse(Node *head)
{
if(!head)return;
BackTranverse(head->lchild);
BackTranverse(head->rchild);
printf("%c\t",head->data);
return;
}
int main(int argc, char *argv[])
{
char pre[]="abdc";
char in[]="bdac";
Node *head = NULL;
head = Convert(pre,0,strlen(pre)-1,
in ,0,strlen(in)-1);
InTranverse(head);
printf("\n");
getch();
}
由此可见该问题不可解。当然也可以构造符合中序要求的所有序列。
分享到:
相关推荐
根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
C语言,数据结构课程,知道中序和后序遍历,画二叉树和写出前序遍历。
二叉树已知前序和中序遍历,求后序遍历,C++代码已编译通过,可直接运行
C++数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历.pdf
如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
数据结构 C/C++ 数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历
二叉搜索树(排序二叉树),树的遍历(前序、中序、后序)【数据结构和算法入门7】
C++源码,可在VC6.0环境下直接运行,核心代码非常经典,不到10行且易懂。
自己写的递归三种遍历,利用栈的非递归三种遍历。
二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。 比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先...
本篇文章是对用C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)的方法进行了详细的分析介绍,需要的朋友参考下
1.已知一棵二叉树的中序遍历结点排列为DGBAECHIF,后序遍历结点排列为GDBEIHFCA,(也可以换成已知 中序和先序遍历的内容) (1)试画出该二叉树; (2)试写出先序遍历排列;(写出没有给出的那种遍历序列) (3)...
在完全二叉树中,在层次遍历和先根序遍历中,已知某节点在一种遍历中的编号,求该节点在另一种遍历中的编号。 程序描述: q = 1表示已知某节点在先根序遍历中的编号,求的是它在层次遍历中的编号。 q = 2表示已知的...
已知二叉树先序和中序遍历,要求二叉树的顺序,本方法使用c语言编写