首页 > 代码库 > PAT-1099(Build A Binary Search Tree)

PAT-1099(Build A Binary Search Tree)

2024-10-18 22:01:01   211人阅读

　　题目见这里

      (分析) 分四步进行：

      1)根据给定的结点情况建二叉树  2)对输入的键值排序(asending) 3)对二叉树中序遍历,同时对应赋key值 4)层次遍历(队列应用)

      题目并不困难,但是我误入了trick,错误假定了结点按先序遍历是按顺序编号的（当然是受样例的影响）,所以有了下面22分(满分30) 的submit(贴出来是因为这不失为好的巩固二叉树知识的程序)

#include <stdio.h> #include <stdlib.h> //qsort,malloc#define N 105typedef 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 = http://www.mamicode.com/key[i++];"%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 105typedef 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 = http://www.mamicode.com/key[j++];" ");		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;}

 

PAT-1099(Build A Binary Search Tree)


联系
我们