ツリー内の条件を満たすノードを特定します.

f=(最大値+最小値)/2の並べ替えツリーで、f値に最も近い、f値より大きいノードを見つけるアルゴリズムを設計します.複雑度はO(n 2)であれば得点しない.

#include "stdafx.h"
#include<iostream>
#include<queue>
using namespace std;

typedef struct node{
        int data;
        struct node *left;
        struct node *right;
}Node,*Bitree;


void insert(Bitree &T,int ch)//         
{
	if(T == NULL)
	{
		Bitree t = (Bitree)malloc(sizeof(Node));
		t->data = ch;
		t->left = NULL;
		t->right = NULL;
		T = t;
	}else if(ch > T->data)
	{
		insert(T->right,ch);
	}else if(ch < T->data)
	{
		insert(T->left,ch);
	}else{
		cout<<"duplicate value in ordered tree"<<endl;
	}

}


void travel(Bitree T)//       
{
     if(T != NULL)
     {
						
                        travel(T->left);
			cout<<T->data<<" ";
                        travel(T->right);
     }
}
int getMin(Bitree T)
{
	if(!T) return 0;
	Bitree p = T;
	while(p->left)
	{
		p = p->left;
	}
	return p->data;
}

int getMax(Bitree T)
{
	if(!T) return 0;
	Bitree p = T;
	while(p->right)
	{
		p = p->right;
	}
	return p->data;
}
//  ：           mid ，              
//           ，           mid，  
void findMax(Bitree root,int mid,int& value)
{
	if(root == NULL)
		return;
	if(root->data <= mid)//           Mid，         
	{
		findMax(root->right,mid,value);
	}
	//          Mid，         
	//          
	else if(root->data > mid)
	{
		value = root->data;
		findMax(root->left,mid,value);
	}
}
int main()
{
	Bitree root = NULL;
	int ch;
	cin>>ch;
	while(ch != 0)//       
	{
		insert(root,ch);
		cin>>ch;
	}
	travel(root);//       
	cout<<endl;

	int mid = (getMin(root)+getMax(root))/2;//  f = (max+min)/2
	cout<<"mid = "<<mid<<endl;
	int value = 0;//    mid    
	findMax(root,mid,value);
	cout<<value<<endl;
	getchar();
    getchar();
    return 0;
}