利用二叉链表构造二叉树的每一个结点
typedef struct TNode
{
char data;
struct TNode *lchild,*rchild;
}*Tree;
先序遍历顺序建立二叉链表
#include<stdio.h>
#include<stdlib.h>
typedef struct TNode
{
char data;
struct TNode *lchild,*rchild;
}TNode,*Tree;
void Create(TNode *T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
*T=NULL;
else
{
T=(TNode *)malloc(sizeof(TNode));
if(!*T)
exit(-1);
T->data=ch;
Create(T->lchild);
Create(T->rchild);
}
}
int main()
{
TNode *T;
printf("输入树(#代表空节点):");
Create(T);
//我是省略号//
}
遍历二叉树
//二叉树的先序遍历//
void travel_pre(TNode T)
{
if(T==NULL)
return ;
printf("%c ",T->data);
travel_pre(T->lchild);
travel_pre(T->rchild);
}
//二叉树的中序遍历//
void travel_in(TNode T)
{
if(T==NULL)
return ;
travel_in(T->lchild);
printf("%C ",T->data);
travel_in(T->rchild);
}
//二叉树的后序遍历//
void travel_post(TNode T)
{
if(T==NULL)
return;
travel_post(T->lchild);
travel_post(T->rchild);
printf("%c ",T->data);
}
先序+中序构造二叉树
根据先序和中序遍历结果还原二叉树基础理论比较好理解,多做几道这些类似的题,也能孰能生巧。关键之处,还是在于代码实现。
这是一道OJ题,请移步HDU1710
因为还原二叉树是一个递归的问题,将复杂地问题简化为一个个小问题,所以就拿三个结点的二叉树举栗。
先序:ABC;
中序:BAC;
我们都知道先序遍历是根左右,而中序遍历是左根右,我们可以通过先序找到根节点,根据中序中根节点的位置,就可以找到根节点的左子树(左孩子),和右子树(右孩子);根据这个规则就可以还原一颗二叉树了。
例如下面的例子。
不难发现根节点是A,那么中序中的1~k就为左子树,k~尾就为右子树。同理,先序中pre+1~pre+k为左子树,pre+k+1~尾为右子树。其他以此类推。
#include<stdlib.h>
#include<stdio.h>
struct TNode
{
int data;
TNode * lchild,* rchild;
}*Tree;
int a[1000],b[1000];
int n;
//代码的核心之处//
TNode * Creat(int *a,int *b,int n)
{
TNode * T;
for(int i =0;i < n ; ++i)
{
if(a[0]==b[i])
{
T = (TNode *)malloc(sizeof(TNode));
T->data = b[i];
T->lchild = Creat(a+1,b,i);
T->rchild = Creat(a+i+1,b+i+1,n-i-1);
return T;
}
}
return NULL;
}
//后序遍历二叉树
void travel_post(TNode *R)
{
if(R!=NULL)
{
travel_post(R->lchild);
travel_post(R->rchild);
if(R==Tree)
{
printf("%dn",R->data);
}
else{
printf("%d ",R->data);
}
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
Tree = NULL;
//先序
for(int i =0;i<n;++i)
{
scanf("%d",&a[i]);
}
//中序
for(int i =0;i<n;++i)
{
scanf("%d",&b[i]);
}
Tree = Creat(a,b,n);
travel_post(Tree);
}
return 0;
}
中序+后序构造二叉树
中序+后序构造二叉树和先序+中序构造二叉树类似,关键之处在于,找到每个二叉结点的根,左孩子,右孩子的位置,然后递归就可以了。
#include<stdio.h>
#include<stdlib.h>
struct TNode
{
int data;
TNode *lchild,*rchild;
}*Tree;
int a[1000],b[1000];
int n;
//核心区
TNode * Creat(int *a,int *b,int n)
{
TNode * T;
T = (TNode *)malloc(sizeof(TNode));
if(n<=0)
return NULL;
else
{
T->data = b[n-1];
int * p;
for(p = a;p<a+n;p++)
{
if(*p==b[n-1])
break;
}
int t = p-a;
T->lchild = Creat(a,b,t);
T->rchild = Creat(a+t+1,b+t,n-t-1);
return T;
}
}
//先序遍历
void travel_pre(TNode * R)
{
if(R!=NULL)
{
if(R==Tree)
printf("%d",R->data);
else
printf(" %d",R->data);
travel_pre(R->lchild);
travel_pre(R->rchild);
}
}
int main()
{
while(~scanf("%d",&n))
{
Tree =NULL;
for(int i =0;i<n;++i)
{
scanf("%d",&a[i]);
}
for(int i =0;i<n;++i)
{
scanf("%d",&b[i]);
}
Tree = Creat(a,b,n);
travel_pre(Tree);
printf("n");
}
return 0;
}
近期评论