Java - бинарное семейное дерево - не могу найти узел

Question

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

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

Вот код для моих классов FamilyTree и Main:

public class FamilyTree
{
Node root;

// Initialize tree
public FamilyTree()
{
    root = null;
}


// --------------------------------------------------------------
// This method inserts a new family member into the tree.
// It takes two parameters - the parent who the new node should
// be inserted under, and the name of the new member being added.
// --------------------------------------------------------------

public void insertNode(String par, String name)
{
    Node parent, current;
    Node newMember = new Node(name);

    // If tree is empty, then the new member becomes the root
    if(root == null)
        root = newMember;


    // If adding a sibling to the root, insert to root's right child
    else if(par == "")
    {
        // Check if root's sibling is empty
        if(root.rightChild == null)
            root.rightChild = newMember;


        // Traverse root's siblings until end, then insert at end
        else
        {
            current = root;

            while(current.rightChild != null)
                current = current.rightChild;

            current.rightChild = newMember;
        }
    }

    else
    {
        // Find the parent where we will insert under
        parent = findNode(par, root);

        System.out.println("parent is = " + parent);
        System.out.println("newMember is = " + newMember + "\n");

        // If that parent doesn't exist, print error msg
        if (parent == null)
            System.out.println("Parent doesn't exist");


        // If parent does exist, but has no left child,
        // then the new member becomes left child
        else if(parent.leftChild == null)   
            parent.leftChild = newMember;


        // If parent already has a left child, then traverse
        // to the end of it's left children and insert node
        else
        {
            current = parent.leftChild;

            while(current.rightChild != null)
                current = current.rightChild;               

            current.rightChild = newMember;
        }   
    }
}


// ------------------------------------------------------------
// This method recursively finds a node in the family tree,
// given the name of the node to look for, and the tree.
// It is run pre-order, and, if found, returns the node
// ------------------------------------------------------------

public Node findNode(String name, Node localTree)
{
    Node current = localTree;

    // Visit the node
    if(current.name == name)
        return current;

    // Pre-order - go left
    if(current.leftChild != null)
    {
        System.out.println("going left to " + current.leftChild);
        return findNode(name, current.leftChild);
    }

    // Pre-order - go right
    if(current.rightChild != null)
    {
        System.out.println("going right to " + current.rightChild);
        return findNode(name, current.rightChild);
    }


    return null;
}

// ------------------------------------------------------------
// This method prints the family tree, given a parent name
// and a tree to print from. It will attempt to find the parent
// node with the given name, then print the entire tree 
// (all children and grandchildren) from that point.
// ------------------------------------------------------------

public void printTree(String par, Node localTree)
{
    Node parent, current;

    // Find the parent to start printing from
    parent = findNode(par, root);
    System.out.println("parent= " + parent);

    // If parent doesn't exist, print error msg
    if (parent == null)
        System.out.println(par + " doesn't exist.");

    else
    {
        current = localTree;

        System.out.println(current);

        if(current.leftChild != null)
            printTree(par, current.leftChild);

        else if(current.rightChild != null)
            printTree(par, current.rightChild);
    }

}

public class Node
{
    Node leftChild, rightChild;
    String name;

    public Node(String n)
    {
        leftChild = null;
        rightChild = null;
        name = n;
    }

    public String toString()
    {
        return name;
    }
}

}

public class Main
{
public static void main (String[] args)
{
    FamilyTree myTree = new FamilyTree();

    myTree.insertNode("", "Grandma Marx");
    myTree.insertNode("", "Great-Aunt Peggie");
    myTree.insertNode("", "Great-Aunt Katherine");
    myTree.insertNode("Grandma Marx", "Aunt Sarah");
    myTree.insertNode("Grandma Marx", "Aunt Tory");
    myTree.insertNode("Grandma Marx", "Uncle Frank");
    myTree.insertNode("Grandma Marx", "Uncle Charles");
    myTree.insertNode("Grandma Marx", "Mom");       

    myTree.insertNode("Aunt Sarah", "Morgan");
    myTree.insertNode("Aunt Sarah", "Tommy");
    myTree.insertNode("Aunt Sarah", "Austin");
    myTree.insertNode("Aunt Sarah", "Luke");

    myTree.insertNode("Aunt Tory", "Tim");

    myTree.insertNode("Mom", "Barret");
    myTree.insertNode("Mom", "Jeremy");
    myTree.insertNode("Mom", "Elliot");


    //myTree.printTree("Grandma Marx", myTree.findNode("Grandma Marx", myTree.root));
}

}

Answer 1

Проблема с твоим преждевременным return из поиска:

public Node findNode(String name, Node localTree)
{
...
    // Pre-order - go left
    if(current.leftChild != null)
    {
        System.out.println("going left to " + current.leftChild);
        return findNode(name, current.leftChild); // <===== HERE!
    }
...
}

Это приводит к завершению функции после прохождения левого поддерева, даже если результат nullне найдено ни одного узла.

Как насчет чего-то вроде этого:

public Node findNode(String name, Node localTree)
{
    Node current = localTree;

    // Visit the node
    if(current.name.equals(name))
        return current;

    // Pre-order - go left
    if(current.leftChild != null)
    {
        System.out.println("going left to " + current.leftChild);
        Node nodeFound = findNode(name, current.leftChild);
        if ( nodeFound != null ) {
          // Only return from findNode if we have already found what we're looking for.
          return nodeFound;
        }
    }

    // Pre-order - go right
    if(current.rightChild != null)
    {
        System.out.println("going right to " + current.rightChild);
        return findNode(name, current.rightChild);
    }

    return null;
}

Кроме того, в Java вы никогда не должны использовать == сравнить строки. Это не будет работать правильно. Со строками всегда используйте String.equals(...), См. Код выше, например, и этот вопрос ТАК.