?主要针对二叉树的顺序结构
完成功能：
前序遍历，中序遍历，后序遍历，按层与位数得到与改变数值
#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);
}
