二叉树顺序表示的实现（C语言）

二叉树顺序表示的实现（C语言）

#include <stdio.h>
#include <string.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAX_TREE_SIZE 100
typedef char seq_bitree[MAX_TREE_SIZE]; //可以把seq_bitree当做一个数据类型用了
char nil = " "; //字符型节点设" "为空节点
int （*visit_fun）（char）;
struct position
{
int level;
int order;
};
/*
初始化二叉树，结点值赋为nil
*/
void init_seq_bitree（seq_bitree tree）
{
int i = 0;
for（i = 0; i < MAX_TREE_SIZE; i++）
{
tree[i] = nil;
}
return ;
}
/*
根据输入的层序str_tree，创建二叉树
*/
void create_seq_bitree（seq_bitree tree, char *str_tree）
{
int i = 0;
int len = 0;
len = strlen（str_tree）;
for（i = 0; i < len; i++）
{
if（str_tree[i] == 0）
{
tree[i] = nil;
}
else
{
tree[i] = str_tree[i];
}
if（（i ！= 0） && （tree[（i + 1） / 2 - 1] == nil） && （tree[i] ！= nil））
{
printf（"出现了无父节点的非根节点！ "）;
exit（ERROR）;
}
}
for（i = len; i < MAX_TREE_SIZE; i++） //将剩余的部分置为空节点
{
tree[i] = nil;
}
return ;
}
/*
功能：判断二叉树是否为空
返回： TRUE 为空；FLASE 非空
*/
int is_bitree_empty（seq_bitree tree）
{
if（tree[0] == nil）
{
return TRUE;
}
else
{
return ERROR;
}
}
/*
获取二叉树的深度
*/
int get_bitree_depth（seq_bitree tree）
{
int i = 0;
int depth = 0;
for（i = （MAX_TREE_SIZE - 1）; i >= 0; i--）
{
if（tree[i] ！= nil）
{
break;
}
}
do
{
depth++;
}while（i >= （int）pow（2, depth））;
return depth;
}
/*供preorder_traverse调用*/
void pre_traverse（seq_bitree tree, int index）
{
visit_fun（tree[index]）;
if（tree[2 * index + 1] ！= nil）
{
pre_traverse（tree, （2 * index + 1））;
}
if（tree[2 * index + 2] ！= nil）
{
pre_traverse（tree, （2 * index + 2））;
}
}
/*
先序遍历二叉树
*/
int preorder_traverse（seq_bitree tree, int （*visit）（char））
{
visit_fun = visit;
if（is_bitree_empty（tree））
{
printf（"the tree is empty. "）;
}
pre_traverse（tree, 0）;
return OK;
}
/*供inorder_traverse调用*/
void in_traverse（seq_bitree tree, int index）
{
if（tree[2 * index + 1] ！= nil）
{
in_traverse（tree, （2 * index + 1））;
}
visit_fun（tree[index]）;
if（tree[2 * index + 2] ！= nil）
{
in_traverse（tree, （2 * index + 2））;
}
}
/*
中序遍历二叉树
*/
int inorder_traverse（seq_bitree tree, int （*visit）（char））
{
visit_fun = visit;
if（is_bitree_empty（tree））
{
printf（"the tree is empty. "）;
}
in_traverse（tree, 0）;
return OK;
}
/*供postorder_traverse调用*/
void post_traverse（seq_bitree tree, int index）
{
if（tree[2 * index + 1] ！= nil）
{
post_traverse（tree, （2 * index + 1））;
}
if（tree[2 * index + 2] ！= nil）
{
post_traverse（tree, （2 * index + 2））;
}
visit_fun（tree[index]）;
}
/*
后序遍历二叉树
*/
int postorder_traverse（seq_bitree tree, int （*visit）（char））
{
visit_fun = visit;
if（is_bitree_empty（tree））
{
printf（"the tree is empty. "）;
}
post_traverse（tree, 0）;
return OK;
}
/*
按层遍历二叉树
*/
int level_order_traverse（seq_bitree tree, int （*visit）（char））
{
int i = MAX_TREE_SIZE - 1;
int j = 0;
visit_fun = visit;
if（is_bitree_empty（tree））
{
printf（"the tree is empty. "）;
return OK;
}
while（tree[i] ！= nil）
{
i--;
}
for（j = 0; j <+ i; j++）
{
if（tree[j] == nil） //不存在的结点不打印
{
continue;
}
visit_fun（tree[j]）;
}
printf（" "）;
return OK;
}
int visit（char e）
{
printf（"%c ", e）;
return OK;
}
int main（int argc, char *argv[]）
{
seq_bitree tree;
char str_tree[MAX_TREE_SIZE] = "abcde fg";
//测试数据，假设二叉树层序遍历如上（" "表示该处无节点）
init_seq_bitree（tree）;
create_seq_bitree（tree, str_tree）;
if（is_bitree_empty（tree））
{
printf（"the bitree is empty. "）;
return 0;
}
printf（"the depth of the bitree is %d ", get_bitree_depth（tree））;
printf（"先序遍历二叉树: "）;
preorder_traverse（tree, visit）;
printf（" 中序遍历二叉树: "）;
inorder_traverse（tree, visit）;
printf（" 后序遍历二叉树: "）;
postorder_traverse（tree, visit）;
printf（" 按层遍历二叉树: "）;
level_order_traverse（tree, visit）;
return 0;
}