C语言之二叉树（包括遍历的实现）

//头函数
#ifndef __2TREE_H__
#define __2TREE_H__
#include "error.h"

#define TRUE  1
#define FALSE 0

typedef struct _btree
{
char data;
struct _btree *rchild;
struct _btree *lchild;
}Btree;

typedef struct _head
{
struct _btree *head;
int count;
}Head;


//创建树
Head *creat_tree();
//插入结点
int Insert_btree(Head *tree, char data, int pos, int count, int flag);
//打印二叉树
void Display (Head* tree);
//结点的删除
int Delete (Head *tree, int pos, int count);
//二叉树的高度
int BTree_Height (Head *);
//二叉树的度
int BTree_Degree (Head *);
//二叉树的清空
int BTree_Clear (Head *);
//二叉树的销毁
int BTree_Destroy (Head **);
//前序遍历
void pre_order (Btree *node);
//中序遍历
void mid_order (Btree *node);
//后序遍历
void last_order (Btree *node);

#endif //__2TREE_H__

//主演代码
#include "2tree.h"
#include <stdlib.h>

Head *creat_tree()
{
Head *tree = (Head *)malloc(sizeof(Head)/sizeof(char));
if(tree == NULL)
{
return FALSE;
}
tree->head  = NULL;
tree->count = 0;

return tree;
}

int Insert_btree(Head *tree, char data, int pos, int count, int flag)
{
if(tree == NULL || flag != 0 && flag != 1)
{
return FALSE;
}
Btree *node = (Btree *)malloc(sizeof(Btree)/sizeof(char));
if(node == NULL)
{
return FALSE;
}
node->data   = data;
node->rchild = NULL;
node->lchild = NULL;

Btree *parent  = NULL;
Btree *current = tree->head;
int way;
while(count)
{
way = pos & 1;
pos = pos >> 1;
parent = current;

if(way == 0)
current = current->lchild;
else
current = current->rchild;

count --;
}
if(flag == 0)
node->lchild = current;
else
node->rchild = current;

if(parent != NULL)
{
if(way == 0)
parent->lchild = node;
else
parent->rchild = node;
}
else
tree->head = node;

tree->count++;

return TRUE;
}

void r_display(Btree *node,int gap)
{
int i;
if(node == NULL)
{
for(i = 0; i < gap; i++)
{
printf("-");
}
printf("\n");
return;
}

for(i = 0; i < gap; i++)
{
printf("-");
}

printf("%c\n",node->data);

if(node->lchild != NULL || node->rchild !=NULL)
{
r_display(node->lchild, gap + 4);
r_display(node->rchild, gap + 4);
}
}

void Display (Head* tree)
{
if(tree == NULL)
{
return;
}
r_display(tree->head, 0);
}

void r_delete(Head *tree, Btree *node)
{
if(node == NULL || tree == NULL)
{
return;
}
r_delete(tree, node->lchild);

r_delete(tree, node->rchild);

free(node);

tree->count--;
}


int Delete (Head *tree, int pos, int count)
{
if(tree == NULL)
{
return FALSE;
}

Btree *parent  = NULL;
Btree *current = tree->head;
int way = 0;

while(count)
{
way = pos & 1;
pos = pos >> 1;
parent = current;

if(way == 0)
current = current->lchild;
else
current = current->rchild;

count --;
}
if(parent != NULL)
{
if(way == 0)
parent->lchild = NULL;
else
parent->rchild = NULL;
}
else
tree->head = NULL;

r_delete(tree,current);

return TRUE;
}

int r_Height(Btree *node)
{
if(node == NULL)
{
return 0;
}
int lh = r_Height(node->lchild);
int rh = r_Height(node->rchild);

return (lh > rh ? lh+1 : rh+1);
}


int BTree_Height (Head *tree)
{
if(tree == NULL)
{
return FALSE;
}
int subHeight = r_Height(tree->head);

return subHeight;
}

int r_Degree(Btree *node)
{
if(node == NULL)
{
return 0;
}
int degree = 0;

if(node->rchild != NULL)
degree++;
if(node->lchild != NULL)
degree++;

if(degree == 1)
{
int rd = r_Degree(node->rchild);
if(rd == 2)
return 2;

int ld = r_Degree(node->lchild);
if(ld == 2)
return 2;
}

return degree;

}


int BTree_Degree(Head *tree)
{
if(tree == NULL)
{
return FALSE;
}
int degree = r_Degree(tree->head);

return degree;
}

int BTree_Clear (Head *tree)
{
if(tree == NULL)
{
return FALSE;
}
Delete(tree,0,0);

return TRUE;
}

int BTree_Destroy (Head **tree)
{
if(tree == NULL)
{
return FALSE;
}

BTree_Clear(*tree);
free(*tree);

return TRUE;
}

void pre_order (Btree *node)
{
if(node == NULL)
{
return ;
}
printf("%4c",node->data);
pre_order(node->lchild);
pre_order(node->rchild);

}

void mid_order (Btree *node)
{
if(node == NULL)
{
return ;
}
mid_order(node->lchild);
printf("%4c",node->data);
mid_order(node->rchild);
}

void last_order (Btree *node)
{
if(node == NULL)
{
return ;
}
last_order(node->lchild);
last_order(node->rchild);
printf("%4c",node->data);

}

//主函数
#include <stdio.h>
#include "2tree.h"

int main()
{
Head *tree = creat_tree();

Insert_btree(tree, 'A', 0, 0, 0);
Insert_btree(tree, 'B', 0, 1, 0);
Insert_btree(tree, 'C', 2, 2, 0);
Insert_btree(tree, 'D', 2, 3, 0);
Insert_btree(tree, 'E', 6, 3, 0);
Insert_btree(tree, 'F', 1, 1, 0);
Insert_btree(tree, 'G', 3, 2, 0);

Display(tree);
printf("前序遍历：");
pre_order (tree->head);
printf("\n");
printf("中序遍历：");
mid_order (tree->head);
printf("\n");
printf("后序遍历：");
last_order(tree->head);
printf("\n");

printf("高度：%d\n",BTree_Height(tree));
printf("度 ： %d\n",BTree_Degree(tree));

printf("删除结点后：\n");
Delete(tree, 2, 2);
Display(tree);

if(BTree_Destroy(&tree))
printf("销毁成功\n");

return 0;
}