Общие элементы из BST

Question

Я работаю с BST, и меня попросят получить общие элементы в 2 BST и вставить их в 3-й. Мой метод должен вернуть третий BST. Я делал то же самое, работая с LL, но теперь для BST, я не знаю, с чего начать! Я придумал решение, но дело в том, что он работает с корнями дерева, и мне это кажется неправильным. Я так потерян, я не могу найти отправную точку. Совет очень ценится.

EDIT: Я создал метод в классе BST

public BinarySearchTree common(BinarySearchTree t1,BinarySearchTree t2){ 
    return commonValues(t1.root,t2.root); 
} 


private BinarySearchTree commonValues(BinaryTreeNode node1, BinaryTreeNode node2) { 
    // BinaryTreeNode temp1; 
    // BinaryTreeNode temp2; 
    BinarySearchTree tree = new BinarySearchTree(); 

    if (node1 == null && node2 == null) { 
     System.out.println("Empty trees!"); 
    } else { 
     if (node1.getInfo().equals(node2.getInfo())) { 
      tree.insert(node1.getInfo()); 
     } else if (node1.getInfo().compareTo(node2.getInfo()) > 0) { // go left 
      node1 = node1.getLlink(); 
      commonValues(node1, node2); 
     } else { 
      node2 = node2.getRlink(); 
      commonValues(node1, node2); 
       } 
     } 
     return tree; 
    } 

Я с NullPointerException каждый раз, когда я запускаю его, хотя

Answer 1

Я не знаю точно, что интерфейс BinarySearchTree , но я предложу несколько идей.

Во-первых, вам нужно пройти через дерево, потому что если вы всегда проверяете root, вы ничего не делаете. У вас может быть метод, который даст вам следующий узел в определенном порядке, например, pre-order (t2Iterator.next() в следующем примере).

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

Это, в коде, то, что я пытаюсь сказать вам.

public static BinarySearchTree common(BinarySearchTree t1, BinarySearchTree t2) { 

    BinarySearchTree t3 = new BinarySearchTree(); 
    BinarySearchTree t2Iterator = t2; 

    for (int x = 0; x < t2.size(); x++) { 
     if (t1.search(t2Iterator.root.getInfo())) { 
      t3.insert(t2Iterator.root.getInfo()); 
     } 
     t2Iterator = t2Iterator.next(); 
    } 

    return t3; 
} 

И это, как может быть функция рядом с предустановленным порядка обхода

BinarySearchTree next() { 
    if (leftChild != null) { 
     return leftChild; 
    } 
    else if (rightChild != null) { 
     return rightChild; 
    } 
    else { 
     BinarySearchTree iterator = this; 
     while (iterator.parent != null) { 
      if (iterator.parent.rightChild != null) { 
       return iterator.parent.rightChild; 
      } 

      iterator = iterator.parent; 
     } 

     return null; 
    } 
} 

Answer 2

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

Не уверен, что на реализацию BinarySearchTree, но вот что я думаю, выполнима:

Мы хотим создать новый BST, используя общие элементы. Для того, чтобы найти общие элементы:

1. Новое дерево (T3), будет только как большой, как меньшая часть (Т1, Т2)
2. Сравнить размер T1 и T2
3. Используйте меньше одного для поиска против большего дерева. Traverse in предварительный заказ способ. Для каждого узла, если поиск возвращает истину, сделать вставку в T3

Answer 3

Ваша задача похожа на «объединения двух деревьев» с тем исключением, что вы только положить общие элементы для вывода дерева. Таким образом, в основном это можно сделать в линейном времени, выполнив следующие шаги:

1. Начните с итераторов на самых маленьких элементах обоих деревьев.

2.

while both iterators are inside trees: 
if (TreeA.node(iteratorA).value > TreeB.node(iteratorB).value) 
    iteratorB = nextNodeinB(); 
else if (TreeA.node(iteratorA).value < TreeB.node(iteratorB).value) 
    iterator A = nextNodeInA(); 
else 
    outputTree.add(new node(TreeA.node(iteratorA).value)); //the values are equal, so add to the output tree. 

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

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