Поиск по глубине в двоичных деревьях / графы в Java - PullRequest
Новая
       49

Поиск по глубине в двоичных деревьях / графы в Java

1 голос
/ 04 марта 2011

Я некоторое время пытался замаскировать этот График под Бинарное Дерево.В настоящее время я использую функцию, которая передает в корневой узел и идентификатор узла, который я ищу.Единственная проблема заключается в том, что в зависимости от того, как я его кодирую, одна из моих сторон никогда не сможет пройти 3 узла.Я уверен, что я просто не делаю рекурсию правильно.Я застрял на этом всю ночь, и не могу этого получить.Я пытался смотреть на другие графики и деревья, но безрезультатно.Мы не используем фактические вершины или другие свойства, подобные графу, но я не могу просто использовать if (x <root.getID()), затем root.left, потому что это не работает, так как это все еще "граф"

Здесьмой неработающий алгоритм поиска, который перестает работать на правой стороне, если я сделаю его длиной в несколько узлов.Visited использует класс HashSet (). 

private Node dfs(Node x, int id)
{
    if (x==null) //base case. Runs into null link
       return null;
    if(visited.contains(x.getID())) //visited before
       return null;
    visited.add(x.getID()); //don't go below Node again
    if(id==x.getID())
      return x;
    Node rc = dfs(x.getRightChild(), id);
    Node lc = dfs(x.getLeftChild(), id);
    //recursive calls

  if (lc.getID()==id)
      return lc;
  if(rc.getID()==id)
      return rc;
  return null;
}

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

private String dfsPrint(Node x) //pass in root at top level
                                //returns a String containing all ID's
{
   if (x==null) //base case. Runs into null link
       return "";
   if(visited.contains(x.getID())) //visited before
       return "";
   visited.add(x.getID()); //don't go below Node again
   String lc = dfsPrint(x.getLeftChild()); //recursive stuffs
   String rc = dfsPrint(x.getRightChild());
   return Integer.toString(x.getID()) + " " + lc + rc;
}

Спасибо за любую помощь.

Редактировать: Я полагаю, я буду расширять то, что я делаю.У меня должна быть функция makeRight или makeLeft, которая вставляет новый узел, а затем существующий узел помещает в него свой левый или правый дочерний элемент.Вот что.В нем поиск является публичным методом, который вызывает закрытые dfs. 

  Node search(int id) // calls private dfsSearch() returns null or a ref to 
                    // a node with ID = id
{
  int ID = id;
  Node x= dfs(root, ID);
  return x;
}


void ML(int x, int y) // ML command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putLeft(temp);

}

void MR(int x, int y)//MR command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putRight(temp);

}

В зависимости от того, как я упорядочиваю рекурсивные функции, если операторы для lc и rc, другая сторона дерева возвращается к базе.case, что заставляет меня предположить, что метод dfs является неправильным.Вот запрошенный класс узлов. 

 class Node {
 private int ID; //ID of the Node. Distinct
 private Node leftChild;
 private Node rightChild;

 Node(int identification)//constructor

{
     ID = identification;
}
 Node(int identification, Node lt, Node rt) //constructor

{
 ID = identification;
 leftChild = lt;
 rightChild = rt;

}

int getID()

{
    return ID;
}

Node getLeftChild()
    {
           return leftChild;
    }
Node getRightChild()
{
    return rightChild;
}
void putLeft(Node lt)
{
    leftChild = lt;
}
void putRight (Node rt)
{
    rightChild = rt;
}

}

Ответы [ 2 ]

1 голос
/ 04 марта 2011

вы могли бы упростить код. Я не думаю, что вам нужен идентификатор. как насчет этого? 

private dfs(Node x, int id) {
    if (x==null) { //base case. Runs into null link
       return;
    }
    if(visited.contains(x)) { //visited before
       return;
    }
    visited.add(x); //don't go below Node again
    dfs(x.getRightChild());
    dfs(x.getLeftChild());
}
0 голосов
/ 04 марта 2011

Ваш метод dfs возвращает ноль в нескольких случаях.Когда вы пытаетесь вызвать getId() для такого возвращаемого значения, вы должны получить исключение.Не так ли?

...