java - 使用递归方法实现二叉树

Question

项目:“使用本章中介绍的递归方法创建二叉树的实现。在这种方法中，每个节点都是一棵二叉树。因此，二叉树包含对其根存储的元素的引用以及对其左子树和右子树的引用。您可能还想包含对其父树的引用。”

问题:在本章中，他们给出了一个二叉树实现(代码如下所示)，我不确定这个项目希望我做哪些与书中实现不同的事情。我所能看到的只是填写一些缺失的细节，例如一些方法，并添加父引用。我知道这是一个最终项目，尽管这不是它所要求的。

Binary Tree Class:
`
//*******************************************************************
// BinaryTree.java Java Foundations
//
// Defines the interface to a binary tree collection.
//*******************************************************************
package javafoundations;
import java.util.Iterator;
public interface BinaryTree<T> extends Iterable<T>
{
    // Returns the element stored in the root of the tree.
    public T getRootElement();
    // Returns the left subtree of the root.
    public BinaryTree<T> getLeft();
    // Returns the right subtree of the root.
    public BinaryTree<T> getRight();
    // Returns true if the binary tree contains an element that
    // matches the specified element and false otherwise.
    public boolean contains (T target);
    // Returns a reference to the element in the tree matching
    // the specified target.
    public T find (T target);
    // Returns true if the binary tree contains no elements, and
    // false otherwise.
    public boolean isEmpty();
    // Returns the number of elements in this binary tree.
    public int size();
    // Returns the string representation of the binary tree.
    public String toString();
    // Returns a preorder traversal on the binary tree.
    public Iterator<T> preorder();
    // Returns an inorder traversal on the binary tree.
    public Iterator<T> inorder();
    // Returns a postorder traversal on the binary tree.
    public Iterator<T> postorder();
    // Performs a level-order traversal on the binary tree.
    public Iterator<T> levelorder(); 
}  

`

LinkedBinaryTree class:
`
//*******************************************************************
// LinkedBinaryTree.java Java Foundations
//
// Implements a binary tree using a linked representation.
//*******************************************************************
package javafoundations;
import java.util.Iterator;
import javafoundations.*;
import javafoundations.exceptions.*;
public class LinkedBinaryTree<T> implements BinaryTree<T>
{
    protected BTNode<T> root;
    //-----------------------------------------------------------------
    // Creates an empty binary tree.
    //-----------------------------------------------------------------
    public LinkedBinaryTree()
    {
        root = null;
    }
    //-----------------------------------------------------------------
    // Creates a binary tree with the specified element as its root.
    //-----------------------------------------------------------------
    public LinkedBinaryTree (T element)
    {
        root = new BTNode<T>(element);
    }
    //-----------------------------------------------------------------
    // Creates a binary tree with the two specified subtrees.
    //-----------------------------------------------------------------
    public LinkedBinaryTree (T element, LinkedBinaryTree<T> left,
    LinkedBinaryTree<T> right)
    {
        root = new BTNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
    }
    //-----------------------------------------------------------------
    // Returns the element stored in the root of the tree. Throws an
    // EmptyCollectionException if the tree is empty.
    //-----------------------------------------------------------------
    public T getRootElement()
    {
        if (root == null)
            throw new EmptyCollectionException 
            ("Get root operation " + "failed. The tree is empty.");
        return root.getElement();
    }
    //-----------------------------------------------------------------
    // Returns the left subtree of the root of this tree.
    //-----------------------------------------------------------------
    public LinkedBinaryTree<T> getLeft()
    {
        if (root == null)
            throw new EmptyCollectionException 
                      ("Get left operation " + "failed. The tree is empty.");
        LinkedBinaryTree<T> result = new LinkedBinaryTree<T>();
        result.root = root.getLeft();
        return result;
    }
    //-----------------------------------------------------------------
    // Returns the element in this binary tree that matches the
    // specified target. Throws a ElementNotFoundException if the
    // target is not found.
    //-----------------------------------------------------------------
    public T find (T target)
    {
        BTNode<T> node = null;
        if (root != null)
            node = root.find(target);
        if (node == null)
            throw new ElementNotFoundException
               ("Find operation failed. " + "No such element in tree.");
        return node.getElement();
    }
    //-----------------------------------------------------------------
    // Returns the number of elements in this binary tree.
    //-----------------------------------------------------------------
    public int size()
    {
        int result = 0;
        if (root != null)
            result = root.count();
        return result;
    }
    //-----------------------------------------------------------------
    // Populates and returns an iterator containing the elements in
    // this binary tree using an inorder traversal.
    //-----------------------------------------------------------------
    public Iterator<T> inorder()
    {
        ArrayIterator<T> iter = new ArrayIterator<T>();
        if (root != null)
            root.inorder (iter);
        return iter;
    }
    //-----------------------------------------------------------------
    // Populates and returns an iterator containing the elements in
    // this binary tree using a levelorder traversal.
    //-----------------------------------------------------------------
    public Iterator<T> levelorder()
    {
        LinkedQueue<BTNode<T>> queue = new LinkedQueue<BTNode<T>>();
        ArrayIterator<T> iter = new ArrayIterator<T>();
        if (root != null)
        {
            queue.enqueue(root);
            while (!queue.isEmpty())
            {
                BTNode<T> current = queue.dequeue();
                iter.add (current.getElement());
                if (current.getLeft() != null)
                    queue.enqueue(current.getLeft());
                if (current.getRight() != null)
                    queue.enqueue(current.getRight());
            }
        }
        return iter;
    }
    //-----------------------------------------------------------------
    // Satisfies the Iterable interface using an inorder traversal.
    //-----------------------------------------------------------------
    public Iterator<T> iterator()
    {
        return inorder();
    }
    //-----------------------------------------------------------------
    // The following methods are left as programming projects.
    //-----------------------------------------------------------------
    // public LinkedBinaryTree<T> getRight() { }
    // public boolean contains (T target) { }
    // public boolean isEmpty() { }
    // public String toString() { }
    // public Iterator<T> preorder() { }
    // public Iterator<T> postorder() { }
}

`

BTNode class:
`
//*******************************************************************
// BTNode.java Java Foundations
//
// Represents a node in a binary tree with a left and right child.
// Therefore this class also represents the root of a subtree.
//*******************************************************************
package javafoundations;
public class BTNode<T>
{       
    protected T element;
    protected BTNode<T> left, right;
    //-----------------------------------------------------------------
    // Creates a new tree node with the specified data.
    //-----------------------------------------------------------------
    public BTNode (T element)
    {
        this.element = element;
        left = right = null;
    }
    //-----------------------------------------------------------------
    // Returns the element stored in this node.
    //-----------------------------------------------------------------
    public T getElement()
    {
        return element;
    }
    //----------------------------------------------------------------- 
    // Sets the element stored in this node.
    //-----------------------------------------------------------------
    public void setElement (T element)
    {
        this.element = element;
    }
    //-----------------------------------------------------------------
    // Returns the left subtree of this node.
    //-----------------------------------------------------------------
    public BTNode<T> getLeft()
    {
        return left;
    }
    //-----------------------------------------------------------------
    // Sets the left child of this node.
    //-----------------------------------------------------------------
    public void setLeft (BTNode<T> left)
    {
        this.left = left;
    }
    //-----------------------------------------------------------------
    // Returns the right subtree of this node.
    //-----------------------------------------------------------------
    public BTNode<T> getRight()
    {
        return right;
    }
    //-----------------------------------------------------------------
    // Sets the right child of this node.
    //-----------------------------------------------------------------
    public void setRight (BTNode<T> right)
    {
        this.right = right;
    }
    //-----------------------------------------------------------------
    // Returns the element in this subtree that matches the
    // specified target. Returns null if the target is not found.
    //-----------------------------------------------------------------
    public BTNode<T> find (T target)
    {
        BTNode<T> result = null;
        if (element.equals(target))
            result = this;
        else
        {
            if (left != null)
                result = left.find(target);
            if (result == null && right != null)
                result = right.find(target);
        }
        return result;
    }
    //-----------------------------------------------------------------
    // Returns the number of nodes in this subtree.
    //-----------------------------------------------------------------
    public int count()
    {
        int result = 1;
        if (left != null)
            result += left.count();
        if (right != null)
            result += right.count();
        return result;
    }
    //-----------------------------------------------------------------
    // Performs an inorder traversal on this subtree, updating the
    // specified iterator.
    //-----------------------------------------------------------------
    public void inorder (ArrayIterator<T> iter)
    {
        if (left != null)
            left.inorder (iter);
        iter.add (element);
        if (right != null)
            right.inorder (iter);
    }
    //-----------------------------------------------------------------
    // The following methods are left as programming projects.
    //-----------------------------------------------------------------
    // public void preorder(ArrayIterator<T> iter) { }
    // public void postorder(ArrayIterator<T> iter) { }
}

`

Answer 1

这里的递归意味着他们希望您的二叉树实现是自引用的。这意味着，您将让树本身引用左右 BinaryTree 子树，然后引用其根元素，而不是像书中示例那样让节点引用其左节点和右节点。

如果您查看说明，请注意它说树本身具有对其左子树和右子树及其元素的引用，而本书的实现依赖于具有以下属性的 Node 类: getRight() 和 getLeft() 等方法。