#include
"stdafx.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)
{
int
i =
0
;
if
( (node != NULL) && (pFunc != NULL) )
{
for
(i=
0
; i<format; i++)=
""
{=
""
printf(
"%c"
,=
""
div);=
""
}=
""
pfunc(node-=
""
>data);
printf(
"\n"
);
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
;
}
}
//如果index>0,则表明他有父亲
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);
}
}
}
static
int
recursive_height(GTreeNode* node)
{
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
;
}
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)
{
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);
}
}
</linklist_length(node-></linklist_length(node-></linklist_length(parent-></linklist_length(list);></linklist_length(node-></format;></malloc.h>