Использование рекурсии для обрезки бинарного дерева на основе заданного минимального и максимального значения

Question

Как видно из заголовка, мне нужно обрезать двоичное дерево на основе заданного минимального и максимального значения. Каждый узел хранит значение и левый / правый узел. Я могу определить частные вспомогательные методы для решения этой проблемы, но в противном случае я не могу вызывать какие-либо другие методы класса или создавать какие-либо структуры данных, такие как массивы, списки и т. Д.

Пример будет выглядеть так:

                           overallRoot
                         _____[50]____________________
                        /                             \
          __________[38]                _______________[90]
         /              \              /
    _[14]                [42]      [54]_____
   /     \                                  \
[8]       [20]                               [72]
          \                             /    \
               [26]                     [61]      [83]

trim(52, 65);

должен вернуть:

overallRoot
[54]
    \
     [61]

Мое попытанное решение имеет три метода:

public void trim(int min, int max) {
rootFinder(overallRoot, min, max);

}

Первый рекурсивный метод отлично находит новый корень.

private void rootFinder(IntTreeNode node, int min, int max) {
if (node == null)
    return;

if (overallRoot.data < min) {
    node = overallRoot = node.right;
    rootFinder(node, min, max);

}

else if (overallRoot.data > max) {
    node = overallRoot = node.left;
    rootFinder(node, min, max);
}
else
    cutter(overallRoot, min, max);
}

Этот второй метод должен исключить любые другие узлы, не входящие в мин / макс, но он не работает, как я надеюсь.

private void cutter(IntTreeNode node, int min, int max) {
if (node == null)
    return;

if (node.data <= min) {
    node.left = null;
}
if (node.data >= max) {
    node.right = null;
}

if (node.data < min) {
    node = node.right;
}

if (node.data > max) {
    node = node.left;
}


cutter(node.left, min, max);
cutter(node.right, min, max);
}

Возвращает:

overallRoot
[54]_____
         \
          [72]
         /
     [61]

Любая помощь приветствуется. Не стесняйтесь просить дальнейших объяснений по мере необходимости.

Answer 1

Предполагается, что узел x имеет следующие значения:

1. left (указатель на левый дочерний элемент)
2. right (указатель на правый дочерний элемент)
3. parent (указатель на родителя)

Возможно, вы захотите создать метод CutBranch, который просто удалит узел со всеми его поддеревьями из вашего дерева.Пусть T будет вашим деревом, а T.root будет указателем на его корень.Тогда он может работать так:

CutBranch(x,T) {
    y = T.root;
    while (y.left != x && y.right != x) {
        if (y < x) y = y.right;
        else       y = y.left;
        }
    if (y < x) y.right = Nil;
    else       y.left = Nil;
}

Это предполагает, что ваше дерево, конечно, не содержит узлов с равными значениями, но это занимает O (LG N) времени.Однако он не выполняет сборку мусора.

теперь вы можете перебирать узлы, и каждый раз, когда вы достигаете узла, меньшего, чем ваша нижняя граница, вы можете вызывать CutBranch у его левого потомка, а затем удалять сам узел.Если узел больше вашей верхней границы, вы можете вырезать его как правильный дочерний элемент и удалить его.

Answer 2

Отличный вопрос, большие пальцы, хотя я думаю, что если рассмотреть другой подход, это станет легче.Например, для каждого узла сначала «TRIM» потомки, а затем сам «TRIM».

1. В следующем методе предполагается, что дерево является BST в соответствии с примером в вашем вопросе.

   public Node trim(Node root, int min, int max){
       if(root==null)
           return root;
       root.rightChild = trim (root.rightChild, min, max);
       root.leftChild = trim (root.leftChild,min,max);
   
       if(root.key>max || root.key<min){
           if(root.rightChild!=null)
               return root.rightChild;
           return root.leftChild;
       }
       return root;
   }
   

2. Хотя, если вы хотите, чтобы оно работало для любого двоичного дерева, погода BST или нет.Просто внесите следующие изменения в оператор if выше.

   if(root.key>max || root.key<min){
       if(root.rightChild==null)
           return root.leftChild;
       else if(root.leftChild==null)
           return root.rightChild;
       else{
           //randomly select one of the children to be parent and add the other child to the first free space in its sub tree
           //This is based on personal preferences
           Node temp = root.leftChild;
           while(temp.leftChild!=null || temp.rightChild!=null){
               temp = temp.leftChild;
           }
           if(temp.leftChild==null)
               temp.leftChild=root.rightChild;
           else
               temp.rightChild=root.rightChild;
           return root.leftChild;
       }
   } 
   

Метод должен называться как

tree.root = trim(tree.root, min, max);

Answer 3

При работе с деревом мне проще всего иметь рекурсивные методы, которые берут Node и возвращают Node, идея в том, что я могу затем вызвать метод, чтобы "обновить" узлы подо мной, вызвав методна них.

В этом случае, например, у вас может быть Node minBound(Node), который возвращает поддерево этого узла, которое находится выше нижней границы.Если текущий Node находится в пределах, то примените рекурсивно к каждому ребенку и верните себя.Если текущий Node не находится в пределах, верните обновленный дочерний элемент Node в правильном направлении.Если текущий Node равен null, просто верните null.

Для maxBound.

должен быть написан эквивалентный метод. Тогда вы можете просто сделать minBound(maxBound(root)), чтобы получитьновый корень для дерева.

(Вы можете объединить minBound и maxBound в один метод, но для простоты объяснения я решил разделить их.)

РЕДАКТИРОВАТЬ:Так как это было так долго, я решил добавить пример кода, чтобы показать, что я имею в виду.

public void trim(int min, int max) {
  overallRoot = minBound(maxBound(overallRoot,max),min);
}

private IntTreeNode minBound(IntTreeNode node, int min) {
  if (node == null) // base case of our recursion
    return null;
  if (node.value < min) // we're too small, but our larger children might be in
    return minBound(node.right, min);
  // if we make it to here then we're in bounds, so update our left child
  // (our right child is bigger than us, so doesn't need to be processed)
  node.left = minBound(node.left, min);
  return node;
}

private IntTreeNode maxBound(IntTreeNode node, int max) {
  if (node == null) // base case of our recursion
    return null;
  if (node.value > max) // we're too big, but our smaller children might be in
    return maxBound(node.left, max);
  // if we make it to here then we're in bounds, so update our right child
  // (our left child is smaller than us, so doesn't need to be processed)
  node.right = maxBound(node.right, max);
  return node;
}