链表-二叉树

链表-二叉树

//========================================//
//程序名称：利用链表建立二叉树            //
//Writtrn 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;

//-----------------------------------------//
//-----------二叉树节点的插入--------------//
//-----------------------------------------//
b_tree Insert_Tree(b_tree root,int data)
{
	 b_tree New;
	 //b_tree Pointer;//节点指针
	 b_tree currentnode;  //当前节点
	 //b_tree parentnode;  //父节点

	 //allocate memory to New
	 New = new treenode[sizeof(treenode)];
	//初始化新的节点
	 New->left = NULL;
	 New->Data = data;
	 New->right = NULL;

    //按照树的结构，左小右大
	//建立根节点
    if(root == NULL)
	{
     root = New;
	}
	else
	{
		//判断此值和root值得大小，左子树和右子树
        currentnode = root ;//当前节点
		while(currentnode != NULL)
		{
			//寻找左子树
			if (data <= currentnode->Data)
			{
                //判断是否有子节点
				if(currentnode->left != NULL)//有子节点
				{
					currentnode = currentnode->left;  //将当前节点向下移动
				}
				else                          //无子节点 
				{//赋值给当前节点
					//parentnode = currentnode;
				    //currentnode = currentnode->left;
                                      break;
				}
			}
			else//右子树
			{
				//寻找右子树
					//判断是否有子节点
					if(currentnode->right != NULL)//有子节点
					{
						//parentnode = currentnode;
						currentnode = currentnode->right;  //将当前节点向下移动
					}
					else                          //无子节点 
					{
						//parentnode = currentnode;
						//parentnode->right = New;    //赋值给当前节点
						//currentnode = currentnode->right;
                                                 break;
					}
			}
		}
		//if(data <= parentnode->Data) //左子树
                //     parentnode->left = New;
		//else
		//	parentnode->right = New;
		if(data <= currentnode ->Data) //左子树
                     currentnode ->left = New;
		else
			currentnode ->right = New;
	}
	return root;
}

//------------------------------------------//
//-------------二叉树的建立-----------------//
//------------------------------------------//
b_tree Create_Tree(int len,int *pArray)
{
	int i;
   //根节点的声明
	b_tree root = NULL;

	//插入左右子树
    for(i=0; i< len; i++)
	{
		root = Insert_Tree(root,pArray[i]);
	}
	return root;
}

//-------------------------------------------//
//-----------存储数值------------------------//
//-------------------------------------------//
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;
   }
}
//-------------------------------------------//
//------------打印二叉树前序遍历------------//
//-------------------------------------------//
void Print_Tree(b_tree point)
{
if(point != NULL)
{
	cout <<point->Data;
	Print_Tree(point->left);//打印左节点
	Print_Tree(point->right);//打印右节点
}
}


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

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