Вставка в дерево

Question

EDIT: правильное решение:

void add(Student s) 
{ 
    if(root == null) 
     root = new TreeNode(s); 
    else 
     insert(root,s);   
} 

void insert(TreeNode tn, Student s) 
{ 
    if(tn.sVal.compareTo(s) > 0) 
    { 
     if(tn.left != null) 
      insert(tn.left, s);    
     else 
     { 
      tn.left = new TreeNode(s); 
      tn.left.parent = tn; 
     } 
    } 
    else if(tn.sVal.compareTo(s) < 0) 
    { 
     if(tn.right != null) 
      insert(tn.right, s); 
     else 
     { 
      tn.right = new TreeNode(s); 
      tn.right.parent = tn; 
     } 
    } 
    balance(tn); 
} 

---

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

void add(Student s) 
    { 
     insert(root,s); 
    } 

private void insert(TreeNode t, Student s) 
{   
    if(t == null) 
     t = new TreeNode(s);   
    else if(t.sVal.compareTo(s) > 0) 
     insert(t.right, s); 
    else if(t.sVal.compareTo(s) < 0) 
     insert(t.left,s);     
} 

Однако, дерево остается пусто, и я не могу понять, почему. Я ненавижу быть настолько расплывчатым, но я не могу найти ошибку в логике. Что мне не хватает?

Answer 1

Вот большой намек: сделать это изменение, а затем отлаживать оттуда:

if (t == null) 
    throw new IllegalArgumentException(); 

И в еще больший намек: При создании нового узла, вы также должны иметь ссылку на его родителей, так что вы может добавить его в родительский.

Answer 2

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

Когда вы звоните insert(root,s), вы передаете ссылку к тому же TreeNode объект на который указывает root. Когда вы затем назначаете t = new TreeNode(s) внутри функции insert, вы назначаете новую ссылку на номер t, NOT до root.

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

Answer 3

Это проблема с указателем. Когда вы переопределяете указатель a с помощью оператора =, все предыдущие ссылки на a теряются. Чтобы сохранить эти ссылки, вам нужно либо изменить объект, используя функции-члены (методы класса в Java), либо написать код напрямую исправить ссылки.

Проще говоря, переопределение указателя влияет только на этот указатель. Все, что уже ссылается на указатель, будет обновлено не.

ПСЕВДОКОД Пример:

Node a = new Node("hello") 
Node b = a 
a = new Node("goodbye") 

print(a) // this prints "goodbye" 
print(b) // this prints "hello" 

Для того, чтобы b, чтобы указать на новый a, вы должны написать b = a.

Отредактировав это, вам нужно будет переписать метод insert(). Поскольку дерево рекурсивно, рекурсивный метод insert() должен делать трюк. Существует множество ресурсов в Интернете для рекурсивных реализаций дерева, если они вам понадобятся: Recursive Tree Java