二叉树--结构体

二叉树--结构体

//========================================//
//程序名称：利用结构体建立二叉树          //
//Written By HEWEI                        //
//2011 05 30                              //
//========================================//
#include<iostream>
using namespace std;

#define  MAX 20
//定义存储二叉树节点的结构体
struct tree
{
	int left;
	int Data;
	int right;
};

//自定义结构体类型
//typedef tree treenode;
//treenode b_tree[MAX];
tree b_tree[MAX];
//公共数组
int nodelist[MAX];

//--------------------------------------//
//---------建立二叉树-------------------//
//--------------------------------------//
void Create_Tree(int nIndex)
{
	int i;
	int level;  //树的阶层数
	int Position;//左树为-1，右树为1

	b_tree[1].Data = nodelist[0];
	for(i = 1; i< nIndex; i++)
	{
		//以i为索引，将nodelist[i]中的数据存入二叉树，并找到它的上一级元素，将此索引存入上一级元素的left or right
		b_tree[i +1].Data = nodelist[i];
		level = 1;
		Position = 0;

		while(Position == 0)
		{
			//nodelist[i]应该在那个索引
			if(nodelist[i] >= b_tree[level].Data)  //右树
			{
				//判断是否有子节点
				if(b_tree[level].right != -1)  //有子节点
				    level = 2*level +1;
				else 
					Position = 1;
			}
			else  //左树
			{
				//判断是否有子节点
				if(b_tree[level].left != -1) //有左节点
				    level = 2* level;
				else
					Position = -1;
			}
		}

		if(Position == -1) //左树
			b_tree[level].left = i;
		else
			b_tree[level].right = i;
	}
}

//---------------------------------------//
//-------------存储输入元素--------------//
//---------------------------------------//
void Store_Data(int nIndex)
{
	int temp;
	int i;

	for(i=0; i <nIndex;i++)
	{
		cout << "Please Input the Data => ";
		cin >> temp;
		nodelist[i] = temp;
	}
}
int main(void)
{

	int capacity ; //输入数据的容量  
	//初始化struct为0  
	for(int i = 0; i < MAX; i++)  
	{  
		b_tree[i].left = -1;
		b_tree[i].Data = 0;
		b_tree[i].right = -1;
	}  

	//存储输入的数据  
	cout <<"Please Input the capacity : ";  
	cin >> capacity;  
	cout << endl;  
	Store_Data(capacity);  
	//建立二叉树  
	Create_Tree(capacity);  

	//输出数组和二叉树的元素  
	cout <<"Output the content Data of NodeList : " << endl; 
	for(int i= 0; i <capacity; i++)
	{
		cout << nodelist[i] << " ";
	}
	cout << endl;  
	cout <<"Output the content Data of b_tree : " << endl;  
	cout <<"==============================\n";
	for(int i = 1; i<= MAX; i++)
	{
		cout  << (i-1) << ":  [" << b_tree[i].left<<"]";
		cout <<"  [" << b_tree[i].Data <<"]";
		cout << "  [" << b_tree[i].right <<"]";
		cout << endl;
	}
	return  0;
}