已知先序与中序遍历结果构建二叉树(C++版)-创新互联
还原思想：
例1：先序序列：ABDGCEF 中序序列：DGBAECF,构造二叉树。
先序序列第一个为A，则根结点第一个为A，然后根据中序序列，DGB在A的左子树，ECF在A的右子树。
先序序列第二个为B（B在A的左子树上），则A左边连B，根据中序序列知道以B为根结点，DG为左子树，右子树空。
先序序列第三个为D(D在B的左子树)，则B左边连D,根据中序序列知道以D为根结点，G为右子树，左子树为空。以此类推……
图解：
这幅图的重点在于找左先序，左中序，右先序，右中序，我看了很多博客，这篇博客的思想较通俗易懂，用来实现代码也是较好理解。
#include#define MaxSize 100
using namespace std;
typedef char ElementType;
typedef struct BiTNode {
ElementType data;
struct BiTNode *lchild,*rchild;
}BinTNode,*BinTree;
BinTree create_BinTree(char a[],char b[],int size) //与该节点相关的先序，与该节点相关的中序,序列中的节点个数大小
{
char c = a[0]; //记录此时根节点
if (c == '\0')
{
return NULL;
}
else
{
int record_index=0;
int count1 = 0, count2 = 0;
char* new_left_PreOrder = (char*)calloc(size, sizeof(char));
char* new_left_InOrder = (char*)calloc(size, sizeof(char));
char* new_right_PreOrder = (char*)calloc(size, sizeof(char));
char* new_right_InOrder = (char*)calloc(size, sizeof(char));
for (int i = 0; i< size; i++) //寻找此时根节点在中序中的位置
{
if (b[i] == c)
{
record_index = i;
}
}
for (int i = 0; i< size; i++) //构建新的左中序，右中序
{
if (i< record_index)
{
new_left_InOrder[count1++] = b[i];
}
if (i >record_index)
{
new_right_InOrder[count2++] = b[i];
}
}
count1 = 0;
count2 = 0;
for (int i = 1; i< size; i++) //构建新的左先序，右先序
{
if (count1< strlen(new_left_InOrder))
{
new_left_PreOrder[count1++] = a[i];
}
else
{
new_right_PreOrder[count2++] = a[i];
}
}
BinTree Node = (BinTree)malloc(sizeof(BinTNode));
Node->data = c;
Node->lchild = create_BinTree(new_left_PreOrder, new_right_InOrder, count1);
Node->rchild = create_BinTree(new_right_PreOrder, new_right_InOrder, count2);
return Node;
}
}
typedef struct {
BinTree Data[MaxSize];
int front, rear;
}Queue;
void InitQueue(Queue& Q)
{
Q.front = Q.rear = 0;
}
bool IsEmpty(Queue& Q)
{
if (Q.rear == Q.front)
{
return true;
}
else
{
return false;
}
}
void EnQueue(Queue& Q, BinTree T)
{
Q.Data[Q.rear] = T;
Q.rear = (Q.rear + 1) % MaxSize;
}
bool DeQueue(Queue& Q, BinTree& p)
{
if (IsEmpty(Q))
{
return false;
}
else
{
printf("%c", Q.Data[Q.front]->data);
p = Q.Data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
}
void LevelOrder(BinTree Tree)
{
Queue Q;
BinTree p = (BinTree)malloc(sizeof(BinTNode));
InitQueue(Q);
EnQueue(Q, Tree);
while (!IsEmpty(Q))
{
DeQueue(Q, p);
if (p->lchild != NULL)
{
EnQueue(Q, p->lchild);
}
if (p->rchild != NULL)
{
EnQueue(Q, p->rchild);
}
}
}
int main()
{
char a[] = "ABDGCEF"; //先序遍历
char b[] = "DGBAECF";//中序遍历
BinTree root = (BinTree)malloc(sizeof(BinTNode));
root=create_BinTree(a, b,strlen(b));
printf("层序遍历的结果是：");
LevelOrder(root);
} 结果如图：
了解构造先序与后序之后的精简代码如下，改变了参数，时间复杂度大大降低，唯一的循环仅在循环中序中发生：
#includeusing namespace std;
typedef char ElementType;
typedef struct BiTNode {
ElementType data;
struct BiTNode *lchild,*rchild;
}BinTNode,*BinTree;
BinTree create_BinTree(ElementType pre[],ElementType In[],int pre_index_start,int pre_index_end,int In_index_start,int In_index_end)
{
if (pre_index_start>pre_index_end)
{
return NULL;
}
else
{
char c = pre[pre_index_start]; //记录此时根节点
int record_index=0;
for (int i = In_index_start; i<= In_index_end; i++) //寻找此时根节点在中序中的位置
{
if (In[i] == c)
{
record_index = i;
}
}
BinTree Node = (BinTree)malloc(sizeof(BinTNode));
Node->data = c;
Node->lchild = create_BinTree(pre,In,pre_index_start+1,pre_index_start+(record_index-In_index_start), In_index_start, record_index - 1);
Node->rchild = create_BinTree(pre,In,(record_index - In_index_start)+1+pre_index_start,pre_index_end,record_index+1,In_index_end);
return Node;
}
}
void PreOrder(BinTree T)
{
if (T != NULL) //如果该节点不为NULL
{
cout<< T->data<< " ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main()
{
char a[] = "ABDGCEF"; //先序遍历
char b[] = "DGBAECF";//中序遍历
BinTree root = (BinTree)malloc(sizeof(BinTNode));
root=create_BinTree(a, b,0,strlen(a)-1,0,strlen(b)-1);
printf("先序遍历的结果是：");
PreOrder(root);
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
新闻名称：已知先序与中序遍历结果构建二叉树(C++版)-创新互联
标题路径：http://6mz.cn/article/dojghp.html