tree_struc_arrey.cpp

二叉树的各种操作

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

#include<stdio.h>
#include<stdlib.h>
struct tree
{
	int left;
	int data;
	int right;
};
typedef struct tree treenode;  //新的树型结构
treenode b_tree[15]; //二叉树的结构数组

/*------------------------------------------------------*/
/*建立二叉树                                            */
/*------------------------------------------------------*/

void create_btree(tree* b_tree,int *nodelist,int len)
{
	int i;
	int level;
	int position;   //左树-1,右树1;

	b_tree[0].data=nodelist[0];
	for(i=1;i<len;i++)
	{
		b_tree[i].data=nodelist[i];
		level=0;
		position=0;
		while(position==0)
		{
			if (nodelist[i]>b_tree[level].data)
				if (b_tree[level].right !=-1)
					level=b_tree[level].right;
				else
					position=-1;//设置为右树
			else
				if(b_tree[level].left!=-1)
					level=b_tree[level].left;
				else
					position=1;
		}//while
		if (position==1)
		    b_tree[level].left=i;
		else
			b_tree[level].right=i;
	}//for
}//create_btree

/*------------------------------------------------------*/
/*主程序:输入元素,建立结构数组,并输出二叉树             */
/*------------------------------------------------------*/

void main()
{
	int i,index;
	int data;
	int nodelist[16];

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

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

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

	/*-------------------清除数组的内容--------------------*/
	for(i=0;i<15;i++)
	{
		b_tree[i].data=0;
		b_tree[i].left=-1;
		b_tree[i].right=-1;
	}

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

	/*------------------输出二叉树的内容-------------------*/
	printf("\nthe binary tree content:\n");
	printf("     left        data           right\n");
	printf("=======================================\n");
	for(i =0;i<15;i++)
        printf("%2d:  [%2d]   [%2d]   [%2d] \n",i,b_tree[i].left,b_tree[i].data,b_tree[i].right);

}