如何在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，或者第th个depth小于零，则返回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;
}