Как подрезать структуру данных дерева на заданной глубине в 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 

Я знаю, как написать функцию, которая чернослив в Lea VES, и я стараюсь, чтобы адаптировать его к подрезать на любом уровне:

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 и использованием вспомогательной функции, которая вычисляет глубину, но это не кажется эффективным. Что является более элегантным способом сделать это?

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 или я 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); 
    } 
} 

Теперь мы просто должны определить метод, который будет PRUNE только на определенном уровне:

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; 
}