; break; } } } //如果他有儿子，将他的儿子们都杀死 while( LinkList_Length(node->child) > 0 ) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0); recursive_delete(list, trNode->node); } LinkList_Destroy(node->child); free(node); } } } static int recursive_height(GTreeNode* node) { int ret = 0; if( node != NULL ) { int subHeight = 0; int i = 0; for(i=0; i
child); i++) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, i); subHeight = recursive_height(trNode->node); if( ret < subHeight ) { ret = subHeight; } } ret = ret + 1; } return ret; } static int recursive_degree(GTreeNode* node) { int ret = -1; if( node != NULL ) { int subDegree = 0; int i = 0; ret = LinkList_Length(node->child); for(i=0; i
child); i++) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, i); subDegree = recursive_degree(trNode->node); if( ret < subDegree ) { ret = subDegree; } } } return ret; } GTree* GTree_Create() { return LinkList_Create(); } void GTree_Destroy(GTree* tree) { GTree_Clear(tree); LinkList_Destroy(tree); } void GTree_Clear(GTree* tree) { GTree_Delete(tree, 0); } int GTree_Insert(GTree* tree, GTreeData* data, int pPos) { LinkList* list = (LinkList*)tree; //传进被插入的树，表示的实质为链表 //合法性判断 int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list)); //所插入的结点必须在树当中， //故而是pPos < LinkList_Length(list) if( ret ) { TLNode* trNode = (TLNode*)malloc(sizeof(TLNode)); //创建一个结点，用于记录保存树的链表中的结点 TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode)); //孩子（是个链表） TLNode* pNode = (TLNode*)LinkList_Get(list, pPos); //从表示树的链表中获取要插入结点父母亲 GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode)); //要插入的结点，用于接收传进来的data ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL); //树中结点不能为空，该结点 if( ret ) { cNode->data = data; //保存数据 cNode->parent = NULL; //现在还弄不清他的父母亲是谁 cNode->child = LinkList_Create(); //要插入的结点的孩子是个链表 trNode->node = cNode; //将要插入的结点赋值给表示树的链表 cldNode->node = cNode; //将要插入的结点赋值给树结点中的孩子链表 LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list)); //向表示树的链表中插入 if( pNode != NULL ) //如果要插入的结点有父节点，就向父节点的子结点链表插入该结点 { cNode->parent = pNode->node;//认亲的过程 //正式加入大家庭 LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child)); } } else { free(trNode); free(cldNode); free(cNode); } } return ret; } //删除结点 GTreeData* GTree_Delete(GTree* tree, int pos) { TLNode* trNode = (TLNode*)LinkList_Get(tree, pos); GTreeData* ret = NULL; if( trNode != NULL ) { ret = trNode->node->data; recursive_delete(tree, trNode->node); } return ret; } //获得指定位置的结点 GTreeData* GTree_Get(GTree* tree, int pos) { TLNode* trNode = (TLNode*)LinkList_Get(tree, pos); GTreeData* ret = NULL; if( trNode != NULL ) { ret = trNode->node->data; } return ret; } //获得根结点 GTreeData* GTree_Root(GTree* tree) { return GTree_Get(tree, 0); } //求树的高度 int GTree_Height(GTree* tree) { TLNode* trNode = (TLNode*)LinkList_Get(tree, 0); int ret = 0; if( trNode != NULL ) { ret = recursive_height(trNode->node); } return ret; } //求树的结点个数 int GTree_Count(GTree* tree) { return LinkList_Length(tree); } //求树的度 int GTree_Degree(GTree* tree) { TLNode* trNode = (TLNode*)LinkList_Get(tree, 0); int ret = -1; if( trNode != NULL ) { ret = recursive_degree(trNode->node); } return ret; } void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div) { TLNode* trNode = (TLNode*)LinkList_Get(tree, 0); if( (trNode != NULL) && (pFunc != NULL) ) { recursive_display(trNode->node, pFunc, 0, gap, div); } }
主函数操作部分：
// 树.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "GTree.h"
#include
void printf_data(GTreeData* data)
{
printf("%c", (int)data);
}
int _tmain(int argc, _TCHAR* argv[])
{
GTree* tree = GTree_Create();
int i = 0;
GTree_Insert(tree, (GTreeData*)'A', -1);
GTree_Insert(tree, (GTreeData*)'B', 0);
GTree_Insert(tree, (GTreeData*)'C', 0);
GTree_Insert(tree, (GTreeData*)'D', 0);
GTree_Insert(tree, (GTreeData*)'E', 1);
GTree_Insert(tree, (GTreeData*)'F', 1);
GTree_Insert(tree, (GTreeData*)'H', 3);
GTree_Insert(tree, (GTreeData*)'I', 3);
GTree_Insert(tree, (GTreeData*)'J', 3);
printf("Tree Height: %d\n", GTree_Height(tree));
printf("Tree Degree: %d\n", GTree_Degree(tree));
printf("Full Tree:\n");
GTree_Display(tree, printf_data, 2, ' ');
printf("Get Tree Data:\n");
for(i=0; i
运行结果：
Tree Height: 3
Tree Degree: 3
Full Tree:
A
B
E
F
C
D
H
I
J
Get Tree Data:
A
B
C
D
E
F
H
I
J
Get Root Data:
A
After Deleting D:
A
--B
----E
----F
--C
After Clearing Tree:
请按任意键继续. . .
如有错误，望不吝指出。
|