分类： C/C++
2013-10-12 14:46:37
原文地址：数据结构深入剖析（8） 作者：mq24705
一、 树的定义
1. 树是一种非线性的数据结构。
2. 树是由n（n >= 0）个结点组成的有限集合。
a) 如果 n = 0，称为空树。
b) 如果n > 0，则：
i. 有一个特定的称之为根（root）的结点，它只有后继，没有直接前驱。
ii. 除根以外的其他结点划分为m（m >= 0）个互不相交的有限集合T0,T1,…,Tm-1,每个集合又是一棵树，并且称之为根的子树。
二、 树家族中的概念
1. 树的结点包含一个数据及若干指向子树的分支。
2. 结点拥有的子树数称为结点的度。
度为0的结点称为叶结点。
度不为0的结点称为分支结点。
3. 树的度的定义为所有结点中的度的最大值。
4. 结点的直接后继称为该结点的孩子，相应的，该结点称为孩子的双亲。
5. 结点的孩子的孩子称为该结点的子孙，相应的，该结点称为子孙的祖先。
6. 同一个父亲的孩子间互称兄弟。
7. 树中结点的最大层次称为树的深度或高度。
8. 如果树中结点的各子树从左向右是有序的，子树间不能互换位置，则称该树为有序树，否则为无序树。
9. 森林是由n棵互不相交的树组成的集合。
三、 树的操作
1. 创建树
2. 销毁树
3. 清空树
4. 插入结点
5. 删除结点
6. 获取结点
7. 获取根结点
8. 获取树的结点数
9. 获取树的高度
10. 获取树的度
四、 树的存储结构
1. 无法直接用数组表示树的逻辑结构
2. 但可以设计结构体数组对结点间的关系进行表述
3. 利用链表组织树中的各个结点
4. 链表中的前后逻辑关系不代表结点间的逻辑关系
5. 结点的逻辑关系由child数据域描述
6. child数据域保存其他结点的存储地址
五、 通用树的实现
//GTree.h
#ifndef _GTREE_H
#define _GTREE_H
typedef void GTree;
typedef void GTreeData;
typedef void (GTree_Printf)(GTreeData*);//用户自定义输出结点数据
GTree* GTree_Create();
void GTree_Destroy(GTree* tree);
void GTree_Clear(GTree* tree);
int GTree_Insert(GTree* tree, GTreeData* data, int pPos);
GTreeData* GTree_Delete(GTree* tree, int pos);
GTreeData* GTree_Get(GTree* tree, int pos);
GTreeData* GTree_Root(GTree* tree);
int GTree_Height(GTree* tree);
int GTree_Count(GTree* tree);
int GTree_Degree(GTree* tree);
void GTree_Display(GTree* tree,GTree_Printf* pFunc,char div);
#endif
//GTree.c
#include
#include
#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,int format,GTree_Printf* pFunc,char div)
{
int i = 0;
if(node != NULL){
for(i = 0;i < format; i++){
printf("%c",div);
}
//printf("%c",(int)node->data);
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,format+1,pFunc,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);
}
}
}
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 = 0;
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_Clear(GTree* tree)
{
GTree_Delete(tree,0);
}
void GTree_Destroy(GTree* tree)
{
GTree_Clear(tree);
LinkList_Destroy(tree);
}
int GTree_Insert(GTree* tree, GTreeData* data, int pPos)
{
LinkList* list = (LinkList*)tree;
int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list));
if(ret){
GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));
TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));
TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));
TLNode* pNode = (TLNode*)LinkList_Get(list,pPos);
ret = (cNode != NULL) && (trNode != NULL) && (cldNode != 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(cldNode);
}
}else{
free(cNode);
free(trNode);
free(cldNode);
return ret;
}
}
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 = 0;
if(trNode != NULL){
ret = recursive_degree(trNode->node);
}
return ret;
}
void GTree_Display(GTree* tree,GTree_Printf* pFunc,char div)
{
TLNode* trNode = (TLNode*)LinkList_Get(tree,0);
if(trNode != NULL){
recursive_display(trNode->node,0,pFunc,div);
}
}
六、 总结
1. 本节中的树结构是一种通用的数据结构
2. 利用链表组织树结点
能够便利的存储结点
链表的维护具有一定的复杂性
