#include <stdio.h>
#include <malloc.h>
#include "GTree.h"
#include "LinkList.h"
typedef struct _tag_GTreeNode GTreeNode; /* 树的节点 */
struct _tag_GTreeNode
{
GTreeData* data; /* 节点自身数据 */
GTreeNode* parent; /* 父亲节点 */
LinkList* child; /* 孩子链表 */
};
typedef struct _tag_TLNode TLNode; /* 链表节点结构体，将树节点串成链表 */
struct _tag_TLNode
{
LinkListNode header;
GTreeNode* node;
};
static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)/* 递归打印函数 定义为static外界看不到 format--缩进单位个数 gap--缩进单位 div--缩进形式 pFunc--打印函数*/
{
int i = 0;
if( (node != NULL) && (pFunc != NULL) )
{
for(i=0; i<format; i++)
{
printf("%c", div);
}
pFunc(node->data); /* 打印数据 */
printf("
");
for(i=0; i<LinkList_Length(node->child); i++)
{
TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
recursive_display(trNode->node, pFunc, format + gap, gap, div);
}
}
}
static void recursive_delete(LinkList* list, GTreeNode* node) /* 递归删除函数 要删除该节点的所有函数 */
{
if( (list != NULL) && (node != NULL) )
{
GTreeNode* parent = node->parent; /* 要删除的节点的父亲节点 */
int index = -1;
int i = 0;
for(i=0; i<LinkList_Length(list); i++) /* 从树的组织链表中删除该节点 */
{
TLNode* trNode = (TLNode*)LinkList_Get(list, i);
if( trNode->node == node )
{
LinkList_Delete(list, i);
free(trNode);
index = i; /* 标记位：表面从组织链表中删除成功 */
break;
}
}
if( index >= 0 )
{
if( parent != NULL ) /* 从父亲节点的孩子链表中删除该节点 */
{
for(i=0; i<LinkList_Length(parent->child); i++)
{
TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);
if( trNode->node == node )
{
LinkList_Delete(parent->child, i);
free(trNode);
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); /* 将insert申请的内存释放 */
}
}
}
static int recursive_height(GTreeNode* node) /* 递归算出树的高度 计算一个树的高度首先要算出子树的高度后+1 */
{
int ret = 0;
if( node != NULL )
{
int subHeight = 0;
int i = 0;
for(i=0; i<LinkList_Length(node->child); i++)
{
TLNode* trNode = (TLNode*)LinkList_Get(node->child, i); /* 从链表中取出子树的根节点 */
subHeight = recursive_height(trNode->node);
if( ret < subHeight )
{
ret = subHeight;
}
}
ret = ret + 1; /* 加上根节点 故要+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<LinkList_Length(node->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) /* 此处数据封装 用户表面看起来只是一个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) /* pPos---代表要插入的数据的父亲在表中的位置 */
{
LinkList* list = (LinkList*)tree;
int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list)); /* 合法性检测 pPos至少小于树节点(链表)长度 */
if( ret )
{
TLNode* trNode = (TLNode*)malloc(sizeof(TLNode)); /* (树)组织节点 */
TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode)); /* child节点 *---插入某个节点时，要将其插入两个链表，一个是组织链表，一个是父亲节点的子节点链表 */
TLNode* pNode = (TLNode*)LinkList_Get(list, pPos); /* 从树中(链表)中取出pPos位置的节点 强制转换为TLnode---里面有指向树节点的指针 */
GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode)); /* 申请一个树节点 */
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) /* 从组织链表中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);
}
}
