Существуют ли какие-либо «стратегии» для решения проблем двоичного дерева?

Question

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

С помощью связанных списков, например, кажется, что есть образец, который подходит к проблеме, но BTs кажутся либо вы знаете, либо не знаете. Любые советы/указатели? Единственное понятие я, кажется, получили вниз, что если я имею дело с нулевыми узлами, и я хочу сделать что-то с ними, или о них, я буду иметь это в случае

if(root == null) 
    //do something 

или если Я не имею ничего общего с нулевыми узлы, то я использую перевернутый базовый случай

if(root != null) 
    //do stuff 
else 
    //do nothing for null case 

Но даже тогда я приду к потере на то, что рядом. Я думаю, вот пример проблемы, с которой я застрял, и не знаю, как подойти. Я не обязательно ищу ответ, просто потенциальную стратегию для решения таких вопросов (и регулярных двоичных древовидных вопросов).

---

Написать метод numberNodes, который изменяет данные, хранящиеся в виде двоичного дерева, назначая последовательные целые числа, начиная с 1 до каждого узла таким образом, что предварительный заказ обход будет производить числа в порядке (1, 2, 3, и т.д.). Например, с учетом дерева, на которое ссылается дерево внизу слева, вызов tree.numberNodes(); будет перезаписывать существующие данные, присваивая значениям узлов от 1 до 6, так что обход по порядку дерева будет производить 1, 2, 3, 4, 5, 6.

Вы не должны изменить структуру дерева. Вы просто меняете значения, хранящиеся в полях данных. Ваш метод должен возвращать подсчет количества узлов в дереве.

Предположим, что вы добавляете этот метод к IntTree класса, как определено ниже:

public class IntTree { 
    private IntTreeNode overallRoot; 
    ... 
} 

---

После глядя на код еще немного, я полагаю, что я должен использовать мой int count в качестве средства для определения, если Я перемещаюсь в левый корень или правый корень, так как это двоичное дерево поиска, но я все еще не могу реализовать эту функциональность ... блок кодирования ahh!

Answer 1

Вообще - Нарисуйте его, написать свой класс Node и пройти через то, что вам нужно сделать

В этом случае есть несколько шагов, вы должны были бы, по существу, перепроектировать его.

1. выяснить, что обходе

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

3. Пройдитесь через то, что вам нужно сделать, проще пойдите с деревом узлов 3 и увеличьте масштаб.

E.г

1 
/\ 
2 3 

Это то, что вам нужно

Таким образом, вы можете видеть приблизительное представление является

Given X 

    Set node.value = X 
    X = Call on Left with X + 1 # add null check 
    X = Call on Right with X + 1 # add null check 
    return X 

и ваш numberMethod() будет обертка, которая вызывает вышеприведенную функцию на корневом узле с X = 1, после проверки нулевого корня.

Answer 2

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

Так что я бы нарушить вашу проблему образца вниз, как это:

• Если дерево пусто, нет ничего, чтобы сделать
• В противном случае, назначить следующий номер к корню (Aha - мне нужно! " следующее число ", которое должно быть передано этому методу.)
• Recurse в левом поддереве, проходящий больше, чем текущее число.
• Recurse на правом поддереве, проходящий. , , Ах. Мне нужно знать, что следующий номер после обработки левого поддерева. Поэтому мне нужен вызов левого поддерева, чтобы вернуть следующий номер (один больше последнего, который был назначен). Это означает, что мне лучше сделать то же самое. Это будет число, возвращаемое после рекурсии в правом поддереве.
• Когда я вызываю этот метод на корневом узле, он возвращает следующий доступный номер после установки всех значений. Количество узлов, которые были установлены, будет меньше этого.
• На самом деле, возможно, лучше просто вернуть последнее число, а не следующее число. Тогда мне не нужна отдельная функция, чтобы вычесть ее из результата. Поэтому мне лучше изменить предыдущий анализ и сказать, что число, которое нужно передать в метод (а также возвращаемый номер), должно быть последним используемым номером (а не следующим доступным номером) и соответствующим образом отрегулировать всю обработку.

При этом у вас в значительной степени есть схема для метода. Вот как я бы это написал:

public class IntTree { 
    private IntTreeNode overallRoot; 

    public int numberNodes() { 
     return numberNodes(overallRoot, 0); 
    } 

    /** Helper function */ 
    private static int numberNodes(IntTreeNode node, int n) { 
     if (node != null) { 
      node.data = ++n; // preorder means we assign to node first 
      n = numberNodes(node.left, n); 
      n = numberNodes(node.right, n); 
     } 
     return n; 
    } 
} 

Answer 3

На первом месте нет нулевых узлов. То, что может быть нулевым, - это указатели right и left.

Во-вторых, существует много разных типов двоичных деревьев. И я имею в виду по существу разные. Это одна из причин, почему вы не видите много общности.

public class BTNode { 
    int value; 
    BTNode left; 
    BTNode right; 
} 

public static int enumerate(BTNode startNode,int startNumber) { 
    int currentNumber= startNumber ; 
    if(startNode == null) return currentNumber ; 
    startNode.value= currentNumber ; // also currentNumber++ and delete next instruction 
    currentNumber++; 
    currentNumber= enumerate(startNode.left,currentNumber) ; 
    currentNumber= enumerate(startNode.right,currentNumber) ; // also together with return 
    return currentNumber ; 
} 

Счет не имеет ничего общего со значениями узлов. Это связано только с их положением. Справа или слева - все, что имеет значение.