由中序遍历和层次遍历还原二叉树。C语言实现
题目链接：http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10609
如果有兴趣帮我的代码找错当然感激不尽，没兴趣就贴出自己的想法和代码。
由于字数限制，只贴出我的还原函数。
void BuildTree(char *level,char *inorder,pBiTree T)
{
int i;
int len=strlen(level); //取得层次遍历长度
int pos=0;
if(len==0)
return ;
char *p=strchr(inorder,level[0]);
if(p==NULL) //如果为空则抛弃第一个，跳到下一个；
{
char *L=(char*)malloc(sizeof(char)*len); //开辟数组
strncpy(L,level+1,len-1); //舍弃第一个
L[len-1]=0;
BuildTree(L,inorder,T); //调用建树函数
return ;
}
pos=p-inorder; //得到中序遍历左子树字符串长度
T->data=level[0]; //为根节点赋值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0) //左子树的递归调用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
char *left_level=(char*)malloc(sizeof(char)*len);
char *left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1); //舍去层次遍历第一个
strncpy(left_inor,inorder,pos); //截取左子树字符串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T->lchild);
}
if(*(p+1)>='A'&&*(p+1)<='Z') //右子树的递归调用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
char *right_level=(char*)malloc(sizeof(char)*(len));
char *right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T->rchild);
}
}
经测，该代码已经修改正确，只需在void BuildTree(char *level,char *inorder,pBiTree T)这里的最后一个变量T改为引用即可。还有一个地方判断调用右子树的地方的判断条件。
#include <stdlib.h>
#include <string.h>
typedef struct _BiTree
{
char data;
struct _BiTree *lchild;
struct _BiTree *rchild;
}BiNode, *pBiTree;
void BuildTree(char *level,char *inorder,pBiTree &T)
{
int i;
int len=strlen(level); //取得层次遍历长度
int pos=0;
if(len==0)
return ;
char *p=strchr(inorder,level[0]);
if(p==NULL) //如果为空则抛弃第一个，跳到下一个；
{
char *L=(char*)malloc(sizeof(char)*len); //开辟数组
strncpy(L,level+1,len-1); //舍弃第一个
L[len-1]=0;
BuildTree(L,inorder,T); //调用建树函数
return ;
}
pos=p-inorder; //得到中序遍历左子树字符串长度
T->data=level[0]; //为根节点赋值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0) //左子树的递归调用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
char *left_level=(char*)malloc(sizeof(char)*len);
char *left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1); //舍去层次遍历第一个
strncpy(left_inor,inorder,pos); //截取左子树字符串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T->lchild);
}
if(pos < strlen(inorder)-1) //右子树的递归调用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
char *right_level=(char*)malloc(sizeof(char)*(len));
char *right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T->rchild);
}
}
void priOrder(pBiTree T)
{
if (T != NULL){
printf ("%c", T->data);
priOrder(T->lchild);
priOrder(T->rchild);
}
}
void postOrder(pBiTree T)
{
if (T != NULL){
postOrder(T->lchild);
postOrder(T->rchild);
printf ("%c", T->data);
}
}
void freeNode(pBiTree &T)
{
if (T != NULL){
freeNode(T->lchild);
freeNode(T->rchild);
free(T);
}
}
int main()
{
pBiTree root;
char level[28], inorder[28];
int n;
scanf ("%d", &n);
//fflush(stdin);
getchar();
while (n --){
scanf ("%s%s", level, inorder);
root = (pBiTree)malloc(sizeof(BiNode));
BuildTree(level, inorder, root);
priOrder(root);
printf ("\n");
postOrder(root);
printf ("\n");
//freeNode(root);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<sys/types.h>
typedef int data_t;
typedef struct node
{
data_t data;
struct node *lchild, *rchild;
}btree;
btree *create_btree(void);
void preorder_btree(btree *bt);
void inorder_btree(btree *bt);
void postorder_btree(btree *bt);
int depth_btree(btree *bt);
void free_btree(btree **bt);
void exchange_btree(btree *bt);
void print_btree(btree *bt); //先序遍历的非递归算法
int main(int argc, const char *argv[])
{
btree *bt = create_btree();
preorder_btree(bt);
printf("\n");
printf("depth=%d\n", depth_btree(bt));
exchange_btree(bt);
preorder_btree(bt);
printf("\n");
print_btree(bt);
printf("\n");
free_btree(&bt);
preorder_btree(bt);
printf("\n");
return 0;
}
btree *create_btree(void)
{
int n;
scanf("%d", &n);
if (n == 0)
{
return NULL;
}
btree *bt = (btree*)malloc(sizeof(btree));
bt->data = n;
bt->lchild = create_btree();
bt->rchild = create_btree();
return bt;
}
void preorder_btree(btree *bt)
{
if (bt)
{
printf("%d,", bt->data);
preorder_btree(bt->lchild);
preorder_btree(bt->rchild);
}
}
void inorder_btree(btree *bt)
{
if (bt)
{
inorder_btree(bt->lchild);
printf("%d,", bt->data);
inorder_btree(bt->rchild);
}
}
void postorder_btree(btree *bt)
{
if (bt)
{
postorder_btree(bt->lchild);
postorder_btree(bt->rchild);
printf("%d,", bt->data);
}
}
int depth_btree(btree *bt)
{
if (!bt)
{
return 0;
}
int ldepth = depth_btree(bt->lchild);
int rdepth = depth_btree(bt->rchild);
return ldepth > rdepth ? ldepth+1 : rdepth+1;
}
void free_btree(btree **bt)
{
if (*bt)
{
free_btree(&(*bt)->lchild);
free_btree(&(*bt)->rchild);
free(*bt);
*bt = NULL;
}
}
void exchange_btree(btree *bt)
{
if (bt)
{
exchange_btree(bt->lchild);
exchange_btree(bt->rchild);
btree *tmp = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = tmp;
}
}
void print_btree(btree *bt) //先序遍历的非递归算法
{
//创建一个栈
btree *stack[20];
int top = 0;
if (bt) //根不空，根入栈
{
stack[top] = bt;
top++;
}
while(top) //当栈不空
{
top--;
btree *tmp = stack[top];//出栈，访问
printf("%d,", tmp->data);
if (tmp->rchild) //右子树不空，右子树入栈
{
stack[top] = tmp->rchild;
top++;
}
if (tmp->lchild) //左子树不空，左子树入栈
{
stack[top] = tmp->lchild;
top++;
}
}
}
//
对于层次遍历的实现是用队列，根节点入队列然后根节点出队列的同时左节点右节点入队列，这样依次，出一次队列对应出队列的节点左右节点如队列，没有就不入。