頭文件BiTree.h
[cpp] view
plain copy
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);
/*判定是否為空*/
IsEmpty(BiTree tree);
/*返回樹的深度*/
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);
/*先序遍歷二叉樹*/
PreOrderTraverse(BiTree tree,void(*visit)());
/*中序遍歷二叉樹*/
InOrderTraverse(BiTree tree,void(*visit)());
/*後序遍歷二叉樹*/
PostOrderTraverse(BiTree tree,void(*visit)());
實現文件BiTree.c
[cpp] view
plain copy
#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 GetRoot(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->rchild == 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);
}
}
}
/*先序遍歷二叉樹*/
PreOrderTraverse(BiTree tree,void(*visit)())
{
BiTNode * pnode = tree;
if(pnode)
{
visit(pnode->data);
PreOrderTraverse(pnode->lchild,visit);
PreOrderTraverse(pnode->rchild,visit);
}
}
/*中序遍歷二叉樹*/
InOrderTraverse(BiTree tree,void(*visit)())
{
BiTNode * pnode = tree;
if(pnode)
{
InOrderTraverse(pnode->lchild,visit);
visit(pnode->data);
InOrderTraverse(pnode->rchild,visit);
}
}
/*後序遍歷二叉樹*/
PostOrderTraverse(BiTree tree,void(*visit)())
{
BiTNode * pnode = tree;
if(pnode)
{
PostOrderTraverse(pnode->lchild,visit);
PostOrderTraverse(pnode->rchild,visit);
visit(pnode->data);
}
}
測試程序如下
[cpp] view
plain copy
#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("樹的深度為：%d",GetDepth(tree));
printf("\n先序遍歷如下：");
PreOrderTraverse(tree,print);
printf("\n中序遍歷如下：");
InOrderTraverse(tree,print);
printf("\n後序遍歷如下：");
PostOrderTraverse(tree,print);
DeleteChild(tree,1);
printf("\n後序遍歷如下：");
PostOrderTraverse(tree,print);
DestroyBiTree(tree);
if(IsEmpty(tree))
printf("\n二叉樹為空，銷毀完畢\n");
}
執行結果如下：
[cpp] view
plain copy
fs@ubuntu:~/qiang/tree$ ./Test
樹的深度為：3
先序遍歷如下：70 30 10 20 60 40 50
中序遍歷如下：10 30 20 70 40 60 50
後序遍歷如下：10 20 30 40 50 60 70
二叉樹為空，銷毀完畢
