Как найти преемника для данного узла BST - PullRequest
Новая
       47

Как найти преемника для данного узла BST

0 голосов
/ 04 октября 2018

Я пытаюсь построить алгоритм для поиска преемника узла, рекурсивно вызывая следующее: 

 public static BTreeNode inorderFirst(BTree T) {

    BTreeNode n = T.getRoot();
    if (n == null)
        return null;
    while (n.getLeftChild() != null)
        n = n.getLeftChild();
    return n;

}

И вызывая это 

public static BTreeNode inorderNext(BTreeNode n) {

    //returns successor. if it finds one.

    // TODO

    // if node has a right child get its left descendant.

     // otherwise get the first ancestor of which in the left sub-tree the node n is.

     // if it didn't find
    return null;

} // inorderNext()

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

   public static BTreeNode inorderNext(BTreeNode n) {


   if (n.getRightChild() != null) {
    BTreeNode temp = n.getRightChild();
    while (temp.getLeftChild() != null)
        temp = temp.getLeftChild();
    return temp;
   }

   else {
    BTreeNode temp = n;
    BTreeNode par = n.getParent();
    while (par != null) {
        if (par.getLeftChild() == temp)
        return par;
        else {
        temp = par;
        par = par.getParent();
        }
    }

    }

    return null;

} // inorderNext()

Но мне все еще интересно, был ли способ использовать первую функцию рекурсивно для этой.

1 Ответ

0 голосов
/ 04 октября 2018

Ваш код будет выглядеть примерно так: 

if(n.getLeftChild() != null)
        inorderNext(n.getLeftChild());
    System.out.print(n.data);
    if(n.getRightChild() != null)
        inorderNext(n.getRightChild());
...