抽象数据类型(ADT)-树

表、栈、队列都是线性数据结构，这次我们讲一个非线性数据结构 - 树。

树定义及相关概念

树可以用多种方式定义，用递归的方式定义是一种自然的方式。树是一些结点的集合，集合可以为空，若非空，则树由一个被称为根结点的 r 和零个或多个非空子树 T0, T1, ……, Tn 组成，这些子树的每一棵的根都由来自 r 的一条有向边所连接。

每一棵子树的根叫做结点 r 的儿子，r 称为每棵子树根的父亲，父亲的父亲结点称为祖父，儿子的儿子结点为孙子。如图中所示：结点 A 是结点 B, C, D, E, F 的父结点，B, C, D, E, F 是结点 A 的子结点，同理，C 是 G 的父结点，G 是 C 的子结点，H, I, J 是结点 D 的子结点，D 是 H, I, J 的父结点。G, H, I, J, K 是 A 的孙子结点，A 是 G, H, I, J, K 的祖父结点。

没有儿子的结点称为叶子结点，拥有相同父亲的结点称为兄弟结点。图中叶子结点有：B, G, H, I, J, E, K。B, C, D, E, F 互为兄弟结点，H, I, J 互为兄弟结点。

结点间的路径是指从结点一到结点二所经过的结点的序列。路径长指结点路径上所经过的边的条数。注意，结点间的路径都是有向的，即只能从祖先结点到子孙结点，结点一需要是结点二的祖先结点。

结点 ni 的深度是指从根结点到 ni 的路径长，结点 ni 的高度指的是从结点 ni 到叶子结点的最长路径的长。结点的深度和高度是不一样的，深度是指从根结点到该结点，高度是指从该结点到叶子结点。

树的实现

树实现时如果在结点在记录所有儿子结点指针是不现实的，因此采取一种方法，将一个结点的所有儿子结点连成一个链表 - 即在每个结点中记录下个兄弟结点的指针，然后在这个结点中记录它的第一个儿子的信息即可，如图所示：

结构定义为：

#define ELEMENT_TYPE    int

typedef struct treeNode {
    struct treeNode* firstChild;
    struct treeNode* nextSibling;
    ELEMENT_TYPE data;
}tagTreeNode;

实现接口：

#define TREE_OK    (0)    //成功
#define TREE_FAIL    (-1)    //失败

//遍历时结点操作函数指针
typedef void (*operateFunc)(tagTreeNode* node, int depth);

//创建根结点
tagTreeNode* createTree(ELEMENT_TYPE rootData);
//销毁树
int destroyTree(tagTreeNode* root);
//添加子结点
int addChild(tagTreeNode* parent, ELEMENT_TYPE data);
//删除子结点
int delChild(tagTreeNode* parent, ELEMENT_TYPE data);
//遍历树
void traversalTree(tagTreeNode* root, operateFunc func);
//查找结点
tagTreeNode* findNode(tagTreeNode* root, ELEMENT_TYPE data);

实现代码：

#define INIT_TREE_NODE(node, value)    \
    node->data = value;                \
    node->firstChild = NULL;           \
    node->nextSibling = NULL;

tagTreeNode* createTree(ELEMENT_TYPE rootData)
{
    tagTreeNode* root = (tagTreeNode*)malloc(sizeof(tagTreeNode));
    if (root == NULL)
        return NULL;
    INIT_TREE_NODE(root, rootData)
    return root;
}

int destroyTree(tagTreeNode* root)
{
    if (root == NULL)
        return TREE_OK;
    tagTreeNode* next;
    for (tagTreeNode* node = root->firstChild; node != NULL; node = next) {
        next = node->nextSibling;
        destroyTree(node);
        free(node);
    }
    return TREE_OK;
}

int addChild(tagTreeNode* parent, ELEMENT_TYPE data)
{
    if (parent == NULL)
        return TREE_FAIL;
    tagTreeNode* node = (tagTreeNode*)malloc(sizeof(tagTreeNode));
    if (node == NULL)
        return TREE_FAIL;
    INIT_TREE_NODE(node, data)
    tagTreeNode* lastNode = parent->firstChild;
    if (lastNode == NULL) {
        parent->firstChild = node;
    } else {
        while (lastNode->nextSibling != NULL)
            lastNode = lastNode->nextSibling;
        lastNode->nextSibling = node;
    }
    return TREE_OK;
}

int delChild(tagTreeNode* parent, ELEMENT_TYPE data)
{
    if (parent == NULL)
        return TREE_FAIL;

    tagTreeNode* pre = NULL;
    for (tagTreeNode* node = parent->firstChild; node != NULL; pre = node, node = node->nextSibling) {
        if (node->data == data) {
            destroyTree(node);
            if (pre == NULL)
                parent->firstChild = node->nextSibling;
            else 
                pre->nextSibling = node->nextSibling;
            free(node);
            return TREE_OK;
        }
        pre = node;
    }
    return TREE_OK;
}

static void traversalTreeInDepth(tagTreeNode* root, operateFunc func, int depth)
{
    if (root == NULL)
        return ;
    if (func)
        func(root, depth);
    for (tagTreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
        traversalTreeInDepth(node, func, depth+1);
    }
}

void traversalTree(tagTreeNode* root, operateFunc func)
{
    int depth = 0;
    traversalTreeInDepth(root, func, depth);
}

tagTreeNode* findNode(tagTreeNode* root, ELEMENT_TYPE data)
{
    if (root == NULL)
        return NULL;
    if (root->data == data)
        return root;
    for (tagTreeNode* node = root->firstChild; node != NULL; node = node->nextSibling) {
        tagTreeNode* result = findNode(node, data);
        if (result != NULL)
            return result;
    }

    return NULL;
}

测试代码：

void printNode(tagTreeNode* node, int depth)
{
    for (int i = 0; i < depth; i++)
        printf("  ");
    printf("%d\n", node->data);
}

int main(int argc, char* argv[])
{
    tagTreeNode* root;
    root = createTree(0);
    addChild(root, 1);
    addChild(root, 2);
    addChild(root, 3);
    addChild(root, 4);

    tagTreeNode* node = findNode(root, 1);
    if (node != NULL) {
        addChild(node, 11);
        addChild(node, 13);
        addChild(node, 15);
    }

    node = findNode(root, 2);
    if (node != NULL) {
        addChild(node, 22);
    }

    node = findNode(root, 4);
    if (node != NULL) {
        addChild(node, 45);
        addChild(node, 48);
    }

    traversalTree(root, printNode);

    node = findNode(root, 1);
    if (node != NULL) {
        delChild(node, 13);
        printf("after del 13:\n");
        traversalTree(root, printNode);
        printf("after del 11:\n");
        delChild(node, 11);
        traversalTree(root, printNode);
        printf("after del 15:\n");
        delChild(node, 15);
        traversalTree(root, printNode);
    }

    delChild(root, 2);
    printf("after del 2:\n");
    traversalTree(root, printNode);

    return 0;
}

参考：

<数据结构与算法分析-C语言描述> P4