#include "linkqueue.h"
/**
* @description: 二叉树的创建
* @param {*}
* @return {r-二叉树根节点的地址}
*/
bittree *tree_create()
{
datatype value;
bittree *r;
scanf("%c", &value);
if(value == '#')
return NULL;
r = (bittree *)malloc(sizeof(bittree));
if(r == NULL)
{
#if DEBUG
printf("bittree create error!\n");
#endif
return NULL;
}
r->data = value;
r->left_tree = tree_create();
r->right_tree = tree_create();
return r;
}
/**
* @description: 前序遍历法
* @param {bittree} *r-二叉树根节点的地址
* @return {0-没有子结点时，1-函数结点}
*/
int preorder(bittree *r)
{
if(r == NULL)
return 0;
printf("%c ", r->data);
preorder(r->left_tree);
preorder(r->right_tree);
return 1;
}
/**
* @description: 中序遍历
* @param {bittree} *r-二叉树根节点的地址
* @return {0-没有子结点时，1-函数结点}
*/
int inorder(bittree *r)
{
if(r == NULL)
return 0;
inorder(r->left_tree);
printf("%c ", r->data);
inorder(r->right_tree);
return 1;
}
/**
* @description: 后序遍历
* @param {bittree} *r-二叉树根节点的地址
* @return {0-没有子结点时，1-函数结点}
*/
int backorder(bittree *r)
{
if(r == NULL)
return 0;
backorder(r->left_tree);
backorder(r->right_tree);
printf("%c ", r->data);
return 1;
}
/**
* @description: 层次遍历
* @param {bittree} *r-二叉树根节点的地址
* @return {0-函数失败，1-函数成功}
*/
int levelorder(bittree *r)
{
linkqueue lq;
if(r == NULL)
{
#if DEBUG
printf("r is NULL\n");
#endif
return 0;
}
if((lq = linkqueue_create()) == NULL)
return 0;
linkqueue_enter(lq, r);
while(!linkqueue_empty(lq))
{
r = linkqueue_out(lq);
printf("%c ",r->data);
if(r->left_tree != NULL)
linkqueue_enter(lq, r->left_tree);
if(r->right_tree != NULL)
linkqueue_enter(lq, r->right_tree);
}
puts("");
return 1;
}
评论0