C中如何修剪给定深度的树形数据结构
C中如何修剪给定深度的树形数据结构
提问于 2017-01-05 20:34:58
我试图写这个函数：
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);
}
}
}做这个的好策略是什么？我的方法是将isLeaf函数替换为isAfterDepth函数，并使用一个计算深度的助手函数，但这看起来并不有效。有什么更优雅的方法可以做到呢？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-01-05 20:54:30
复制树
如果您打算复制在某一级别上被修剪的树的，您可以简单地使用递归，并且在每次递归调用时用一个减少深度参数，如果深度导致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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41494201
复制相关文章
相似问题
腾讯云开发者
