问题
解析
（1）检索得到所有的叶子
（2）对每个叶子自底向上检索，每次只向上检索一层
（3）利用队列实现的
（4）对每个结点做标记，利用条件结点不能相邻，作出合理的标记（根据自己需要即可）
（5）根据结点的标记，删除重复的，还有就是在最后节点最大数目确定的情况下，有可能有好几种结点组合，答案不唯一，我只求了其中一种
时间复杂度（n*log n)，n计算的是n个叶子，log n 是树的高度（不考虑单叉树），即每个叶子都要走到树的根。
实验
方便大家查看，我自己把树画出来吧
代码
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define NATURE 0
#define HALF 1
#define OK 2
#define NO -1
#define RESULT 3
const int SIZE = 24 ;
class node
{
public:
int value ;
node * Parent ;
node * Lchild ;
node * Rchild ;
int flag ;
node( )
{
value = NATURE ;
Parent = NULL ;
Lchild = NULL ;
Rchild = NULL ;
flag = 0 ;
};
};
typedef vector<node*> NVector ;
typedef NVector::iterator NIterator;
typedef queue<node*> NQueue;
class tree
{
public:
node * Root ;
tree( void )
{
Root = new node( );
};
void Insert( node * R,int data )
{
if( data > R -> value )
{
if( R -> Rchild == NULL )
{
R -> Rchild = new node() ;
R->Rchild->value = data ;
R->Rchild->Parent =R;
}
else
this->Insert( R->Rchild,data ) ;
}
if( data < R->value )
{
if( R->Lchild == NULL )
{
R -> Lchild = new node( ) ;
R ->Lchild->value = data ;
R->Lchild->Parent = R ;
}
else
this->Insert( R->Lchild,data ) ;
}
};
void Create( node * R,int * data,int size )
{
R->value = *data;
for(int i=1;i<size;i++)
{
this->Insert(R,*(data+i));
}
};
void InorderShow( node * R )
{
if(R->Lchild)
this->InorderShow( R->Lchild );
cout<<R->value<<" ";
if(R->Rchild)
this->InorderShow( R->Rchild );
};
void PreorderShow( node * R )
{
cout<<R->value<<" ";
if(R->Lchild)
this->PreorderShow( R->Lchild );
if(R->Rchild)
this->PreorderShow( R->Rchild );
};
void Findleaf( node * R ,NVector * L )
{
if( this->IsLeaf(R) )
L->insert(L->begin(),R) ;
else
{
if( R->Lchild != NULL )
this->Findleaf(R->Lchild,L) ;
if( R->Rchild != NULL )
this->Findleaf(R->Rchild,L) ;
}
};
bool IsLeaf( node * R)
{
if( R->Lchild==NULL && R->Rchild==NULL )
return true;
else return false ;
};
bool CheckBelongResult(node * p)
{
if(p->Parent&&p->Parent->flag == OK)
return false ;
if(p->Lchild&&p->Lchild->flag == OK)
return false ;
if(p->Rchild&&p->Rchild->flag == OK)
return false ;
return true ;
};
void ShowResult(NVector * L)
{
cout<<"result "<<(L->end()-L->begin())<<endl;
for( NIterator i =L->begin(); i<L->end() ; i++ )
{
cout<<(*i)->value<<endl;
}
};
void VectorSwap( NVector * L ,int a,int b)
{
node * p;
p = *(L->begin()+a);
*(L->begin()+a) = *(L->begin()+b);
*(L->begin()+b)= p;
};
void Buttom_to_up( NVector * L )
{
NQueue * Q = new NQueue();
NVector * Halflist = new NVector();
cout<<" leaf "<<endl;
// put leaves into queue :running time O(n)
for( NIterator i =L->begin(); i<L->end( ) ; i++ )
{
(*i)->flag = OK ;
cout<<(*i)->value<<endl;
Q->push( *i );
}
cout<<"progress"<<endl;
L->clear();
node * p =NULL;
while( ! Q->empty() )
{
cout<<endl;
p =Q->front();
if( p->flag == OK )
{
L->insert(L->begin(),p);
//cout<<p->value<<endl;
}
if( p->flag == HALF )
{
Halflist->insert(Halflist->begin(),p);
//cout<<p->value<<endl;
}
cout<<p->value<<" out"<<endl;
Q->pop();
if( p->Parent != NULL )
{
if(p->Parent->flag== NATURE)
{
Q->push(p->Parent);
cout<<p->Parent->value<<" in"<<endl;
}
if( p->flag == OK )
{
p->Parent->flag = NO ;
}
else
{
switch( p->Parent->flag )
{
case NO:break;
case NATURE:p->Parent->flag = HALF ;break;
case HALF:p->Parent->flag =OK;break;
}
}//else
cout<<p->Parent->value<<" "<<p->Parent->flag<<endl;
}//if
}//while
for( NIterator i = Halflist->begin();i<Halflist->end();i++ )
{
if(this->CheckBelongResult(*i))
{
(*i)->flag = OK ;
L->insert(L->begin(),(*i));
}
else
{
(*i)->flag = NO ;
}
}
for( NIterator i = L->begin(); i<L->end() ; i++ )
{
// delete the duplicate point
if( (*i)->flag != OK )
{
this->VectorSwap( L,L->end()-L->begin()-1,i-L->begin() );
L->pop_back();
}
else
{
(*i)->flag = RESULT ;
}
}
};
void Main( int * data,int size )
{
NVector * L = new NVector ();
//L->resize(size);
// create the tree :running time O(n*log n )
this->Create(Root,data,size);
cout<<"IN ORDER"<<endl;
this->InorderShow(Root);
cout<<endl;
cout<<"PRE ORDER"<<endl;
this->PreorderShow(Root);
cout<<endl;
this->Findleaf(Root,L);
this->Buttom_to_up(L);
this->ShowResult(L);
};
~tree( void ) ;
};
int main()
{
int * data = new int[SIZE];
for( int i =0 ;i<SIZE ;i++ )
{
*(data+i) = rand()%100+4;
}
tree * T = new tree() ;
T->Main(data,SIZE) ;
system("pause") ;
return 0;
}