Question

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

已知一个整形数组，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);
}