树的定义及通用树结构的实现

一、树的定义

1>定义

   树是一种非线性的数据结构，树是由n(n>=0)个结点组成的有限集合；如果n=0，称为空树;如

果n>0，则：

    有一个特定的称之为根(root)的结点,它只有直接后继，但没有直接前驱；

    

    除根以外的其他结点划分为m(m>=0)个，互不相交的有限集合T0，T1，...，Tn-1，每个集合又是

一棵树，并且称之为根的子树（subTree）.

2>树家族中的概念

    树的结点包含一个数据及若干指向子树的分支；

    结点拥有的子树称为结点的度：

        度为0的结点称为叶结点；

        度不为0的结点称为分支结点；

    树的度定义为所有结点中的度的最大值。

    结点的直接后继称为该结点的孩子，相应的，该结点称为孩子结点的双亲；

    结点的孩子的孩子的...称为该结点的子孙，相应的，该结点称为子孙的祖先；

    同一个双亲的孩子之间互称兄弟。

    结点的层次：根为第一层，根的孩子为第二层......树中结点的最大层次称为树的深度或高度。

    如果树中结点的各子树从左向右是有次序的，子树间不能互换位置，则称该树为有序树，否则为

无序树。

    森林是 由n(n>=0)棵互不相交的树组成的集合。

3>树的操作：

创建树、销毁树、清空树、插入结点、删除结点、获取结点、获取根结点、获取树的结点树、获取树

的高度、获取树的度。

4>树操作的实现

树在程序中表现为一种特殊的数据类型，树的操作在程序中的表现为一组函数。

Tree* Tree_Create();

void Tree_Destroy(Tree* tree);

void Tree_Clear(Tree* tree);

int Tree_Insert(Tree* tree,TreeNode* node,int pos);

TreeNode* Tree_Delete(Tree* tree,int pos);

TreeNode* Tree_Get(Tree* tree,int pos);

TreeNode* Tree_Root(Tree* tree);

int Tree_Height(Tree* tree);

int Tree_Count(Tree* tree);

int Tree_Degree(Tree* tree);

二、树的存储结构

无法直接用数组表示树的逻辑结构，但可以设计结构体数组对结点间的关系进行表述，利用链表组织

树中的各个结点；链表中的前后关系不代表结点间的逻辑关系，结点的逻辑关系由child数据域描述

child数据域保存其他结点的存储地址。

树结点结构体：

typedef struct _tag_GTreeNode GTreeNode;

struct _tag_GTreeNode

{

    GTreeData* data;

    GTreeNode* parent;

    LinkList* child;

};

链表结点结构体

typedef struct _tag_TLNode TLNode;

struct _tag_TLNode

{

    LinListNode* header;

    GTreeNode* node;

};

树中每一个结点包含一个指向父节点的指针。注意：树结点在链表中的位置不代表树的任何逻辑关

系。本节中的树结构式一种通用的数据结构，利用链表组织树结点能够便利的存取结点，链表的维护

具有一定的复杂性。

通过链表的代码复用，通用树结构的实现代码如下：

/***********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 pPos);

GTreeData* GTree_Get(GTree* tree,int pPos);

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,int gap, char div);

#endif

/*****************GTree.c*********************/
#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)
{
    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;
            }
        }

        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);
        }
    }
}
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));
    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(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;
}

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;
}


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,int gap, char div)
{
    TLNode* trNode = (TLNode*)LinkList_Get(tree,0);

    if( trNode != NULL )
    {
        recursive_display(trNode->node,pFunc,0,gap,div);
    }
}

/******************main.c********************/
#include <stdio.h>
#include <stdlib.h>
#include "GTree.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

void printf_data(GTreeData* data)
{
    printf("%c ",(int)data);
}

int main(int argc, char *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 Degree: %d\n",GTree_Degree(tree));

    printf("Tree Height: %d\n",GTree_Height(tree));

    printf("Get Tree Data: \n");

    for(i=0; i<GTree_Count(tree); i++)
    {
        printf_data(GTree_Get(tree,i));

    }
    printf("\n");

    printf("Get Root Data: \n");

    printf_data(GTree_Root(tree));
    printf("\n");

    GTree_Display(tree,printf_data,2,'*');


    GTree_Delete(tree,3);



    printf("After Delete D : \n");
    GTree_Display(tree,printf_data,2,'-');

    GTree_Clear(tree);

    printf("After Clear: \n");
    GTree_Display(tree,printf_data,2,'+');

    GTree_Destroy(tree);

    return 0;
}