通用树的双亲表示法（代码演示））

//通用树双亲表示法头文件
#ifndef __TREE_H__
#define __TREE_H__

#include 
#include 
#include 

#define FALSE 0
#define TRUE 1

struct _treenode;

typedef struct _childnode       //孩子链表内孩子结点
{
    struct _childnode *Next;
    struct _treenode *ChildNode; //指向孩子结点的指针
}CHILD_NODE;

typedef char TREE_DATA;
typedef struct _treenode         //树结点
{
    TREE_DATA data;
    struct _treenode *Parent;    //双亲结点
    struct _childnode *ChildList; //孩子结点链表
    struct _treenode *Next;
    int degree;                  //树结点的度
}TREE_NODE;

typedef struct _tree
{
    struct _treenode *head;      //带头结点，方便遍历
    int length;                  //树的总长度(不是高度)
}TREE;

//创建一个空树
extern TREE* CreateTree();
//在指定位置pos插入一个树结点
extern int InsertTreeNode(TREE* tree, TREE_DATA data, int pos);
//打印树
extern void Display(TREE* tree);
//删除指定位置pos的树结点
extern DeleteTreeeNode(TREE *tree, int pos, TREE_DATA* e);
//获得指定位置的树结点数据
extern int GetTreeNode(TREE* tree, int pos, TREE_DATA *e);
//清空一棵树
extern int ClearTree(TREE* tree);
//销毁一棵树
extern int DestoryTree(TREE* tree);
//获得根结点
extern TREE_NODE* GetTreeRoot(TREE* tree);
//获得树的总长度
extern int TreeLength(TREE* tree);
//获得树的高度
extern int TreeHeight(TREE* tree);
//获得树的度
extern int TreeDegree(TREE *tree);

#endif

//tree.c 包含了通用树的常用操作
#include "tree.h"

TREE* CreateTree()
{
    TREE* tree = (TREE*)malloc(sizeof(TREE));                    //创建一颗空树(包含头结点)
    if(tree == NULL)    
    {
        printf("create tree:malloc error!\n");
        return NULL;
    }
    tree->length = 0;                                            //初始长度为0
    tree->head = (TREE_NODE*)malloc(sizeof(TREE_NODE));          //带头结点的树
    if(tree->head == NULL)
    {
        printf("create tree head:malloc error!\n");
        free(tree);
        return NULL;
    }
    tree->head->degree = 0;                                      //初始化头结点
    tree->head->data = 0;
    tree->head->Next = NULL;
    tree->head->Parent = NULL;
    tree->head->ChildList = NULL;

    return tree;
}

int InsertTreeNode(TREE* tree, TREE_DATA data, int pos)          //在指定位置pos后面插入一个树结点
{
    if(tree == NULL || pos < 0 || pos > tree->length)
    {
        printf("insert tree node[1]:invalid input\n");
        return FALSE;
    }
    if(pos != 0 && tree->length == pos)//不能等于树的长度
    {
        printf("insert tree node[2]:invalid input\n");
        return FALSE;
    }

    TREE_NODE* node = (TREE_NODE*)malloc(sizeof(TREE_NODE));     //创建一个树结点
    if(node == NULL)
    {
        printf("insert tree node: node malloc error\n");
        return FALSE;
    }
    node->data = data;                                           //初始化数据内容
    node->Next = NULL;//指针域指向空

    node->ChildList = (CHILD_NODE*)malloc(sizeof(CHILD_NODE));   //创建该树结点的孩子链表头结点
    if(node->ChildList == NULL)
    {
        printf("insert tree node:childlist malloc error\n");
        free(node);
        return FALSE;
    }
    node->ChildList->Next = NULL;                                //初始化孩子链表头结点
    node->ChildList->ChildNode = NULL;

    int i = 0;
    TREE_NODE* _parent = tree->head->Next;                       //开始寻找双亲结点
    for (i = 0; i < pos; i++)
    {
        _parent = _parent->Next;//如果是根结点，则双亲为空
    }
    node->Parent = _parent;

    if(_parent != NULL)                                          //如果有双亲，则在其孩子链表中新增一个结点指向插入的结点
    {
        CHILD_NODE* child_node = (CHILD_NODE*)malloc(sizeof(CHILD_NODE));//新增的孩子链表结点
        if(child_node == NULL)
        {
            printf("insert tree node:child node malloc error!\n");
            free(node->ChildList);
            free(node);
            return FALSE;
        }
        child_node->Next = NULL;
        child_node->ChildNode = node;//让孩子链表结点指向需要插入的树结点

        CHILD_NODE* tmp = _parent->ChildList;                    //并且将其插入到双亲的孩子链表后面
        while (tmp->Next != NULL)
        {
            tmp = tmp->Next;
        }

        tmp->Next = child_node;
        _parent->degree++;                                       //别忘了双亲的度加一
    }
    TREE_NODE* temp = tree->head;                                //最后将该结点插入到树中
    while(temp->Next != NULL)
    {
        temp = temp->Next;
    }
    temp->Next = node;
    tree->length++;      //别忘了树的长度加一

    return TRUE;
}

void RDisplay(TREE_NODE* node, int gap)
{
    if(node == NULL)
    {
        printf("R display:no node\n");
        return ;
    }
    int i = 0;
    for(i = 0; i < gap; i++)
    {
        printf("%c", '-');//用来显示树的层次
    }
    printf("%c\n", node->data);

    CHILD_NODE* child = node->ChildList->Next;                   //当前结点的子结点
    while(child != NULL)
    {
        RDisplay(child->ChildNode, gap + 4);                     //打印孩子结点的孩子结点......如果是孩子结点，那么就得多打印4个'-'
        child = child->Next;
    }
}

void Display(TREE* tree)
{
    if(tree == NULL)
    {
        printf("display:invalid input\n");
        return ;
    }
    RDisplay(tree->head->Next, 0);                               //递归打印结点 这个参数0是用来初始化'-'的。
}

void RDelete(TREE *tree, TREE_NODE* node)
{
    if(tree == NULL || node == NULL)
    {
        printf("R delete:unexpected error\n");
        return ;
    }
    TREE_NODE* tmp = tree->head;                                 //1.将需要删除的树结点移出来，树长度减一
    while(tmp->Next != NULL)
    {
        if(tmp->Next == node)
        {
            tmp->Next = node->Next;//也就是这一步
            tree->length--;
            break;
        }
        tmp = tmp->Next;
    }

    TREE_NODE* parent = node->Parent;                            //2.删除双亲结点孩子链表中指向该结点的结点
    if(parent != NULL)
    {
        CHILD_NODE* temp = parent->ChildList;
        while(temp->Next != NULL)
        {
            if(temp->Next->ChildNode == node)
            {
                CHILD_NODE* p = temp->Next;
                temp->Next = p->Next;
                free(p);
                parent->degree--;                                //别忘了双亲的度减一
                break;
            }
            temp = temp->Next;
        }
    }

    CHILD_NODE* child = node->ChildList->Next;                   //3.删除该结点的孩子结点
    while (child != NULL)
    {
        CHILD_NODE* pchild = child->Next;//这边保存child的next域是为了防止程序长时间运行后，该域被意外修改导致程序崩溃
        RDelete(tree, child->ChildNode);                         //4.每个孩子结点的孩子链表处理并且删除其孩子结点
        child  = pchild;
    }

    free (node->ChildList);   //别忘了释放两个空间
    free (node);
}

int DeleteTreeNode(TREE* tree, int pos, TREE_DATA *e)  //删除指定位置pos的树结点
{
    if(tree == NULL || pos < 0 || pos > tree->length)
    {
        printf("delete tree node:input invalid\n");
        return FALSE;
    }
    if(pos != 0 && pos == tree->length)
    {
        printf("delete tree node:input invalid\n");
        return FALSE;
    }
    int i = 0;
    TREE_NODE* node = tree->head->Next;                          //树中第一个结点
    for (i = 0; i < pos; i++)
    {
        node = node->Next;                                       //遍历到需要删除的结点位置
    }
    *e = node->data;                                             //保存所需删除的结点的数据
    RDelete(tree, node);                                         //递归删除

    return TRUE;
}

int GetTreeNode(TREE* tree, int pos, TREE_DATA *e)
{
    if(tree == NULL || pos < 0 || pos > tree->length)
    {
        printf("get tree node:input invalid\n");
        return FALSE;
    }
    if(pos != 0 && pos == tree->length)
    {
        printf("get tree node:input invalid\n");
        return FALSE;
    }
    int i = 0;
    //遍历到该结点直接返回即可
    TREE_NODE* tmp = tree->head->Next;
    for(i = 0; i < pos; i++)
    {
        tmp = tmp->Next;
    }
    *e = tmp->data;

    return TRUE;
}

int ClearTree(TREE* tree)
{
    if(tree == NULL)
    {
        printf("clear tree:no tree\n");
        return FALSE;
    }
    TREE_DATA e;

        return DeleteTreeNode(tree, 0, &e);//其实就是删除根结点
}

int DestoryTree(TREE *tree)
{
    if(tree == NULL)
    {
        printf("destory tree:no tree\n");
        return FALSE;
    }

    ClearTree(tree);

    free(tree->head);  //清空之后再把刚开始分配的树和头结点释放掉
    free(tree);

    return TRUE;
}

TREE_NODE* GetTreeRoot(TREE* tree)
{
    if(tree == NULL)
    {
        printf("get tree root:no tree\n");
        return FALSE;
    }

    return tree->head->Next;
}

int TreeLength(TREE* tree)
{
    if(tree == NULL)
    {
        printf("get tree length:no tree\n");
        return FALSE;
    }

    return tree->length;
}

int RHeight(TREE_NODE* node)
{
    if(node == NULL)
    {
        printf("r height:no tree head\n");
        return FALSE;
    }
    int SubHeight = 0;
    int max = 0;
    CHILD_NODE* child = node->ChildList->Next;//第一个孩子结点
    while(child != NULL)  //遍历孩子链表
    {
        SubHeight = RHeight(child->ChildNode); //向下递归找最深的叶子结点，最后一级一级返回求出max
        if(SubHeight > max)
        {
            max = SubHeight;
        }
        child = child->Next;
    }

    return max + 1;  //由于根结点没算上所以返回max+1
}

int TreeHeight(TREE* tree)
{
    if(tree == NULL)
    {
        printf("get tree height:no tree\n");
        return FALSE;
    }
    int height = RHeight(tree->head->Next);//从第一个结点开始向下递归深入求深度

    return height;
}

int RDegree(TREE_NODE* node)
{
    if(node == NULL)
    {
        printf("get tree degree:no tree head\n");
        return FALSE;
    }
    int SubDegree = 0;
    int max = node->degree;  //假设当前结点度最大
    CHILD_NODE* child = node->ChildList->Next;
    while(child != NULL)
    {
        SubDegree = RDegree(child->ChildNode);向下递归找最大度
        if(SubDegree > max)
        {
            max = SubDegree;
        }
        child = child->Next;
    }

    return max;
}

int TreeDegree(TREE* tree)
{
    if(tree == NULL)
    {
        printf("get tree degree:no tree\n");
        return FALSE;
    }
    int degree = RDegree(tree->head->Next);

    return degree;
}

//main.c 基本测试
#include "tree.h"

int main()
{
    TREE* tree = CreateTree();
    if(tree == NULL)
    {
        return -1;
    }
    InsertTreeNode(tree, 'A', 0);
    InsertTreeNode(tree, 'B', 0);
    InsertTreeNode(tree, 'C', 0);
    InsertTreeNode(tree, 'D', 0);
    InsertTreeNode(tree, 'E', 1);
    InsertTreeNode(tree, 'F', 1);
    InsertTreeNode(tree, 'G', 3);
    InsertTreeNode(tree, 'H', 3);
    InsertTreeNode(tree, 'I', 3);
    InsertTreeNode(tree, 'J', 8);

    Display(tree);

    printf("删除结点D\n");
    TREE_DATA e;
    DeleteTreeNode(tree, 3, &e);
    Display(tree);

    printf("获取结点F的值\n");
    TREE_DATA e1;
    GetTreeNode(tree, 4, &e1);
    printf("F data is %c\n", e1);

    printf("获取树的高度\n");
    int height = TreeHeight(tree);
    printf("树的高度为 %d\n", height);

    printf("获取树的度\n");
    int degree = TreeDegree(tree);
    printf("树的度为 %d\n", degree);

    return 0;
}