c - 如何在C中给定深度修剪树数据结构

Question

我正在尝试编写这个函数:

struct treeNode *pruneTree(struct treeNode *root, int depth);

给定一棵树:

          1           level 0
         / \
        2   3         level 1
       / \    \
      4  5     6      level 2
     / \
    7   8             level 3

如果深度 = 1，则创建一棵深度 = 1 的树并砍掉之后的所有内容，因此结果应该是:

          1
         / \
        2   3  // tree with depth = 1

我知道如何编写一个修剪叶子的函数，并且我正在尝试使其适应任何级别的修剪:

int isLeaf (struct treeNode * treeNode) {
    return (treeNode->left == NULL) && (treeNode->right == NULL);
}

void removeLeaves(struct treeNode * root) {
    if (root->left != NULL) {
        if (isLeaf (root->left)) {
            free(root->left);
        }
        else {
            removeLeaves(root->left);
        }
    }

    if (root->right != NULL) {
        if (isLeaf (root->right)) {
            free(root->right);
        }

        else {
            removeLeaves(root->right);
        }
    }
}

执行此操作的好策略是什么？我的方法是用 isAfterDepth 函数替换 isLeaf 函数，并使用计算深度的辅助函数，但这似乎效率不高。更优雅的方法是什么？

Answer 1

复制树

如果您打算制作在某一级别修剪的树的副本，您可以简单地使用递归，并在每次递归调用时将深度参数减少一，如果深度结果为0，您只需不再递归复制子级即可。

struct treeNode *pruneTree(struct treeNode *root, int depth) { //version where the tree is copied
    if(root == NULL || depth < 0) {
        return NULL;
    } else {
        treeNode *copyRoot = (treeNode*) malloc(sizeof(treeNode));
        copyRoot->value = root->value;
        copyRoot->left = pruneTree(root->left,depth-1);
        copyRoot->right = pruneTree(root->right,depth-1);
        return copyRoot;
    }
}

代码的工作原理如下:如果给定的root指针为NULL或深度小于零，则NULL 被返回，因为我们要么用叶子的子代调用它，要么已经达到深度约束。

如果不是这种情况，我们会复制当前节点:我们分配一个新的treeNode对象，复制原始节点的value(假设这个称为 value)，并执行递归调用来复制 left 和 right 子级。

改变树

您还可以更改当前树。在这种情况下，您最好首先定义一个函数来删除子树及其所有后代:

void prune(struct treeNode * root) {
    if(root != NULL) {
        if (root->left != NULL) {
            prune(root->left);
        }
        if (root->right != NULL) {
            prune(root->right);
        }
        free(root);
    }
}

现在我们只需要定义一个仅在特定级别进行修剪的方法:

struct treeNode *pruneTree(struct treeNode *root, int depth) { //version where the tree is altered
    if(root != NULL) {
        if(depth <= 0) {
            prune(root->left);
            root->left = NULL;
            prune(root->right);
            root->right = NULL;
        } else {
            pruneTree(root->left,depth-1);
            pruneTree(root->right,depth-1);
        }
    }
    return root;
}