이진 검색 트리에서 노드에 액세스

Question

BST를 만들고 값을 추가했습니다. 그러나 그것들은 TreeNode를 매개 변수로 요구하는 메소드입니다. 값이 트리에 추가 된 후 "10"과 같은 매개 변수를 전달할 때 이는 유효한 매개 변수가 아닙니다. 그것을 param으로 요구하는 메소드에 param을 전달하려면 어떻게해야합니까? 예를 들어, 내가 작성한 메소드는 검색중인 노드를 알아야 할 필요가 있으므로 treenode param이 필요합니다. 내가 값을 전달한 후에 트리에 삽입했습니다. (이전에 "10"을 시연 했으므로 유효한 param이 아닙니다. 노드에 추가 된 이후 유효한 param이 아닌 이유를 이해할 수 없습니다. 그들이 와서 어떻게의 TreeNode에서 PARAMS

이러한 방법 중 하나에 문자열을 전달하는 경우는 말한다 :.. 유형 BST의 방법 전순 (BST.TreeNode)는 인수 (문자열) 적용 할 수 없습니다

public class BST<E extends Comparable<E>> { 
    int height = 0; 
    protected TreeNode<E> root; 
    protected int size = 0; 

    /** Create a default binary tree */ 
    public BST() { 
    } 

    /** Create a binary tree from an array of objects */ 
    public BST(E[] objects) { 
    for (int i = 0; i < objects.length; i++) 
     insert(objects[i]); 
    } 

    /** Returns true if the element is in the tree */ 
    public boolean search(E e) { 
    TreeNode<E> current = root; // Start from the root 

    while (current != null) { 
     if (e.compareTo(current.element) < 0) { 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     current = current.right; 
     } 
     else // element matches current.element 
     return true; // Element is found 
    } 

    return false; 
    } 

    /** Insert element o into the binary tree 
    * Return true if the element is inserted successfully */ 
    public boolean insert(E e) { 
    if (root == null) 
     root = createNewNode(e); // Create a new root 
    else { 
     // Locate the parent node 
     TreeNode<E> parent = null; 
     TreeNode<E> current = root; 
     while (current != null) 
     if (e.compareTo(current.element) < 0) { 
      parent = current; 
      current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
      parent = current; 
      current = current.right; 
     } 
     else 
      return false; // Duplicate node not inserted 

     // Create the new node and attach it to the parent node 
     if (e.compareTo(parent.element) < 0) 
     parent.left = createNewNode(e); 
     else 
     parent.right = createNewNode(e); 
    } 

    size++; 
    return true; // Element inserted 
    } 

    protected TreeNode<E> createNewNode(E e) { 
    return new TreeNode<E>(e); 
    } 

    /** Inorder traversal from the root*/ 
    public void inorder() { 
    inorder(root); 
    } 

    /** Inorder traversal from a subtree */ 
    protected void inorder(TreeNode<E> root) { 
    if (root == null) return; 
    inorder(root.left); 
    System.out.print(root.element + " "); 
    inorder(root.right); 
    } 

    /** Postorder traversal from the root */ 
    public void postorder() { 
    postorder(root); 
    } 

    /** Postorder traversal from a subtree */ 
    protected void postorder(TreeNode<E> root) { 
    if (root == null) return; 
    postorder(root.left); 
    postorder(root.right); 
    System.out.print(root.element + " "); 
    } 

    /** Preorder traversal from the root */ 
    public void preorder() { 
    preorder(root); 
    } 

    /** Preorder traversal from a subtree */ 
    protected void preorder(TreeNode<E> root) { 
    if (root == null) return; 
    System.out.print(root.element + " "); 
    preorder(root.left); 
    preorder(root.right); 
    } 

    /** This inner class is static, because it does not access 
     any instance members defined in its outer class */ 
    public static class TreeNode<E extends Comparable<E>> { 
    protected E element; 
    protected TreeNode<E> left; 
    protected TreeNode<E> right; 

    public TreeNode(E e) { 
     element = e; 
    } 
    } 

    /** Get the number of nodes in the tree */ 
    public int getSize() { 
    return size; 
    } 

    /** Returns the root of the tree */ 
    public TreeNode<E> getRoot() { 
    return root; 
    } 

    /** Returns a path from the root leading to the specified element */ 
    public java.util.ArrayList<TreeNode<E>> path(E e) { 
    java.util.ArrayList<TreeNode<E>> list = 
     new java.util.ArrayList<TreeNode<E>>(); 
    TreeNode<E> current = root; // Start from the root 

    while (current != null) { 
     list.add(current); // Add the node to the list 
     if (e.compareTo(current.element) < 0) { 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     current = current.right; 
     } 
     else 
     break; 
    } 

    return list; // Return an array of nodes 
    } 

    /** Delete an element from the binary tree. 
    * Return true if the element is deleted successfully 
    * Return false if the element is not in the tree */ 
    public boolean delete(E e) { 
    // Locate the node to be deleted and also locate its parent node 
    TreeNode<E> parent = null; 
    TreeNode<E> current = root; 
    while (current != null) { 
     if (e.compareTo(current.element) < 0) { 
     parent = current; 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     parent = current; 
     current = current.right; 
     } 
     else 
     break; // Element is in the tree pointed at by current 
    } 

    if (current == null) 
     return false; // Element is not in the tree 

    // Case 1: current has no left children 
    if (current.left == null) { 
     // Connect the parent with the right child of the current node 
     if (parent == null) { 
     root = current.right; 
     } 
     else { 
     if (e.compareTo(parent.element) < 0) 
      parent.left = current.right; 
     else 
      parent.right = current.right; 
     } 
    } 
    else { 
     // Case 2: The current node has a left child 
     // Locate the rightmost node in the left subtree of 
     // the current node and also its parent 
     TreeNode<E> parentOfRightMost = current; 
     TreeNode<E> rightMost = current.left; 

     while (rightMost.right != null) { 
     parentOfRightMost = rightMost; 
     rightMost = rightMost.right; // Keep going to the right 
     } 

     // Replace the element in current by the element in rightMost 
     current.element = rightMost.element; 

     // Eliminate rightmost node 
     if (parentOfRightMost.right == rightMost) 
     parentOfRightMost.right = rightMost.left; 
     else 
     // Special case: parentOfRightMost == current 
     parentOfRightMost.left = rightMost.left;  
    } 

    size--; 
    return true; // Element inserted 
    } 

    /** Obtain an iterator. Use inorder. */ 
    public java.util.Iterator<E> iterator() { 
    return new InorderIterator(); 
    } 

    // Inner class InorderIterator 
    private class InorderIterator implements java.util.Iterator<E> { 
    // Store the elements in a list 
    private java.util.ArrayList<E> list = 
     new java.util.ArrayList<E>(); 
    private int current = 0; // Point to the current element in list 

    public InorderIterator() { 
     inorder(); // Traverse binary tree and store elements in list 
    } 

    /** Inorder traversal from the root*/ 
    private void inorder() { 
     inorder(root); 
    } 

    /** Inorder traversal from a subtree */ 
    private void inorder(TreeNode<E> root) { 
     if (root == null)return; 
     inorder(root.left); 
     list.add(root.element); 
     inorder(root.right); 
    } 

    /** More elements for traversing? */ 
    public boolean hasNext() { 
     if (current < list.size()) 
     return true; 

     return false; 
    } 

    /** Get the current element and move to the next */ 
    public E next() { 
     return list.get(current++); 
    } 

    /** Remove the current element */ 
    public void remove() { 
     delete(list.get(current)); // Delete the current element 
     list.clear(); // Clear the list 
     inorder(); // Rebuild the list 
    } 
    } 

    /** Remove all elements from the tree */ 
    public void clear() { 
    root = null; 
    size = 0; 
    } 

    public double treeHeight(){ 
     double level = this.getSize(); 
     if (level ==0) 
      return 0; 
     if (level < 2){ 
      return level; 
     } 
     if(level == 2){ 
      return 2; 
     } 
     else 
     while (level >= 2){ 
      height++; 
      level = level/2; 
     } 
    return height++; 
    } 

    public double numberOfNodeAtLevel(TreeNode node, double current,double desired){ 
     TreeNode<E> currentNode = root; 
     if (currentNode == null){ 
      return 0; 
     } 
     if (currentNode.equals(node)){ 
     return 1;} 

     else return numberOfNodeAtLevel(currentNode.left, current+1, desired)+ 
        numberOfNodeAtLevel(currentNode.right, current+1, desired); 


    } 





    public static void main(String[] args){ 
     BST <String> c = new BST<String>(); 
     c.insert("50"); 
     c.insert("25"); 
     c.insert("55"); 
     c.insert("13"); 
     c.insert("65"); 
     c.insert("10"); 
     c.insert("14"); 
     c.insert("54"); 

    numberOfNodeAtLevel("10",0,2) ; 
    c.preorder(); 


    } 
} 

Answer 1

메서드는 TreeNode 유형의 객체를 필요로하며 문자열을 전달합니다. 트리를 초기화 할 때 지정한 유형으로 호출하려면 generic 유형 E :

을 사용하십시오.

public double numberOfNodeAtLevel(TreeNode node, double current,double desired){ 
    TreeNode<E> currentNode = root; 
    if (currentNode == null){ 
     return 0; 
    } 
    if (currentNode.equals(node)){ 
     return 1; 
    } else { 
     return numberOfNodeAtLevel(currentNode.left, current+1, desired)+ 
       numberOfNodeAtLevel(currentNode.right, current+1, desired); 
    } 
} 

element이 비교되는 TreeNode 개체가 아닌 equals 메서드를 재정의하려고합니다. 이런 식으로 뭔가 :

public bool equals(Object obj) { 
    return this.element.equals(((TreeNode) obj).element); 
}