序列中查找第二小元素

#include <stdio.h>
#include <stdlib.h>


typedef struct node {
	struct node *left;
	struct node *right;
	struct node *next;
	struct node *parent;
	int key;
}node;

int find(node *head)
{
	node **curr,*ptr,*q,*t;
	
	//一层只有一个元素时表示root
	while(head->next) {
		
		//q指向每一层第一个节点
		//ptr移动地指向每两两节点的第一个
		q=ptr=head;
		curr=&t;
		while(ptr) {
			(*curr)=(node *)malloc(sizeof(*q));
			(*curr)->next=NULL;
			//数组为奇数个
			if(ptr->next==NULL) {
				(*curr)->key=ptr->key;
				(*curr)->left=(*curr)->right=ptr;
				ptr->parent=*curr;
				break;
			}
			else {
				int fir=ptr->key;
				int sec=ptr->next->key;
				(*curr)->key=(fir>sec?sec:fir);
				(*curr)->left=ptr;
				(*curr)->right=ptr->next;
				ptr->parent=ptr->next->parent=*curr;
			}
			curr=&((*curr)->next);
			ptr=ptr->next->next;
		}
		//向上移动一层
		head=q->parent;
	}

	int min=head->key,min2=0x7fffffff;
	//从根节点往下找，从最小值的那个分支找次小值
	while(head->left) {
		int lval=head->left->key;
		int rval=head->right->key;
		if(lval==min) {
			min2=rval>min2?min2:rval;
			head=head->left;
		}else {
			min2=lval>min2?min2:lval;
			head=head->right;
		}
	}
	return min2;
}


int main()
{
	int a[7]={3,1,7,5,9,0,6};
	//双重指针用来存放新分配节点的地址
	//这样就不用再判断是不是首节点了
	node *curr,**ptr=&curr;
	
	for(int i=0;i<7;i++) {
		*ptr=(node *)malloc(sizeof(*curr));
		(*ptr)->left=(*ptr)->right=(*ptr)->parent=NULL;
		(*ptr)->key=a[i];
		ptr=&((*ptr)->next);
	}
	*ptr=NULL;

	printf("%d\n",find(curr));
	//没有释放内存
}