재귀 적 접근을 사용하는 이진 트리 구현

Question

프로젝트 : "장에서 소개 한 재귀 적 접근법을 사용하여 이진 트리의 구현 만들기이 방법에서는 각 노드가 이진 트리입니다. 따라서 이진 트리에는 요소에 대한 참조가 포함되어 있습니다 루트에 저장 될뿐만 아니라 왼쪽 및 오른쪽 하위 트리에 대한 참조가 포함됩니다. 또한 부모에 대한 참조를 포함 할 수도 있습니다. "

질문 :이 장에서는 이진 트리 구현 (아래 코드 참조)을 제공하며이 프로젝트에서 저의 책에서 구현이 다르게 수행되기를 원하는지 잘 모르겠습니다. 내가 볼 수있는 몇 가지 방법과 같은 몇 가지 누락 된 세부 정보를 작성하고 또한 부모 참조를 추가하는 것입니다. 이게 그것이 묻는 것이 아니지만 나는 최종 프로젝트로 알고 있습니다. `

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

재귀 여기에 그들이 당신의 이진 트리 구현이 자체 참조 할 것을 의미합니다

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() { } 
} 

`

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(); 
} 

. 즉, 북 예제와 같이 노드가 왼쪽 및 오른쪽 노드를 참조하는 대신 왼쪽 및 오른쪽 BinaryTree 하위 트리를 참조하는 트리 자체와 루트 요소에 대한 참조를 갖게됩니다. 당신이 당신의 지시에 보면

는,이 책의 구현이 Node 클래스 갖는 getRight() 및 getLeft() 등에 의존하면서 나무 자체가, 그 왼쪽과 오른쪽 서브 트리,뿐만 아니라 요소에 대한 참조를 가지고 있다고 알 행동 양식.