树

1. 简介

树是一种非线性的数据结构，是由 n（n >= 0）个结点组成的一个具有层次关系有限集合。

树是由一个集合以及在该集合上定义的一种关系构成的。

关于树的相关术语与知识可以查看：这篇文章 和 百度百科。

2. 树的实现

#define MAX_SIZE 100

typedef struct Node {
    
    int data;
    
    int parentData;  // 父节点数据
    struct Node * parent;   // 父节点
    
    int childCount;  // 子节点数
    struct Node * nodes[MAX_SIZE]; // 子节点数组
    
} Node, Tree;

/// 初始化树
void initTree(Tree * tree)
{
    tree->parent = NULL;
    tree->childCount = 0;
}

/// 初始化节点
Node * initNode(int data)
{
    Node * node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->parent = NULL;
    node->childCount = 0;
    
    return node;
}

/// 空树
bool isEmptyTree(Tree * tree)
{
    return tree == NULL;
}

/// 查找节点 node
Node * findNode(Tree * tree, int data)
{
    Node * node = NULL;  // 指向根节点
    
    if (tree != NULL) {
        // 检查根结点
        if (tree->data == data) {
            return tree;
        }
        else {
            // 遍历根节点的子结点
            for(int i = 0; i < tree->childCount; i++) {
                // 查找子节点
                node = findNode(tree->nodes[i], data);
                
                // 找到了返回
                if (node)
                    return node;
            }
        }
    }
    
    return node;
}

/// 查看 node 在树中是否存在
bool isExist(Tree * tree, Node * node)
{
    if (tree == NULL || node == NULL)
        return NO;
    
    // 根节点
    if (tree->data == node->data)
        return YES;
    
    BOOL result = NO;
    
    // 遍历根节点的子节点
    for (int i = 0; i < tree->childCount; i++) {
        result = isExist(tree->nodes[i], node);
        
        // 找到了
        if (result)
            return result;
    }
    
    return result;
}

/// 查看 data 数据的节点在树中是否存在
bool isExistByData(Tree * tree, int data)
{
    Node * node = findNode(tree, data);
    
    return isExist(tree, node);
}

/// 插入节点
bool insertNode(Tree * tree, Node * node)
{
    // 空节点
    if (node == NULL) {
        return YES;
    }
    
    // 空树
    if (tree == NULL) {
        node->parent = NULL;
        tree = node;  // 设置根节点
        return YES;
    }
    // 非空
    else {
        // 找到父节点
        Node * parent = findNode(tree, node->parentData);
        
        if (parent != NULL) {
            
            if (parent->childCount == MAX_SIZE) {
                printf("父节点已满！");
                return NO;
            }
            else {
                parent->nodes[parent->childCount] = node;
                parent->childCount++;   // 子节点数 + 1
                node->parent = parent;
                node->parentData = parent->data;
                return YES;
            }
        }
        else {
            printf("未找到父节点！");
            return NO;
        }
    }
    return NO;
}

/// 删除节点
bool removeByNode(Tree * tree, Node * node)
{
    if (tree == NULL || node == NULL)
        return YES;
    
    BOOL result = NO;
    
    // 根节点
    if (tree == node) {
        tree = NULL;
        result = YES;
    }
    else {
        for (int i = 0; i< node->childCount; i++) {
            result = removeByNode(node->nodes[i], node);
            
            // 找到了
            if (result)
                return result;
        }
    }
    
    return result;
}

/// 根据内容删除节点
bool removeByData(Tree * tree, int data)
{
    Node * node = findNode(tree, data);
    
    return removeByNode(tree, node);
}

/* 结点的度：结点拥有的子树的数量。

  度 = 0 称为叶结点，度 > 0 称为分支结点。树的度 = 树的所有结点中度的最大值。
*/
/// 树的度
int degree(Tree * tree)
{
    if (tree == NULL)
        return 0;
    
    // 本节点的度
    int count = tree->childCount;
    
    // 循环子节点。取最大值
    for (int i = 0; i < tree->childCount; i++)
        count = MAX(count, degree(tree->nodes[i]));
    
    return count;
}

/*  树中根结点为第 1 层，根结点的孩子为第 2 层，依次类推。树中结点的最大层次称为树的深度或高度。
 */
/// 树的高度
int height(Tree * tree)
{
    if (tree == NULL)
        return 0;
    
    int n = 1;
    
    // 循环子节点。将每次循环后的结果与上次的比较
    for (int i = 0; i < tree->childCount; i++)
        n = MAX(n, 1 + height(tree->nodes[i]));
    
    return n;
}

/// 树的结点数目
int treeCount(Tree * tree)
{
    if (tree == NULL)
        return 0;
    
    int count = 1;

    // 循环子节点
    for (int i = 0; i < tree->childCount; i++)
        count += treeCount(tree->nodes[i]);
        
    return count;
}

/// 调用
{
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    Tree tree = { 0 };
    initTree(&tree);
    
    tree.data = array[0];

    Node * node2 = initNode(array[1]);
    node2->parentData = 1;
    node2->parent = &tree;
    insertNode(&tree, node2);
    
    Node * node3 = initNode(array[2]);
    node3->parentData = 2;
    node3->parent = node2;
    insertNode(&tree, node3);
    
    Node * node4 = initNode(array[3]);
    node4->parentData = 3;
    node4->parent = node3;
    insertNode(&tree, node4);
    
    Node * node5 = initNode(array[4]);
    node5->parentData = 4;
    node5->parent = node4;
    insertNode(&tree, node5);
    
    Node * node6 = initNode(array[5]);
    node6->parentData = 5;
    node6->parent = node5;
    insertNode(&tree, node6);
    
    Node * node7 = initNode(array[6]);
    node7->parentData = 6;
    node7->parent = node6;
    insertNode(&tree, node7);
    
    printf("%d\t", degree(&tree));
    printf("%d\t", height(&tree));
    
    printf("%d\t", isExist(&tree, node5));
}

1   7   1