Найти корень из любого узла в BST

Question

Как найти корень двоичного дерева поиска с любого узла? Более конкретно, когда я должен останавливаться при прохождении предков с любого данного узла? Есть ли какая-либо функция в java для получения корня? Пожалуйста, помогите мне.

Answer 1

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

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

Но мне непонятно, что именно вы пытаетесь сделать. Зачем вам нужен корневой узел?

Answer 2

Вот двоичное представление дерева узел Java

class Node{ 
    int data; 
    Node leftChild; 
    Node rightChild; 
} 

Но, если мы будем следовать такого рода представления узла, то было бы трудно траверс от конечных узлов к своим предкам. Такое представление подходит для проблем, в которых дается ссылка на корневой узел вместе с оператором проблемы.

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

class Node{ 
    int data; 
    Node parent; 
    Node leftChild; 
    Node rightChild; 
} 

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

/* the logic for traversing */ 
Node tempRoot = given node; 
while(true){ 
    if(null != tempRoot.parent){ 
     tempRoot = tempRoot.parent; 

    }else{ 
     break; 
    } 
} 
/* return value of tempRoot: this is your root */ 

[Изменить: Я не использовал геттеры и сеттеры. Хотя я не предлагаю это реализовать :)]

Answer 3

Если вы внедрили свой собственный BST, то у вас должен быть член данных Node root; в вашем классе BST, вы можете получить доступ/найти корень, просто обратившись к этому элементу данных от любого метода класса BST