题目见这里
(分析) 分四步进行：
1)根据给定的结点情况建二叉树 2)对输入的键值排序(asending) 3)对二叉树中序遍历,同时对应赋key值 4)层次遍历(队列应用)
题目并不困难,但是我误入了trick,错误假定了结点按先序遍历是按顺序编号的（当然是受样例的影响）,所以有了下面22分(满分30) 的submit(贴出来是因为这不失为好的巩固二叉树知识的程序)
#include <stdio.h>
#include <stdlib.h> //qsort,malloc
#define N 105
typedef struct node{
int data;
struct node *lChild,*rChild;
}BiNode,*BiTree;
void CreatBiTree(BiTree *bt){
(*bt) = (BiTree)malloc(sizeof(BiNode));
(*bt)->lChild = (*bt)->rChild = NULL;
int left,right;
scanf("%d%d",&left,&right);
if(left!=-1) CreatBiTree(&((*bt)->lChild));
if(right!=-1) CreatBiTree(&((*bt)->rChild));
}
int cmp(const void *a, const void *b){ //asending
return *(int *)a - *(int *)b;
}
void Sort(int *key, int n){
int i;
for(i=0;i<n;i++)
scanf("%d",&key[i]);
qsort((void*)key,n,sizeof(key[0]),cmp);
}
void LDR(BiTree bt, int key[]){
static int i = 0;
if(bt){
LDR(bt->lChild,key);
bt->data = key[i++];
LDR(bt->rChild,key);
}
}
void LOT(BiTree bt){
BiTree q[N],bNode;
int front,rear,flag;
rear = front = flag = 0;
q[rear] = bt;
while(front<=rear){
bNode = q[front++];
if(!flag){
printf("%d",bNode->data);
flag = 1;
}
else printf(" %d",bNode->data);
if(bNode->lChild) q[++rear] = bNode->lChild;
if(bNode->rChild) q[++rear] = bNode->rChild;
}
printf("n");
}
void DestryBiTree(BiTree *bt){
if(*bt){
DestryBiTree(&((*bt)->lChild));
DestryBiTree(&((*bt)->rChild));
free(*bt);
}
}
int main(){
int key[N];
BiTree bt;
int n;
// freopen("Data.txt","r",stdin);
scanf("%d",&n);
CreatBiTree(&bt,n);
Sort(key,n);
LDR(bt,key); //中序遍历
LOT(bt); //层次遍历
DestryBiTree(&bt);
return 0;
}
当然,既然认识到这个错误,当然是因为找到了反例：
8
7 1
2 3
-1 -1
-1 4
5 6
-1 -1
-1 -1
-1 -1
33 37 34 30 50 43 37 33
从上面的反例中,我们注意到创建链表形式的二叉树是不太可能的,而应采用数组形式，所以有了AC的提交：
#include <stdio.h>
#define N 105
typedef struct{
int lChild,rChild;
int data;
}Node;
void CreatBiTree(Node node[], int n){
int i = 0;
for(;i<n;i++) scanf("%d%d",&node[i].lChild,&node[i].rChild);
}
int cmp(const void *a, const void *b){ //asending
return *(int *)a - *(int *)b;
}
void Sort(int *key, int n){
int i;
for(i=0;i<n;i++)
scanf("%d",&key[i]);
qsort((void*)key,n,sizeof(key[0]),cmp);
}
void LDR(Node *node, int key[], int i){
static int j = 0;
if(node[i].lChild!=-1) LDR(node,key,node[i].lChild);
node[i].data = key[j++];
if(node[i].rChild!=-1) LDR(node,key,node[i].rChild);//注意不要写误
}
void LOT(Node node[]){
Node q[N],qNode;
int front,rear;
rear = front = 0;
q[rear] = node[0];
while(front<=rear){
qNode = q[front++];
if(rear) printf(" ");
printf("%d",qNode.data);
if(qNode.lChild!=-1) q[++rear] = node[qNode.lChild];
if(qNode.rChild!=-1) q[++rear] = node[qNode.rChild];
}
printf("n");
}
int main(){
int key[N];
Node node[N];
int n;
// freopen("Data.txt","r",stdin);
scanf("%d",&n);
CreatBiTree(node,n);
Sort(key,n);
LDR(node,key,0); //中序遍历
LOT(node); //层次遍历
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
