Day 66 二叉树 排序

#include
#include
#include
#define Ele int 
#define NODENUM 7
 
typedef Ele bitree[NODENUM];
 
void initbitree(bitree T){
	Ele node;
	int i=0;
	printf("按照层次从左往右输入树中节点的值，0表示空节点，#表示输入结束：\n");
	while(scanf("%d",&node)){
		T[i]=node;
		i++;
		if(i==NODENUM){
			break;
		}
	}
}
 
Ele parent(bitree T,Ele e){
	int i;
	if(T[0]==0){
		printf("存储的是一个空树。\n");
	}else{
		if(T[0]==e){
			printf("当前节点是根节点，没有双亲节点。\n");
			return 0;
		}
		for(i=1;i
			if(T[i]==e){
				return T[(i+1)/2-1];
			}
		}
		printf("二叉树中没有指定节点。\n");
	}
	return -1;
}
 
Ele leftchild(bitree T,Ele e){
	int i;
	if(T[0]==0){
		printf("存储的是一颗空树。\n");
	}else{
		for(i=1;i
			if(T[i==e]){
				if(((i+1)*21)*2-1]!=0)){
					return T[(i+1)*2-1];
				}else{
					printf("当前节点没有左孩子。\n");
					return 0;
				}
			}
		}
		printf("二叉树中没有指定节点。\n");
	}
	return -1;
}
 
Ele rightchild(bitree T,Ele e){
	int i;
	if(T[0]==0){
		printf("存储的是一颗空树。\n");
	}else{
		for(i=1;i
			if(T[i]==e){
				if(((i+1)*2+11)*2]!=0)){
					return T[(i+1)*2];
				}else{
					printf("当前节点没有右孩子。\n");
					return 0;
				}
			}
		}
		printf("二叉树中没有指定的节点。\n");
	}
	return -1;
}
 
int main(){
	int res;
	bitree T={0};
	initbitree(T);
	res=parent(T,3);
	if(res!=0 && res!=-1){
		printf("节点3的双亲节点的值为：%d\n",res);
	}
	res=leftchild(T,2);
	if(res!=0 && res!=-1){
		printf("节点2的左孩子的值为：%d\n",res);
	}
	res=rightchild(T,2);
	if(res!=0 && res!=-1){
		printf("节点2的右孩子的值为：%d\n",res);
	}
	return 0;
}
 
 

结果如下：

二叉树的链式存储：

#include
#include
#define Ele int
 
typedef struct bitnode{
	Ele data;
	struct bitnode *lchild;
	struct bitnode *rchild;
}Bnode,*Btree;
 
void creatbitree(Btree *T){
	*T=(Bnode *)malloc(sizeof(Bnode));
	(*T)->data=1;
	(*T)->lchild=(Bnode *)malloc(sizeof(Bnode));
	(*T)->lchild->data=2;
	(*T)->rchild=(Bnode *)malloc(sizeof(Bnode));
	(*T)->rchild->data=3;
	(*T)->rchild->lchild=NULL;
	(*T)->rchild->rchild=NULL;
	(*T)->lchild->lchild=(Bnode *)malloc(sizeof(Bnode));
	(*T)->lchild->lchild->data=4;
	(*T)->lchild->rchild=NULL;
	(*T)->lchild->lchild->lchild=NULL;
	(*T)->lchild->lchild->rchild=NULL;
}
 
void destorybitree(Btree T){
	if(T){
		destorybitree(T->lchild);
		destorybitree(T->rchild);
		free(T);
	}
}
 
int main(){
	Btree tree;
	creatbitree(&tree);
	printf("根节点的左孩子节点为：%d\n",tree->lchild->data);
	printf("根节点的右孩子节点为：%d\n",tree->rchild->data);
	destorybitree(tree);
	return 0;
}

#include
#include
 
void px(int fs[],int n){
	int s,m,min,temp;
	for(s=0;s
		min=s;
		for(m=s+1;m
			if(fs[min]>fs[m]){
				min=m;
			}
		}
		if(min!=s){
			temp=fs[min];
			fs[min]=fs[s];
			fs[s]=temp;
		}
	}
}
 
int main(){
	int fs[6]={89,52,36,74,52,75};
	px(fs,6);
	for(int s=0;s<6;s++){
		printf("%d ",fs[s]);
	}
	printf("\n");
	return 0;
}

#include 
#include 
#include 
#include 
#include 
#define SIZE 5
long get_sys_time(void)
{
struct timeb tb;
ftime(&tb);
return tb.time*1000+tb.millitm;
}
void print(int arr[],int n)
{
for(int i=0;i
{
printf("%d ",arr[i]);
}
printf("\n");
}
void insert_sort(int arr[], int n)
{
for(int i=1;i
{
if(arr[i]-1])
{
int temp=arr[i];
int j;
for(j=i-1; j>=0;j--)
{
if(temp
{
arr[j+1]=arr[j];
}
else
{
break；
}
}
arr[j+1]=temp;
}
}
}
int main()
{
int arr[SIZE]={0};
srand((unsigned int)time(NULL));
for(int i=0;i
{
arr[i]= rand()%1000+1;
}
print(arr,SIZE);
long t_start=get_sys_time();
insert_sort(arr,SIZE);
long t_end=get_sys_time();
printf("\n 运行时间:%ld\n",t_end-t_start);
print(arr,SIZE);
return 0;
}

#include
#include
 
void px(int fs[],int start,int end){
	int i=start;
	int j=end;
	int temp=fs[start];
	if(i
		while(i
			while(i=temp){
			j--;
			}
			if(i
				fs[i]=fs[j];
				i++;
			}
			while(i
				i++;
			}
			if(i
				fs[j]=fs[i];
				j--;
			}
		}
		fs[i]=temp;
		px(fs,start,i-1);
		px(fs,i+1,end);
	}
}
 
int main(){
	int fs[6]={56,89,21,58,33,45};
	int s;
	px(fs,0,5);
	for(s=0;s<6;s++){
		printf("%d ",fs[s]);	
	}
	printf("\n");
	return 0;
}