递归--二叉树

递归--二叉树

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

#define  MAX 20
//链表结构的声明
struct tree
{
	struct tree *left;
	int Data;
	struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;

int capacity;
//---------------------------------------//
//---------建立二叉树--------------------//
//---------------------------------------//
b_tree Create_Tree(int *nodelist,int position)
{
	b_tree New;  //建立新的节点

	//递归的条件 
    if(position > capacity -1 )
		return NULL;
	else
	{
		//申请内存空间
		New = new treenode[sizeof(treenode)];
      //存入节点值
		New->Data = nodelist[position];
		New->left = Create_Tree(nodelist,2*position); //左树节点
		New->right = Create_Tree(nodelist,2*position + 1); //右树节点
        return New;
	}
}

//-------------------------------------------//
//--------前序遍历二叉树---------------------//
//-------------------------------------------//
void preorder(b_tree pointer)
{
	if(pointer != NULL)  
	{  
		cout <<pointer->Data << " ";  
		preorder(pointer->left);//打印左节点  
		preorder(pointer->right);//打印右节点  
	} 
}

//-------------------------------------------//  
//-----------存储数值------------------------//  
//-------------------------------------------//  
void Store_Data(int nMaxIndex,int *pArray)  
{  
	int i ;  
	int temp;  
	for(i = 0; i <nMaxIndex; i++)  
	{  
		cout << "Please Input the Data => ";  
		cin >> temp;  
		pArray[i] = temp;  
	}  
}  

//-------------------------------------------//
//------------主函数-------------------------//
//-------------------------------------------//
int main(void)
{
	b_tree root = NULL; //声明根节点  
	int i,index;  
	int value;  
	int nodelist[MAX];  

	//读取数值到数组中  
	cout <<"Please Input the capacity : ";  
	cin >> capacity;  
	cout << endl;  
	Store_Data(capacity,nodelist);  
	//建立二叉树  
	root = Create_Tree(nodelist,1);  
	//遍历二叉树  
	preorder(root);  
	return 0;
}