数据结构的实践心得(基于典型树结构的C语言XML操作封装,以及相应的树型结构重构:myxml、tre

2021-01-23 01:05发布

数据结构的实践心得(基于典型树结构的C语言XML操作封装,以及相应的树型结构重构:myxml、treeList)

COMZHJ 咕咚的小宇宙

XML操作封装头文件(myxml.h):


#pragma once
#include "treeList.h"

#define XMLNodeAttributeBLOCK 10
#define XMLNumberSIZE 20
#define XMLValueERROR -99999999

#define XMLFileBufferBLOCK 4096

typedef struct
{
    double version;
    char *encoding;
}XMLDocument;

// 初始化XML根节点
treeNode* initXMLRoot(char *rootName);
// 取得匹配xmlPath路径的第一个节点
treeNode* selectSingleXMLNode(treeNode *xmlNode, char *xmlPath);
// 取得节点名称
char* getXMLNodeName(treeNode *xmlNode);

// 取得节点文本
char* getXMLNodeText(treeNode *xmlNode);
// 设置节点文本
int setXMLNodeText(treeNode *xmlNode, char *nodeText);
// 取得子节点
treeNode* getXMLChildNode(treeNode *xmlNode, char *childName);

// 取得节点属性值(字符串)
char* getXMLAttValue(treeNode *xmlNode, char *attName);
// 取得节点属性值(整型)
int getXMLAttValueInt(treeNode *xmlNode, char *attName);
// 取得节点属性值(浮点型)
double getXMLAttValueDouble(treeNode *xmlNode, char *attName);

// 设置节点属性值(字符串)
int setXMLAttValue(treeNode *xmlNode, char *attName, char *attValue);
// 设置节点属性值(整型)
int setXMLAttValueInt(treeNode *xmlNode, char *attName, int attValue);
// 设置节点属性值(浮点型)
int setXMLAttValueDouble(treeNode *xmlNode, char *attName, double attValue);

// 插入XML子节点
treeNode* insertXMLChildNode(treeNode *xmlNode, char *childName, char *childText);
// 移动XML子节点
treeNode* moveXMLChildNode(treeNode *xmlNode, treeNode *childNode);
// 设置节点属性数量
int setXMLNodeAttCount(treeNode *xmlNode, int attCount);
// 删除XML节点(递归)
int deleteXMLNode(treeNode *xmlNode);

// 保存XML文件
void saveXMLFile(char *filePath, treeNode *tnIn, char *encoding);
// 加载XML文件
treeNode* loadXMLFile(char *filePath);

XML操作封装程序文件(myxml.c):


#include <stdlib.h>
#include <stdio.h>
#include "mystring.h"
#include "myxml.h"

// 初始化XML根节点
treeNode* initXMLRoot(char *rootName)
{
    // 取得根节点名称长度
    int len = mystrlen(rootName);
    if (len <= 0) return NULL;

    // 准备复制名称的内存空间
    char *name = (char *)malloc(sizeof(char) * (len + 1));
    if (!name) return NULL;

    // 创建根节点
    treeNode *tn = createTreeNode();
    if (tn)
    {
        // 复制根节点名称
        mystrcpy(rootName, name);
        // 设置树节点的值
        setTreeNodeValue(tn, name, 0);
    }
    else
    {
        // 如果创建树节点失败,则释放名称的内存空间
        free(name);
    }
    return tn;
}

// 取得匹配xmlPath路径的第一个节点
treeNode* selectSingleXMLNode(treeNode *xmlNode, char *xmlPath)
{
    if (!xmlNode) return NULL;
    // 取得文本长度
    int len = mystrlen(xmlPath);
    if (len <= 0) return NULL;

    char *splitList = (char *)malloc(sizeof(char) * (len + 1));
    if (!splitList) return NULL;
    // 分割xmlPath路径
    seqList split = mySplit(xmlPath, '/', splitList);
    char *name = split.elem[0];
    // 逐个比较xmlPath路径
    if (!myEqual(xmlNode->key, name)) return NULL;

    treeNode *tn = xmlNode;
    int i;
    // 循环解析内容
    for (i = 1; i < split.len; i++)
    {
        // 取得每个解析内容
        name = split.elem[i];
        // 逐个比较xmlPath路径
        tn = getXMLChildNode(tn, name);

        if (!tn) break;
    }
    // 释放分割字符串列表
    clearSeqList(&split);

    return tn;
}

// 取得节点名称
char* getXMLNodeName(treeNode *xmlNode)
{
    if (!xmlNode) return NULL;

    return (char *)xmlNode->key;
}

// 取得节点文本
char* getXMLNodeText(treeNode *xmlNode)
{
    if (!xmlNode) return NULL;

    return (char *)(int)xmlNode->value;
}

// 设置节点文本
int setXMLNodeText(treeNode *xmlNode, char *nodeText)
{
    if (!xmlNode) return -1;
    // 取得文本长度
    int len = mystrlen(nodeText);
    if (len <= 0) return -1;

    // 准备复制文本的内存空间
    char *text = (char *)malloc(sizeof(char) * (len + 1));
    if (!text) return -1;

    // 复制文本
    mystrcpy(nodeText, text);
    // 设置树节点的值
    setTreeNodeValue(xmlNode, xmlNode->key, (int)text);

    return 1;
}

// 取得子节点
treeNode* getXMLChildNode(treeNode *xmlNode, char *childName)
{
    if ((!xmlNode) || (!childName)) return NULL;

    treeNode *tn;
    int i;
    for (i = 0; i < xmlNode->childCount; i++)
    {
        tn = xmlNode->childList[i];
        // 进行名称(key)的深度比较
        if (myEqual(tn->key, childName)) return tn;
    }
    return NULL;
}

// 取得节点属性值(字符串)
char* getXMLAttValue(treeNode *xmlNode, char *attName)
{
    if ((!xmlNode) || (!attName)) return NULL;

    int i;
    for (i = 0; i < xmlNode->dataSize; i++)
    {
        // 进行属性名称(dataKey)的深度比较
        if (myEqual(xmlNode->dataKey[i], attName)) return (char *)(int)xmlNode->data[i];
    }
    return NULL;
}

// 取得节点属性值(整型)
int getXMLAttValueInt(treeNode *xmlNode, char *attName)
{
    char *value = getXMLAttValue(xmlNode, attName);
    if (!value) return XMLValueERROR;

    return myatoi(value);
}

// 取得节点属性值(浮点型)
double getXMLAttValueDouble(treeNode *xmlNode, char *attName)
{
    char *value = getXMLAttValue(xmlNode, attName);
    if (!value) return XMLValueERROR;

    return myatof(value);
}

// 设置节点属性值(字符串)
int setXMLAttValue(treeNode *xmlNode, char *attName, char *attValue)
{
    if ((!xmlNode) || (!attName)) return -1;
    // 初始化空字符串
    if (!attValue) attValue = "";

    // 取得属性值长度(允许为空字符串)
    int len = mystrlen(attValue);
    if (len < 0) return -1;

    // 准备复制属性值的内存空间
    char *value = (char *)malloc(sizeof(char) * (len + 1));
    if (!value) return -1;

    int i;
    for (i = 0; i < xmlNode->dataLen; i++)
    {
        // 进行属性名称(dataKey)的深度比较
        if (myEqual(xmlNode->dataKey[i], attName))
        {
            char *tmp = (int)xmlNode->data[i];
            // 释放原有的属性值空间
            if (tmp) free(tmp);

            // 复制属性值
            mystrcpy(attValue, value);
            // 设置树节点的属性值
            xmlNode->data[i] = (int)value;

            return 1;
        }
    }

    // 节点属性的数量,是否小于允许存储的空间
    if (xmlNode->dataLen < xmlNode->dataSize)
    {
        // 取得属性名称长度
        len = mystrlen(attName);
        if (len > 0)
        {
            // 准备复制属性名称的内存空间
            char *name = (char *)malloc(sizeof(char) * (len + 1));
            if (name)
            {
                // 复制属性名称
                mystrcpy(attName, name);
                // 设置树节点的属性名称
                xmlNode->dataKey[xmlNode->dataLen] = name;

                // 复制属性值
                mystrcpy(attValue, value);
                // 设置树节点的属性值
                xmlNode->data[xmlNode->dataLen] = (int)value;

                // 数据内容的长度自增
                xmlNode->dataLen++;
                return 1;
            }
        }
    }
    // 如果上述操作失败,则释放属性值的内存空间
    free(value);

    return -1;
}

// 设置节点属性值(整型)
int setXMLAttValueInt(treeNode *xmlNode, char *attName, int attValue)
{
    if ((!xmlNode) || (!attName)) return -1;

    // 缓存属性值的内存空间
    char *tmp = (char *)malloc(sizeof(char) * XMLNumberSIZE);
    if (!tmp) return -1;

    // 整型转换为字符串
    myitoa(attValue, tmp);
    // 设置节点属性值(字符串)
    int result = setXMLAttValue(xmlNode, attName, tmp);

    // 释放缓存空间
    free(tmp);
    return result;
}

// 设置节点属性值(浮点型)
int setXMLAttValueDouble(treeNode *xmlNode, char *attName, double attValue)
{
    if ((!xmlNode) || (!attName)) return -1;

    // 缓存属性值的内存空间
    char *tmp = (char *)malloc(sizeof(char) * XMLNumberSIZE);
    if (!tmp) return -1;

    // 浮点型转换为字符串
    myftoa(attValue, tmp);
    // 设置节点属性值(字符串)
    int result = setXMLAttValue(xmlNode, attName, tmp);

    // 释放缓存空间
    free(tmp);
    return result;
}

// 插入XML子节点
treeNode* insertXMLChildNode(treeNode *xmlNode, char *childName, char *childText)
{
    if ((!xmlNode) || (!childName)) return NULL;
    // 初始化空字符串
    if (!childText) childText = "";

    // 取得子节点文本长度(允许为空字符串)
    int len = mystrlen(childText);
    if (len < 0) return NULL;

    // 准备复制子节点文本的内存空间
    char *text = (char *)malloc(sizeof(char) * (len + 1));
    if (!text) return NULL;

    // 取得子节点名称长度
    len = mystrlen(childName);
    if (len > 0)
    {
        // 准备复制子节点名称的内存空间
        char *name = (char *)malloc(sizeof(char) * (len + 1));
        if (name)
        {
            // 复制子节点名称
            mystrcpy(childName, name);
            // 复制子节点文本
            mystrcpy(childText, text);

            // 插入子节点
            treeNode* child = insertChildNode(xmlNode, name, (int)text);
            if (child)
            {
                // 设置树节点的数据内容空间大小(属性值数量)
                setTreeNodeDataSize(child, XMLNodeAttributeBLOCK);
                return child;
            }
        }
    }
    // 如果上述操作失败,则释放子节点文本的内存空间
    free(text);

    return NULL;
}

// 移动XML子节点
treeNode* moveXMLChildNode(treeNode *xmlNode, treeNode *childNode)
{
    if ((!xmlNode) || (!childNode)) return NULL;
    // 添加子节点
    return addChildNode(xmlNode, childNode);
}

// 设置节点属性数量
int setXMLNodeAttCount(treeNode *xmlNode, int attCount)
{
    if (!xmlNode) return -1;
    // 判断传入的节点属性数量是否符合要求
    if (attCount < XMLNodeAttributeBLOCK) return -1;

    // 设置树节点的数据内容空间大小
    return setTreeNodeDataSize(xmlNode, attCount);
}

// 删除XML节点(递归)
int deleteXMLNode(treeNode *xmlNode)
{
    if (!xmlNode) return -1;

    // 移除原有的父级关系
    removeChildNode(xmlNode->parent, xmlNode);
    // 清空子节点
    clearTreeList(xmlNode);

    return 1;
}

// 节点的属性信息
char* writeXMLNodeAttInfo(char *buffer, treeNode *tnIn)
{
    if ((!buffer) || (!tnIn)) return buffer;

    int i;
    // 遍历属性信息
    for (i = 0; i < tnIn->dataLen; i++)
    {
        // 拼接属性名称和属性值
        mystrcat(buffer, " ");
        mystrcat(buffer, tnIn->dataKey[i]);
        mystrcat(buffer, "=\"");
        mystrcat(buffer, (int)tnIn->data[i]);
        mystrcat(buffer, "\"");
    }
    return buffer;
}

// 写入节点信息
void writeXMLNodeInfo(char *buffer, treeNode *tnIn, FILE *fpIn, treeNode *root)
{
    if ((!buffer) || (!tnIn) || (!fpIn)) return;
    // 初始化缓存内容
    mymemset(buffer, 0, XMLFileBufferBLOCK);

    // 取得子节点的相对层级
    int i, level = levelChildNode(root, tnIn);
    // 补充制表缩进符号
    for (i = 0; i < level; i++)
    {
        buffer[i] = '\t';
    }
    buffer[i] = '<';
    // 节点名称
    mystrcat(buffer, tnIn->key);
    // 节点的属性信息
    writeXMLNodeAttInfo(buffer, tnIn);
    mystrcat(buffer, ">\r\n");

    // 取得待写入的缓存长度
    int len = mystrlen(buffer);
    // 写入XML文件
    fwrite(buffer, 1, len, fpIn);

    // 是否包含节点值
    len = mystrlen((int)tnIn->value);
    if (len > 0)
    {
        // 初始化缓存内容
        mymemset(buffer, 0, XMLFileBufferBLOCK);

        int valueLevel = level + 1;
        // 补充制表缩进符号
        for (i = 0; i < valueLevel; i++)
        {
            buffer[i] = '\t';
        }
        // 节点值
        mystrcat(buffer, (int)tnIn->value);
        mystrcat(buffer, "\r\n");

        // 写入XML文件
        fwrite(buffer, 1, (i + len + 2), fpIn);
    }
    // 遍历子节点
    for (i = 0; i < tnIn->childCount; i++)
    {
        // 递归写入子节点信息
        writeXMLNodeInfo(buffer, tnIn->childList[i], fpIn, root);
    }
    // 初始化缓存内容
    mymemset(buffer, 0, XMLFileBufferBLOCK);

    // 补充制表缩进符号
    for (i = 0; i < level; i++)
    {
        buffer[i] = '\t';
    }
    // 拼接节点的结束信息
    buffer[i] = '<'; buffer[i + 1] = '/';
    // 节点名称
    mystrcat(buffer, tnIn->key);
    mystrcat(buffer, ">\r\n");

    // 取得待写入的缓存长度
    len = mystrlen(buffer);
    // 写入XML文件
    fwrite(buffer, 1, len, fpIn);
}

// 保存XML文件
void saveXMLFile(char *filePath, treeNode *tnIn, char *encoding)
{
    if (!tnIn) return;
    // 打开待保存的文件(r是只读,w是写入,b打开二进制文件)
    FILE *fp = fopen(filePath, "wb");
    if (!fp) return;

    // 定义一个写入缓存
    char buffer[XMLFileBufferBLOCK] = "<?xml version=\"1.0\" encoding=\"";
    // 连接字符编码设置(如果使用“UTF-8”,则必须保证XML文件内的中文符合“UTF-8”编码要求)
    int len = mystrlen(encoding);
    if (len <= 0) encoding = "GB2312";
    mystrcat(buffer, encoding);
    // 补充文件标识的后续字符
    mystrcat(buffer, "\"?>\r\n");

    // 取得待写入的缓存长度
    len = mystrlen(buffer);
    // 写入XML文件的头部标识
    fwrite(buffer, 1, len, fp);

    // 写入节点信息
    writeXMLNodeInfo(buffer, tnIn, fp, tnIn);
    // 关闭文件
    fclose(fp);
}

// 读取节点信息
treeNode* readXMLNodeInfo(treeNode *parent, char *read, FILE *fpIn, char *splitStr)
{
    if ((!read) || (!fpIn)) return NULL;
    // 读取节点的结束信息
    if (indexOfStr(read, "</") >= 0)
    {
        if (!parent) return NULL;
        // 返回当前节点的父级,表示当前节点完成读取
        return parent->parent;
    }

    treeNode *tn = NULL;
    // 使用空格分割解析内容
    seqList split = mySplit(read, ' ', splitStr);

    char *tmp, *name, *value;
    int i, tmpIndex, len;
    // 循环解析内容
    for (i = 0; i < split.len; i++)
    {
        // 取得每个解析内容
        tmp = split.elem[i];
        // 是否已解析节点
        if (tn)
        {
            tmpIndex = indexOfStr(tmp, "=\"");
            // 解析属性
            if (tmpIndex > 0)
            {
                tmp[tmpIndex] = 0;
                // 属性名称
                name = tmp;
                // 属性值
                value = tmp + tmpIndex + 2;
                myReplaceLast(value, '"', 0);

                // 设置节点属性值(字符串)
                setXMLAttValue(tn, name, value);
            }
        }
        else
        {
            tmpIndex = indexOf(tmp, '<');
            // 解析节点文本
            if (tmpIndex < 0)
            {
                // 设置当前节点文本
                if (parent)
                {
                    len = mystrlen(tmp);
                    // 文本长度是否有效
                    if (len > 0)
                    {
                        // 解析制表符
                        tmpIndex = indexOfLast(tmp, '\t');
                        // 节点文本
                        value = tmp + tmpIndex + 1;
                        myReplaceLast(value, '\n', 0);
                        myReplaceLast(value, '\r', 0);

                        // 设置节点文本
                        setXMLNodeText(parent, value);
                    }
                }
            }
            else
            {
                // 节点名称
                name = tmp + tmpIndex + 1;
                myReplaceLast(name, '>', 0);

                if (parent)
                {
                    // 插入XML子节点
                    tn = insertXMLChildNode(parent, name, "");
                }
                else
                {
                    // 初始化XML根节点
                    tn = initXMLRoot(name);
                }
            }
        }
    }
    // 释放分割字符串列表
    clearSeqList(&split);

    // 如果无法解析有效内容,则继续返回父级节点
    if (!tn) return parent;

    return tn;
}

// 加载XML文件
treeNode* loadXMLFile(char *filePath)
{
    // 打开待保存的文件(r是只读,w是写入,b打开二进制文件)
    FILE *fp = fopen(filePath, "rb");
    if (!fp) return NULL;

    // 定义一个读取缓存
    char buffer[XMLFileBufferBLOCK] = { 0 };
    // 定义一个分割缓存
    char splitStr[XMLFileBufferBLOCK] = { 0 };

    // 读取文件第一行内容
    char *read = fgets(buffer, XMLFileBufferBLOCK, fp);
    // 是否包含文件标识
    if (indexOfStr(read, "?xml") > 0)
    {
        // 继续读取文件第二行内容
        read = fgets(buffer, XMLFileBufferBLOCK, fp);
    }

    // 根节点
    treeNode *root = NULL, *parent;
    // 继续读取文件每一行内容
    while (read)
    {
        if (root)
        {
            // 读取节点信息
            parent = readXMLNodeInfo(parent, read, fp, splitStr);
            // 已读取根节点的结束信息,完成解析
            if (!parent) break;
        }
        else
        {
            // 读取根节点
            root = readXMLNodeInfo(NULL, read, fp, splitStr);
            // 初始化父级节点
            if (root) parent = root;
        }
        // 继续读取
        read = fgets(buffer, XMLFileBufferBLOCK, fp);
    }
    // 关闭文件
    fclose(fp);

    return root;
}

典型树型重构头文件(treeList.h):


#pragma once

#define ChildListMemoryBLOCK 10

typedef double treeElemType;
typedef struct
{
    int key;                        // 树节点关键字
    treeElemType value;         // 树节点值

    int *dataKey;                   // 数据关键字
    treeElemType *data;         // 数据内容
    int dataLen;                    // 数据内容的数量
    int dataSize;                   // 数据内容的空间大小

    struct treeNode *parent;                // 父节点
    struct treeNode **childList;            // 子节点列表
    int childCount;             // 子节点数量
}treeNode;

// 创建树节点
treeNode* createTreeNode();
// 设置树节点的数据内容空间大小
int setTreeNodeDataSize(treeNode *T, int dataSize);
// 设置树节点的值
void setTreeNodeValue(treeNode *T, int key, treeElemType value);
// 设置树节点的数据内容
void setTreeNodeData(treeNode *T, int *dataKey, treeElemType *data, int dataLen);

// 是否为叶子节点返回1,否则返回0
int isLeafTreeNode(treeNode *T);
// 树节点的长度(递归)
int lengthTreeList(treeNode *T);
// 取得树节点的层级
int levelTreeNode(treeNode *T);
// 取得子节点的相对层级
int levelChildNode(treeNode *T, treeNode *child);
// 是否为子节点返回1,否则返回0(递归)
int isChildNode(treeNode *T, treeNode *child);

// 取得树节点的根节点
treeNode* getRoot(treeNode *T);
// 通过关键字,取得树节点(递归)
treeNode* getNodeByKey(treeNode *T, int key);
// 通过索引,取得子节点
treeNode* getChildNode(treeNode *T, int index);

// 插入子节点
treeNode* insertChildNode(treeNode *T, int key, treeElemType value);
// 添加子节点
treeNode* addChildNode(treeNode *T, treeNode *child);
// 移除子节点
int removeChildNode(treeNode *T, treeNode *child);

// 删除子节点
int deleteChildNode(treeNode *T, int index);
// 通过关键字,删除子节点(递归)
int deleteNodeByKey(treeNode *T, int key);
// 清空树列表(递归)
void clearTreeList(treeNode *T);

典型树型重构程序文件(treeList.c):


#include <stdlib.h>
#include "mystring.h"
#include "treeList.h"

// 创建树节点
treeNode* createTreeNode()
{
    treeNode *tn = (treeNode *)malloc(sizeof(treeNode));
    if (!tn) return NULL;

    tn->key = 0;
    tn->value = 0;
    tn->parent = NULL;
    tn->childList = NULL;
    tn->childCount = 0;

    tn->dataKey = NULL;
    tn->data = NULL;
    tn->dataLen = 0;
    tn->dataSize = 0;

    return tn;
}

// 设置树节点的数据内容空间大小
int setTreeNodeDataSize(treeNode *T, int dataSize)
{
    // 判断树节点是否有效
    if (!T) return -1;
    // 判断传入的数据内容空间大小是否有效
    if (dataSize < 1) return -1;

    // 是否需要补充内存空间
    if (T->dataSize < dataSize)
    {
        if (T->dataSize > 0)
        {
            // 补充申请树节点的数据内存空间
            T->dataKey = (int *)realloc(T->dataKey, sizeof(int) * dataSize);
            T->data = (treeElemType *)realloc(T->data, sizeof(treeElemType) * dataSize);
        }
        else
        {
            // 初始化树节点的数据内存空间
            T->dataKey = (int *)malloc(sizeof(int) * dataSize);
            T->data = (treeElemType *)malloc(sizeof(treeElemType) * dataSize);
        }
        // 内存空间申请失败,则退出
        if ((!T->dataKey) || (!T->data)) return -1;

        // 更新数据内容空间大小
        T->dataSize = dataSize;
    }
    return 1;
}

// 设置树节点的值
void setTreeNodeValue(treeNode *T, int key, treeElemType value)
{
    // 判断树节点是否有效
    if (!T) return;

    T->key = key;
    T->value = value;
}

// 设置树节点的数据内容
void setTreeNodeData(treeNode *T, int *dataKey, treeElemType *data, int dataLen)
{
    // 判断树节点是否有效
    if (!T) return;

    int len = T->dataSize;
    // 可设置的数据内容长度,以dataSize和dataLen相对较小的数量为准
    if (dataLen < T->dataSize) len = dataLen;
    if (len <= 0) return;

    // 是否包含数据内容
    int i;
    // 数据关键字
    if ((T->dataKey) && (dataKey))
    {
        // 设置数据关键字
        for (i = 0; i < len; i++)
        {
            T->dataKey[i] = dataKey[i];
        }
    }
    // 数据内容
    if ((T->data) && (data))
    {
        // 设置数据内容
        for (i = 0; i < len; i++)
        {
            T->data[i] = data[i];
        }
    }
    // 数据内容长度
    T->dataLen = len;
}

// 是否为叶子节点返回1,否则返回0
int isLeafTreeNode(treeNode *T)
{
    if (!T) return -1;

    return (T->childCount <= 0);
}

// 树节点的长度(递归)
int lengthTreeList(treeNode *T)
{
    if (!T) return 0;
    // 记录树节点自己的数量
    int count = 1;

    int i;
    // 递归循环子节点
    for (i = 0; i < T->childCount; i++)
    {
        // 递归调用
        count += lengthTreeList(T->childList[i]);
    }
    return count;
}

// 取得树节点的层级
int levelTreeNode(treeNode *T)
{
    if (!T) return -1;
    // 从 0 开始
    int level = 0;

    treeNode *tn = T;
    // 递归父节点
    while (tn->parent)
    {
        tn = tn->parent;
        level++;
    }
    return level;
}

// 取得子节点的相对层级
int levelChildNode(treeNode *T, treeNode *child)
{
    if ((!T) || (!child)) return -1;
    // 判断T是否就是child
    if (T == child) return 0;

    treeNode *tn = child->parent;
    // 从 1 继续
    int level = 1;

    // 递归父节点
    while (tn)
    {
        if (T == tn) return level;

        tn = tn->parent;
        level++;
    }
    return -1;
}

// 是否为子节点返回1,否则返回0(递归)
int isChildNode(treeNode *T, treeNode *child)
{
    if ((!T) || (!child)) return -1;
    // 判断T是否就是child
    if (T == child) return 1;

    int i, result;
    // 递归循环子节点
    for (i = 0; i < T->childCount; i++)
    {
        // 递归调用
        result = isChildNode(T->childList[i], child);
        if (result) return result;
    }
    return 0;
}

// 取得树节点的根节点
treeNode* getRoot(treeNode *T)
{
    if (!T) return NULL;

    treeNode *tn = T;
    // 递归父节点
    while (tn->parent)
    {
        tn = tn->parent;
    }
    return tn;
}

// 通过关键字,取得树节点(递归)
treeNode* getNodeByKey(treeNode *T, int key)
{
    if (!T) return NULL;
    // 判断Key值是否匹配
    if (T->key == key) return T;

    treeNode *tn;
    int i;
    // 递归循环子节点
    for (i = 0; i < T->childCount; i++)
    {
        // 递归调用
        tn = getNodeByKey(T->childList[i], key);
        if (tn) return tn;
    }
    return NULL;
}

// 通过索引,取得子节点
treeNode* getChildNode(treeNode *T, int index)
{
    if (!T) return NULL;
    // 判断索引是否有效
    if ((index < 0) || (index >= T->childCount)) return NULL;

    return T->childList[index];
}

// 插入子节点
treeNode* insertChildNode(treeNode *T, int key, treeElemType value)
{
    if (!T) return NULL;

    if (T->childCount > 0)
    {
        // 计算内存块是否需要增加
        int blockCount = T->childCount % ChildListMemoryBLOCK;
        // 如果余数为零,则需要补充内存空间
        if (!blockCount)
        {
            blockCount = (T->childCount / ChildListMemoryBLOCK);
            // 补充申请子节点列表的内存空间
            T->childList = (treeNode **)realloc(T->childList, 
                sizeof(treeNode *) * ChildListMemoryBLOCK * (blockCount + 1));
        }
    }
    else
    {
        // 申请子节点列表的内存空间
        T->childList = (treeNode **)malloc(sizeof(treeNode *) * ChildListMemoryBLOCK);
    }

    // 创建树节点
    treeNode *child = createTreeNode();
    // 设置子节点的数据值
    setTreeNodeValue(child, key, value);

    child->parent = T;
    // 在子节点列表中添加新增的子节点
    T->childList[T->childCount] = child;
    // 子节点数量自增
    T->childCount++;

    return child;
}

// 添加子节点
treeNode* addChildNode(treeNode *T, treeNode *child)
{
    if ((!T) || (!child)) return NULL;
    // 避免嵌套死循环
    if (isChildNode(child, T) > 0) return NULL;

    if (T->childCount > 0)
    {
        // 计算内存块是否需要增加
        int blockCount = T->childCount % ChildListMemoryBLOCK;
        // 如果余数为零,则需要补充内存空间
        if (!blockCount)
        {
            blockCount = (T->childCount / ChildListMemoryBLOCK);
            // 补充申请子节点列表的内存空间
            T->childList = (treeNode **)realloc(T->childList, 
                sizeof(treeNode *) * ChildListMemoryBLOCK * (blockCount + 1));
        }
    }
    else
    {
        // 申请子节点列表的内存空间
        T->childList = (treeNode **)malloc(sizeof(treeNode *) * ChildListMemoryBLOCK);
    }

    // 移除原有的子节点
    removeChildNode(child->parent, child);

    child->parent = T;
    // 在子节点列表中添加新增的子节点
    T->childList[T->childCount] = child;
    // 子节点数量自增
    T->childCount++;

    return child;
}

// 移除子节点
int removeChildNode(treeNode *T, treeNode *child)
{
    if ((!T) || (!child)) return -1;
    // 判断父级关系是否匹配
    if (T != child->parent) return -1;

    int i, count;
    // 判断原有的父级关系是否已经维护
    for (i = 0; i < T->childCount; i++)
    {
        if (T->childList[i] == child)
        {
            count = T->childCount - 1;
            // 维护子级列表关系,之后的子级指针需要前移
            for (; i < count; i++)
            {
                T->childList[i] = T->childList[i + 1];
            }
            T->childCount--;

            return 1;
        }
    }
    return -1;
}

// 删除子节点
int deleteChildNode(treeNode *T, int index)
{
    if (!T) return -1;
    // 判断索引是否有效
    if ((index < 0) || (index >= T->childCount)) return -1;

    // 清空子节点
    clearTreeList(T->childList[index]);

    int i, count = T->childCount - 1;
    // 维护子级列表关系,之后的子级指针需要前移
    for (i = index; i < count; i++)
    {
        T->childList[i] = T->childList[i + 1];
    }
    T->childCount--;

    return 1;
}

// 通过关键字,删除子节点(递归)
int deleteNodeByKey(treeNode *T, int key)
{
    // 通过关键字,取得树节点(递归)
    treeNode *tn = getNodeByKey(T, key);
    if (!tn) return -1;

    // 移除原有的父级关系
    removeChildNode(tn->parent, tn);
    // 清空子节点
    clearTreeList(tn);

    return 1;
}

// 清空树列表(递归)
void clearTreeList(treeNode *T)
{
    if (!T) return;

    int i;
    // 递归循环子节点
    for (i = 0; i < T->childCount; i++)
    {
        // 递归调用
        clearTreeList(T->childList[i]);
    }

    // 释放数据关键字
    if (T->dataKey) free(T->dataKey);
    // 释放数据空间
    if (T->data) free(T->data);
    // 释放子节点空间
    if (T->childList) free(T->childList);

    // 释放自己
    free(T);
}
标签: