二叉树C语言-白红宇

二叉树C语言

阅读量：4679 次

发布时间：2019-06-09

本文共 4661 字，大约阅读时间需要 15 分钟。

几乎报价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 
     
      #include 
      
       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 
     
      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!

转载于:https://www.cnblogs.com/gcczhongduan/p/4665008.html

你可能感兴趣的文章