二叉树的C语言实现

几乎引自http://blog.csdn.net/hopeyouknow/article/details/6740616，对其中细微的地方进行了修改，才得以运行。

bitree.h

typedef int Item;
typedef struct node
{
	struct node *lchild;
	struct node *rchild;
	Item	data;
}BiTNode, *BiTree;

BiTree InitBiTree(BiTNode *root);

BiTNode *MakeNode(Item item, BiTNode *lchild, BiTNode *rchild);

void FreeNode(BiTNode *pnode);

void ClearBiTree(BiTree tree);

void DestroyBiTree(BiTree tree);

int IsEmpty(BiTree tree);

int GetDepth(BiTree tree);

BiTree GetRoot(BiTree tree);

Item GetItem(BiTNode *pnode);

void SetItem(BiTNode *pnode, Item item);

BiTree SetLChild(BiTree parent, BiTree lchild);

BiTree SetRChild(BiTree parent, BiTree rchild);

BiTree GetLchild(BiTree tree);

BiTree GetRchild(BiTree tree);

BiTree InsertChild(BiTree parent, int lr, BiTree child);

void DeleteChild(BiTree parent, int lr);

void PreOrderTraverse(BiTree tree, void (*visit)());

void InOrderTraverse(BiTree tree, void (*visit)());

void PostOrderTraverse(BiTree tree, void (*visit)());

bitree.c

#include "bitree.h"
#include <malloc.h>
#include <stdlib.h>

BiTree InitBiTree(BiTNode *root)
{
	BiTree tree = root;
	return tree;
}

BiTNode *MakeNode(Item item, BiTNode *lchild, BiTNode *rchild)
{
	BiTNode *pnode = (BiTNode *)malloc(sizeof(BiTNode));
	if(pnode){
		pnode->data = item;
		pnode->lchild = lchild;	
		pnode->rchild = rchild;	
	}
	return pnode;
}

void FreeNode(BiTNode *pnode)
{
	if(pnode != NULL)
			free(pnode);
}

void ClearBiTree(BiTree tree)
{
	BiTNode *pnode = tree;
	if(pnode->lchild != NULL)
			ClearBiTree(pnode->lchild);

	if(pnode->rchild != NULL)
			ClearBiTree(pnode->rchild);

	FreeNode(pnode);
}

void DestroyBiTree(BiTree tree)
{
	if(tree)
			ClearBiTree(tree);
}

IsEmpty(BiTree tree)
{
	if(tree == NULL)
			return 0;
	else
			return 1;
}

int GetDepth(BiTree tree)
{
	int cd, ld, rd;
	cd = ld = rd = 0;
	if(tree){
		ld = GetDepth(tree->lchild);	
		rd = GetDepth(tree->rchild);	
		cd = (ld > rd ? ld : rd);
		return cd+1;
	}else
			return 0;
}

BiTree GetRoor(BiTree tree)
{
	return tree;
}

Item GetItem(BiTNode *pnode)
{
	return pnode->data;		
}

void SetItem(BiTNode *pnode, Item item)
{
	pnode->data = item;
}

BiTree SetLChild(BiTree parent, BiTree lchild)
{
	parent->lchild = lchild;
	return lchild;
}

BiTree SetRChild(BiTree parent, BiTree rchild)
{
	parent->rchild = rchild;
	return rchild;
}

BiTree GetLchild(BiTree tree)
{
	if(tree)
			return tree->lchild;
	return NULL;
}

BiTree GetRchild(BiTree tree)
{
	if(tree)
			return tree->rchild;
	return NULL;
}

BiTree InsertChild(BiTree parent, int lr, BiTree child)
{
	if(parent){
		if(lr == 0 && parent->lchild == NULL){
			parent->lchild = child;
			return child;	
		}	
		if(lr == 1 && parent->lchild == NULL){
			parent->rchild = child;
			return child;	
		}	
	}
	return NULL;
}

void DeleteChild(BiTree parent, int lr)
{
	if(parent){
		if(lr == 0 && parent->lchild != NULL){
			parent->lchild = NULL;
			FreeNode(parent->lchild);	
		}	
		if(lr == 1 && parent->rchild != NULL){
			parent->rchild = NULL;
			FreeNode(parent->rchild);	
		}	
	}
}

void PreOrderTraverse(BiTree tree, void (*visit)())
{
	BiTNode *pnode = tree;
	if(pnode){
		visit(pnode->data);
		PreOrderTraverse(pnode->lchild, visit);	
		PreOrderTraverse(pnode->rchild, visit);	
	}
}

void InOrderTraverse(BiTree tree, void (*visit)())
{
	BiTNode *pnode = tree;
	if(pnode){
		InOrderTraverse(pnode->lchild, visit);	
		visit(pnode->data);
		InOrderTraverse(pnode->lchild, visit);	
	}
}

void PostOrderTraverse(BiTree tree, void (*visit)())
{
	BiTNode *pnode = tree;
	if(pnode){
		PostOrderTraverse(pnode->lchild, visit);	
		PostOrderTraverse(pnode->lchild, visit);	
		visit(pnode->data);
	}
}

test.c

#include "bitree.h"
#include <stdio.h>

void print(Item item)
{
	printf("%d ", item);
}

main()
{
	BiTNode *n1 = MakeNode(10, NULL, NULL);
	BiTNode *n2 = MakeNode(20, NULL, NULL);
	BiTNode *n3 = MakeNode(30, n1, n2);
	BiTNode *n4 = MakeNode(40, NULL, NULL);
	BiTNode *n5 = MakeNode(50, NULL, NULL);
	BiTNode *n6 = MakeNode(60, n4, n5);
	BiTNode *n7 = MakeNode(70, NULL, NULL);

	BiTree tree = InitBiTree(n7);
	SetLChild(tree, n3);
	SetRChild(tree, n6);

	printf("the depth of the tree is %d.\n", GetDepth(tree));

	printf("preorderTraverse:\n");
	PreOrderTraverse(tree, print);
	putchar('\n');

	printf("inorderTraverse:\n");
	InOrderTraverse(tree, print);
	putchar('\n');

	printf("postorderTraverse:\n");
	PostOrderTraverse(tree, print);
	putchar('\n');

	DeleteChild(tree, 1);
	printf("postorderTraverse:\n");
	PostOrderTraverse(tree, print);

	DestroyBiTree(tree);
	if(IsEmpty(tree))
			printf("the tree is empty!\n");

	return 0;

}

编译：gcc test.c bitree.c

运行：./a.out

运行结果：

the depth of the tree is 3.
preorderTraverse:
70 30 10 20 60 40 50 
inorderTraverse:
10 30 10 70 10 30 10 
postorderTraverse:
10 10 30 10 10 30 70 
postorderTraverse:
10 10 30 10 10 30 70 
the tree is empty!