1. 簡(jiǎn)介

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)向楼，是由 n（n >= 0）個(gè)結(jié)點(diǎn)組成的一個(gè)具有層次關(guān)系有限集合加缘。

樹(shù)是由一個(gè)集合以及在該集合上定義的一種關(guān)系構(gòu)成的锤悄。

關(guān)于樹(shù)的相關(guān)術(shù)語(yǔ)與知識(shí)可以查看：這篇文章 和 百度百科衣形。

2. 樹(shù)的實(shí)現(xiàn)

#define MAX_SIZE 100

typedef struct Node {
    
    int data;
    
    int parentData;  // 父節(jié)點(diǎn)數(shù)據(jù)
    struct Node * parent;   // 父節(jié)點(diǎn)
    
    int childCount;  // 子節(jié)點(diǎn)數(shù)
    struct Node * nodes[MAX_SIZE]; // 子節(jié)點(diǎn)數(shù)組
    
} Node, Tree;

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

/// 初始化節(jié)點(diǎn)
Node * initNode(int data)
{
    Node * node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->parent = NULL;
    node->childCount = 0;
    
    return node;
}

/// 空樹(shù)
bool isEmptyTree(Tree * tree)
{
    return tree == NULL;
}

/// 查找節(jié)點(diǎn) node
Node * findNode(Tree * tree, int data)
{
    Node * node = NULL;  // 指向根節(jié)點(diǎn)
    
    if (tree != NULL) {
        // 檢查根結(jié)點(diǎn)
        if (tree->data == data) {
            return tree;
        }
        else {
            // 遍歷根節(jié)點(diǎn)的子結(jié)點(diǎn)
            for(int i = 0; i < tree->childCount; i++) {
                // 查找子節(jié)點(diǎn)
                node = findNode(tree->nodes[i], data);
                
                // 找到了返回
                if (node)
                    return node;
            }
        }
    }
    
    return node;
}

/// 查看 node 在樹(shù)中是否存在
bool isExist(Tree * tree, Node * node)
{
    if (tree == NULL || node == NULL)
        return NO;
    
    // 根節(jié)點(diǎn)
    if (tree->data == node->data)
        return YES;
    
    BOOL result = NO;
    
    // 遍歷根節(jié)點(diǎn)的子節(jié)點(diǎn)
    for (int i = 0; i < tree->childCount; i++) {
        result = isExist(tree->nodes[i], node);
        
        // 找到了
        if (result)
            return result;
    }
    
    return result;
}

/// 查看 data 數(shù)據(jù)的節(jié)點(diǎn)在樹(shù)中是否存在
bool isExistByData(Tree * tree, int data)
{
    Node * node = findNode(tree, data);
    
    return isExist(tree, node);
}

/// 插入節(jié)點(diǎn)
bool insertNode(Tree * tree, Node * node)
{
    // 空節(jié)點(diǎn)
    if (node == NULL) {
        return YES;
    }
    
    // 空樹(shù)
    if (tree == NULL) {
        node->parent = NULL;
        tree = node;  // 設(shè)置根節(jié)點(diǎn)
        return YES;
    }
    // 非空
    else {
        // 找到父節(jié)點(diǎn)
        Node * parent = findNode(tree, node->parentData);
        
        if (parent != NULL) {
            
            if (parent->childCount == MAX_SIZE) {
                printf("父節(jié)點(diǎn)已滿辣往！");
                return NO;
            }
            else {
                parent->nodes[parent->childCount] = node;
                parent->childCount++;   // 子節(jié)點(diǎn)數(shù) + 1
                node->parent = parent;
                node->parentData = parent->data;
                return YES;
            }
        }
        else {
            printf("未找到父節(jié)點(diǎn)兔院！");
            return NO;
        }
    }
    return NO;
}

/// 刪除節(jié)點(diǎn)
bool removeByNode(Tree * tree, Node * node)
{
    if (tree == NULL || node == NULL)
        return YES;
    
    BOOL result = NO;
    
    // 根節(jié)點(diǎn)
    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;
}

/// 根據(jù)內(nèi)容刪除節(jié)點(diǎn)
bool removeByData(Tree * tree, int data)
{
    Node * node = findNode(tree, data);
    
    return removeByNode(tree, node);
}

/* 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)的數(shù)量。

  度 = 0 稱為葉結(jié)點(diǎn)站削，度 > 0 稱為分支結(jié)點(diǎn)秆乳。樹(shù)的度 = 樹(shù)的所有結(jié)點(diǎn)中度的最大值。
*/
/// 樹(shù)的度
int degree(Tree * tree)
{
    if (tree == NULL)
        return 0;
    
    // 本節(jié)點(diǎn)的度
    int count = tree->childCount;
    
    // 循環(huán)子節(jié)點(diǎn)钻哩。取最大值
    for (int i = 0; i < tree->childCount; i++)
        count = MAX(count, degree(tree->nodes[i]));
    
    return count;
}

/*  樹(shù)中根結(jié)點(diǎn)為第 1 層屹堰，根結(jié)點(diǎn)的孩子為第 2 層，依次類推街氢。樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度或高度扯键。
 */
/// 樹(shù)的高度
int height(Tree * tree)
{
    if (tree == NULL)
        return 0;
    
    int n = 1;
    
    // 循環(huán)子節(jié)點(diǎn)。將每次循環(huán)后的結(jié)果與上次的比較
    for (int i = 0; i < tree->childCount; i++)
        n = MAX(n, 1 + height(tree->nodes[i]));
    
    return n;
}

/// 樹(shù)的結(jié)點(diǎn)數(shù)目
int treeCount(Tree * tree)
{
    if (tree == NULL)
        return 0;
    
    int count = 1;

    // 循環(huán)子節(jié)點(diǎn)
    for (int i = 0; i < tree->childCount; i++)
        count += treeCount(tree->nodes[i]);
        
    return count;
}

/// 調(diào)用
{
    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