// 二叉树的构造.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include
using namespace std;
struct node
{
char data;
node *lChild;
node *rChild;
};
node* pre_in_Tree (char * pre,char* in,int n)//由先序序列和中序序列来确定二叉树
{
node *s;
s = new node;
char *p;
int k;
if(n <= 0)return NULL;
s->data = https://www.it610.com/article/*pre;
for(p = in;
p < in + n;
p++)//通过for循环在中序序列中找到根结点的位置
{
if(*p == *pre)
{
break;
}
}
k = p - in;
//k就是根结点的位置
s->lChild = pre_in_Tree(pre + 1, in, k);
s->rChild = pre_in_Tree(pre + k + 1, p + 1, n - k - 1);
return s;
}
node* in_post_Tree(char *post,char *in,int n)//通过中序和后序来确定二叉树
{
node *s;
char r,*p;
int k;
if(n <= 0)return NULL;
r = *(post + n - 1);
//根结点的值
s = new node;
s->data = https://www.it610.com/article/r;
for(p = in;
p < in + n;
p++)
{
if(*p == r)
{
break;
}
}
k = p - in;
//根结点的位置
s->lChild = in_post_Tree(post,in,k);
s->rChild = in_post_Tree(post + k, p + 1, n - k - 1);
return s;
}
void display(node *&b)//输出二叉树
{
if(b != NULL)
{
cout<
if(b->lChild != NULL || b->rChild != NULL)
{
cout<<"(";
display(b->lChild);
【二叉树的构造】
if(b->rChild != NULL)cout<<",";
//cout<<",";
display(b->rChild);
cout<<")";
}
}
}
int getLength(char *pre)
{
return strlen(pre);
}
int _tmain(int argc, _TCHAR* argv[])
{
char *pre = "ABDGCEF";
//先序序列
char *in = "DGBAECF";
//中序序列
char *post = "GDBEFCA";
//后序序列
node *p = NULL;
p = in_post_Tree(post,in,strlen(in));
display(p);
return 0;
}
