アルゴリズム論9.1-1は第二の小さい要素を求めます。

#include <iostream>
#include<time.h>

using namespace std;
//              
struct node
{
	int key;
	node *next;//            
	node *p;  //   
	node *left;　//   
	node *right; //   
	node(int k):key(k),next(NULL),p(NULL),left(NULL),right(NULL){}
};
//     
node* Find_S2(node *head)
{
	node *p, *q, *r, *t;
	//step1：    
	//    ，          ，               
	while(head->next != NULL)
	{
		//        ，head                  
		p = head;head = NULL;
		while(p)
		{
			//p p->next  ，       
			if(p->next != NULL)
			{
				q = p->next;
				r = new node(min(p->key, q->key));
				r->left = p;
				r->right = q;
				p->p = r;
				q->p = r;
				p = q->next;
			}
			//          ，          
			else
			{
				r = new node(p->key);
				r->left = p;
				p->p = r;
				p = p->next;
			}
			//head  　                ，t   head         
			if(head == NULL)
			{
				head = r;
				t =  head;
			}
			else
			{
				t -> next = r;
				t = r;
			}
		}
	}
	return head;
}
int ws_ws(node* head)
{
	//step2：      
	//Min       ，Min2        
	int Min = head->key, Min2 = 0x7fffffff;
	//        
	node* p = head;
	//            
	while(p->left != NULL)
	{
		//            
		if(p->right && p->right->key == Min)
		{
			Min2 = min(Min2, p->left->key);
			p = p->right;
		}
		//            
		else
		{
			//           
			if(p->right)
				Min2 = min(Min2, p->right->key);
			p = p->left;
		}
	}
	return Min2;
}
//  
int main()
{
	int A[8] = {0};
	srand((int)time(0));
	node *head = NULL;
	//  8       
	for(int i = 0; i < 8;i++)
	{
		A[i] = rand() % 100;
		//          
		node *p = new node(A[i]);
		p->next = head;
		head = p;
	}
	for(int i=0;i<8;i++)
		cout<<A[i]<<' ';
	//         
	head=Find_S2(head);
	int ret=ws_ws(head);
	cout<<endl<<ret<<endl;
	return 0;
}