樓主妳好!
這是我的思路:
a,b)說明 根結點<左結點<右結點
c)說明這是壹棵除了最後壹層不滿其余層全滿的完全二叉樹
我覺得a,b的條件可以有很多種解決方法,這裏用最簡單的辦法.就是按每壹層的從小到大排序.
因此,第壹步先將數組排序(快速排序,插入排序.....任何壹種) nlgn內搞定.
第二步,就是完全二叉樹的插入法.完全二叉樹插入法可以用水平遍歷的辦法的擴展,這裏不細說.
第三步,統計葉子節點值和輸出葉子節點值(這個太簡單,只需要輸出left和right都為空的結點即可.)
完整代碼:
排序步驟忽略.
#include<iostream>#include<queue>
using?namespace?std;
struct?node
{
int?value;
node*?left;
node*?right;
node(int?val):value(val),left(NULL),right(NULL){}
};
struct?Tree
{
node*?root;
Tree():root(NULL){}
};
node*?HorizInsert(node*?root,node*?z)
{
if(!root)
{
root=z;
return?root;
}
queue<node*>?q;
q.push(root);
while(!q.empty())
{
node*?Front=q.front();
q.pop();
if(Front->left==NULL)
{
Front->left=z;
return?root;
}
if(Front->right==NULL)
{
Front->right=z;
return?root;
}
if(Front->left)
q.push(Front->left);
if(Front->right)
q.push(Front->right);
}
return?root;
}
void?HorizPrint(node*?root)
{
if(!root)?return?;
queue<node*>?q;
q.push(root);
int?calc=0;
cout<<"The?Leaves:";
while(!q.empty())
{
node*?Front=q.front();
q.pop();
if(!Front->left?&&?!Front->right)
{
++calc;
cout<<Front->value<<'?';
}
if(Front->left)
q.push(Front->left);
if(Front->right)
q.push(Front->right);
}
cout<<endl<<"Ther?number?of?leaves:?"<<calc<<endl;
}
void?main()
{
int?Array[]={1,2,3,4,5,6,7,8,9,10,11};
int?len=sizeof(Array)/sizeof(Array[0]);
Tree*?T=new?Tree;
for(int?i=0;i<len;++i)
T->root=HorizInsert(T->root,new?node(Array[i]));
HorizPrint(T->root);
}