переход от листа к корню bst

Мне просто интересно, учитывая узел, который указывает на своих левых и правых дочерних элементов, возможно ли каким-то образом получить неупорядоченный отпечаток всего дерева bst?

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

Я думаю, что для начала недостаточно информации, и мой друг получил этот вопрос во время собеседования, и ему было интересно, был ли это неразрешимый вопрос или есть уловка, о которой я не знаю?

Заранее благодарю за любую помощь :)


java binary-search-tree inorder
person user3530718    schedule 24.05.2016    source источник
comment
Если вы не можете пройти вверх с того места, где вы начали, вы не сможете распечатать все дерево, потому что вы можете получить доступ только к узлам на более низком уровне, чем ваш начальный узел.   -  person Keiwan    schedule 25.05.2016
comment
Либо ваш друг не понял/объяснил проблему должным образом, либо интервьюер ничего не знает, и вы правы, невозможно пройти по дереву вверх, если вам не дан родительский указатель   -  person Sleiman Jneidi    schedule 25.05.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

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

На всякий случай, порядок печати прост:

def inorder(node):
    if node == null: return
    inorder(node.left)
    print node.data
    inorder(node.right)
person T. Claverie    schedule 24.05.2016