tree_arrey.cpp

二叉树的各种操作

/*=========================Programme Description==========================*/
/*程序名称:Tree_Arrey.c                                                   */
/*程序目的:以数组的方式建立二叉树                                         */
/*Written By:Wang Qiang.                                                  */
/*========================================================================*/

#include<stdio.h>
/*------------------------------------------------------*/
/*建立二叉树                                            */
/*------------------------------------------------------*/
void create_btree(int *b_tree, int *nodelist, int len)
{
	int i;
	int level;    /*树的阶层数*/

	b_tree[1]=nodelist[1]; //以第一个元素为根节点
	
	for (i=2;i<len;i++) //依序建立其他节点
	{
		level=1;  //从阶层一开始建立
		while( b_tree[level] !=0) //判断是否有子树存在
		{
			if(nodelist[i]<b_tree[level]) //判断是左子树还是右子树
				level=level*2; //左子树
		    else
				level=level*2+1;//右子树
		}//while
		b_tree[level]=nodelist[i];
	}//for
}//create_btree

/*-------------------------------------------------------*/
/*主函数:输入元素、建立二叉树并输出二叉树的内容          */
/*-------------------------------------------------------*/

void main()
{
	int i,index;
	int data;  //读入输入值所使用的暂存变量
	int b_tree[100]; //二叉树数组
	int nodelist[100];//存储输入数据的数组

	printf("Please input the elements of the binary tree(Exit for 0):\n");

	index=1;

    /*--------------------读取数值到数组中------------------*/
    scanf("%d",&data);

    while(data !=0)
	{
		nodelist[index]=data;
	    index=index+1;
	    scanf("%d",&data);
	}


    /*-------------------清除二叉树数组的内容---------------*/
    for(i=0;i<100;i++)
       b_tree[i]=0;

    /*-------------------建立二叉树--------------------------*/
    create_btree(b_tree,nodelist,index);

    /*-------------------输出二叉树的内容---------------------*/
    printf("\nThe binary tree is:\n");
    for(i=1;i<100;i++)
       printf("%2d:[%d]    \n",i,b_tree[i]);
}

//二叉树组的优点是:对于任一个结点都能容易地找到其父节点,子节点,及兄弟,而且每个节点地存储空间不大
//只占用数组的一个内存空间,但当二叉树的深度和节点数的比例偏高时(二叉树分布不均匀,如歪斜树),内存
//的利用率偏低,容易造成空间的浪费.