Двоичное дерево - Как пройти рекурсив без каких-либо параметров - PullRequest
Новая
       14

Двоичное дерево - Как пройти рекурсив без каких-либо параметров

0 голосов
/ 04 июня 2011

Я не знаю, как рекурсивно обходить данное двоичное дерево, просто используя следующие методы дерева.Например, у каждого TreeNode есть int Value и метод get TreeNode.getValue (), и теперь я хочу найти узел с максимальным значением в дереве.Обратите внимание, что у дерева есть только указатель на его текущий узел, и вы можете перейти к родительскому, правому, левому или корневому узлу.

Мой вопрос: 

Tree tree;

public int findMaxValue() {
    //how to implement this as recursive function
}

Класс дерева: 

/**
 * The abstract class for a tree.
 * @author JK, KM
 */
public abstract class Tree {

    /**
     * Moves to the left child of the current node
     * 
     * @return true if left child exists and the move was successful; otherwise
     *         false
     */
    public abstract boolean moveToLeftNode();

    /**
     * Moves to the right child of the current node
     * 
     * @return true if right child exists and the move was successful; otherwise
     *         false
     */
    public abstract boolean moveToRightNode();

    /**
     * Moves to the parent of the current node
     * 
     * @return true if parent exists and the move was successful; otherwise
     *         false
     */
    public abstract boolean moveToParentNode();

    /**
     * @return true if left child exists; otherwise false
     */
    public abstract boolean hasLeftNode();

    /**
     * @return true if right child exists; otherwise false
     */
    public abstract boolean hasRightNode();

    /**
     * @return true if parent exists; otherwise false
     */
    public abstract boolean hasParentNode();

    /**
     * Sets the left child of the current node
     * 
     * @return true if successful; otherwise false (no root set)
     * 
     */
    public abstract boolean setLeftNode(TreeNode node);

    /**
     * Sets the right child of the current node
     * 
     * @return true if successful; otherwise false (no root set)
     * 
     */
    public abstract boolean setRightNode(TreeNode node);

    /**
     * Sets the current node. If the tree is empty, sets the root.
     * 
     */
    public abstract void setCurrentNode(TreeNode node);

    /**
     * @return the current node or null if the tree is empty
     */
    public abstract TreeNode getCurrentNode();

    /**
     * moves to the root node of this tree
     * 
     * @return true if there's a root; otherwise false
     */
    public abstract boolean moveToRoot();

    /**
     * clears the whole tree, which includes deleting all nodes and the root
     * node
     */
    public abstract void clearTree();

1 Ответ

2 голосов
/ 04 июня 2011

Вы можете рекурсивно пройти через двоичное дерево следующим образом: 

public int findMaxValue() {
    return max(this.node.getValue(),
               this.getLeftChild().findMaxValue(),
               this.getRightChild().findMaxValue());
}

Реализация этого с учетом вашего интерфейса Tree и проверка на наличие конечных узлов оставлены в качестве упражнения.

...