关于二叉树的一道C编程题，请各位高手帮忙写个完整代码。

Question

已知一个整形数组，int array[100] = {12,34,21,......,799,324,45}；
请以上面给出的数组数据创建一个二叉树。要求：
a）每个节点的值都小于其子节点；
b）每个节点的左子结点的值小于右子结点；
3）树的高度尽可能小；
请输出数组高度并输出树的层次结构
请输出所有叶子节点的值并统计叶子节点的个数

请各位高手帮忙，给出个完整的正确代码，谢谢

Answer 1

楼主你好!

这是我的思路:

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);
}