二叉树顺序结构C语言实现

 主要针对二叉树的顺序结构

完成功能：

前序遍历，中序遍历，后序遍历，按层与位数得到与改变数值

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"
#define maxlen 100

typedef int Tree[maxlen]; /* 0号单元存储根结点  */


int InitTree(Tree T)
{
	int i;
	for (i = 0;i < maxlen;i++)
		T[i] = 0; /* 初值为空 */
	return 1;
}

int CreateTree(Tree T)
{
	int i;
	int n = 0;
	printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n", maxlen);
	while (1)
	{
		scanf("%d", &i);
		if (i == 99)
		{
			break;
		}
		T[n] = i;
		n++;
	}
	return 1;
}

int CreateTree1(Tree T)
{
	int i = 0;
	printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n", maxlen);
	while (i < 10)
	{
		T[i] = i + 1;

		if (i != 0 && T[(i + 1) / 2 - 1] == 0 && T[i] != 0) /* 此结点(不空)无双亲且不是根 */
		{
			printf("出现无双亲的非根结点%d\n", T[i]);
			break;
		}
		i++;
	}
	while (i < maxlen)
	{
		T[i] = 0; /* 将空赋值给T的后面的结点 */
		i++;
	}

	return 1;
}



int get_lastnode(Tree T)
{
	int i;
	for (i = maxlen - 1;i >= 0;i--)
	{
		if (T[i] != 0)
		{

			break;
		}
	}
	return i;
}

int get_depth(Tree T)
{
	int i;
	int depth;
	for (i = maxlen - 1;i >= 0;i--)
	{
		if (T[i] != 0)
		{
			
			break;
		}
	}
	i++;//
	depth = (int)(log(i) / log(2))+1;
	return depth;

}

int  seeTree(Tree T)
{
	int i, n;
	i = get_lastnode(T);
	printf("层序遍历：\n");
	for (n = 0;n <= i;n++)
	{
		printf("%d ", T[n]);
	}
	printf("\n");
	return 1;

}

int get_data(Tree T,int level, int order)
{
	int i;
	int j=0;
	i = powl(2, level-1) - 1;
	while (j!=order)
	{
		if (T[i] != 0)
		{
			j++;
		}
		i++;
	}
	return T[i-1];
}

int change_data(Tree T,int level, int order, int value)
{
	int i;
	int j = 0;
	i = powl(2, level - 1) - 1;
	while (j != order)
	{
		if (T[i] != 0)
		{
			j++;
		}
		i++;
	}
	i--;
	T[i] = value;
	return 1;
}

int get_lchild(int i)  //得到第i个节点的左子节点
{
	return (2 * i+1);
}

int get_rchild(int i)  //得到第i个节点的左子节点
{
	return (2 * i+2 );
}

int pre_traverse(Tree T, int i)
{
	int l = get_lchild(i);
	int r = get_rchild(i);
	if (T[0] == 0)
	{
		return 0;
	}
	printf("%d ", T[i]);
	if (T[l] != 0)
	{
		pre_traverse(T, l);
	}
	if (T[r] != 0)
	{
		pre_traverse(T, r);
	}
	return 1;
}

int mid_traverse(Tree T, int i)
{
	int l = get_lchild(i);
	int r = get_rchild(i);
	if (T[0] == 0)
	{
		return 0;
	}
	if (T[l] != 0)
	{
		mid_traverse(T, l);
	}
	printf("%d ", T[i]);
	if (T[r] != 0)
	{
		mid_traverse(T, r);
	}

	return 1;
}

int post_traverse(Tree T, int i)
{
	int l = get_lchild(i);
	int r = get_rchild(i);
	if (T[0] == 0)
	{
		return 0;
	}
	if (T[l] != 0)
	{
		post_traverse(T, l);
	}
	if (T[r] != 0)
	{
		post_traverse(T, r);
	}
	printf("%d ", T[i]);

	return 1;
}

int main()
{
	Tree T;
	int depth;
	int m;
	InitTree(T);
	CreateTree1(T);
	seeTree(T);
	depth = get_depth(T);
	printf("\n%d\n", depth);

	printf("前序遍历：\n");
	pre_traverse(T, 0);
	printf("\n");
	printf("中序遍历：\n");
	mid_traverse(T, 0);
	printf("\n");
	printf("后序遍历：\n");
	post_traverse(T, 0);
	printf("\n");

	m = get_data(T, 4, 3);
	printf("\n%d\n", m);

	change_data(T, 3, 2, 78);
	seeTree(T);


}