根据二叉树的前序和中序序列来恢复二叉树

来源：百度知道编辑：UC知道时间：2024/05/14 01:32:15

我写的算法的思想是：例如前序序列abcdefg

中序序列bcadegf

前序序列的第一个元素就是树的根节点，在中序序列中找到这个根节点，在中须序列中根节点左边元素的就是根节点的左子树，根节点右边的元素就是根节点的右子树，然后在前序序列中，找到根节点的左子树中最先访问的节点（即前序序列中下标最小的），该节点就是左子树的根节点。然后就是递归调用……

按道理说算法的思路应该是没有什么问题的，但是我写的算法并不能恢复正确的二叉树，到底是什么问题呢？期待高手~~

#include "stdafx.h"
#include<malloc.h>
typedef struct node
{
char data;
struct node *left;
struct node *right;

}*TreeNode,TNode;

//其中a[] ,b[]分别表示是前序和中序序列 ,i表示是子树序列的起点下标,n表示是子树的终点下标+1,k如果是1表示是给左子树，为2是给右子树，T是根节点，total表示是原始的数列的长度。

void rebuild(char a[],char b[],int i, int n,int k,TreeNode &T,int total)
{
int num,min;
TreeNode node;
if(T==NULL)//根节点
{
node=(TreeNode)malloc(sizeof(TNode));
node->data=a[0];
T=node;
for(;i<n;i++)
{
if(a[0]==b[i])//在中序序列中找根节点下标
break;
}
}
else
{
if(n==i)//如果数列的长度小于1
{
if(k==1)//k

#include <iostream>
#include <queue>

using namespace std;

struct BiNode
{
char data;
BiNode *lchild, *rchild;
};
typedef BiNode *BiTree;

int CreateBiTree(BiTree &T, const char *s1, const char *s2, int len)
{
if (len<=0)
{
T = NULL;
return 1;
}
else
{
T = new BiNode;
T->data = *s1;
int i;
for ( i=0; i<len; i++) if (s2[i]==*s1) break;
CreateBiTree(T->lchild, s1+1, s2, i);
CreateBiTree(T->rchild, s1+i+1, s2+i+1, len-(i+1));
}
return 1;
}

int DestroyBiTree(BiTree &T)
{
if (T==NULL) return 1;
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
delete T;
T = NULL;
return 1;
}

int ATraverse(BiTree &T)
{
if (T==NULL) return 1;
ATraverse(T->lchild

根据二叉树的前序和中序序列来恢复二叉树已知二叉树T中结点的前序和中序遍历序列建立一棵二叉树设计一个程序,根据二叉树的先根序列和对称序序列创建一棵用左、右指针表示的二叉树. 由二叉树的后序序列和中序序列可唯一确定一棵二叉树，试构造相应的二叉树。各位前辈们如果给定结点的前序序列和后序序列能否确定一棵二叉树已知二叉树后序遍历序列是dabec，中序遍历序列debac，它的前序遍历的序列是怎样根据前序列和中序序列得出后序序列求教由二叉树的前序遍历序列建立二叉树的非递归算法已知二叉树的后序遍历序列dabec,中序遍历序列是debac,它的前序遍历序列是什么已知一棵二叉树的先序遍历序列和中序遍历序列，编写一个程序唯一确定一棵二叉树