0
好的，教授希望我爲我的TreeSet類實現get方法。他給我的算法爲指針，實現get方法：指導實施TreeSet的get方法。 （作業）
GET（K）
從樹根開始，令M是節點的左子樹 的數量。
（1）如果M等於k-1，那麼根就是你要找的節點。 （2）如果M小於k，那麼你正在尋找的節點必須在 右子樹中。當我們移動到右側子樹時，我們必須從 減去M + 1。現在右子樹成爲新的根，並且你重複這個過程。
（3）如果M大於k，則必須檢查左邊 子樹中的節點。
我試着用遞歸和迭代的方式實現這個方法（我不知道如何拼寫它）。這裏是低於整個類代碼：
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.TreeSet;
import sun.misc.Queue;
/**
* Binary Search Tree that inherits from the TreeSet class
* The class is based on Weiss's non-generic implementation of BinarySearchTree
*
* @author Daniel
* @param <T>
*/
public class BinarySearchTree<T extends Comparable<T>> extends TreeSet<T> implements Iterable<T>
{
/**
* Construct the tree.
*/
public BinarySearchTree()
{
root = null;
}
@Override
public boolean add(T e)
{
insert(e);
return true;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert(Comparable x)
{
{
root = insert(x, root);
}
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove(Comparable<T> x)
{
root = remove(x, root);
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin()
{
return elementAt(findMin(root));
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public Comparable findMax()
{
return elementAt(findMax(root));
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find(Comparable x)
{
return elementAt(find(x, root));
}
/**
* Make the tree logically empty.
*/
public void makeEmpty()
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty()
{
return root == null;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree()
{
if(isEmpty())
System.out.println("Empty tree");
else
printTree(root);
}
/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt(BinaryNode t)
{
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
*/
private BinaryNode insert(Comparable<T> x, BinaryNode<T> t)
{
/* 1*/ if(t == null)
{
/* 2*/ t = new BinaryNode(x, null, null);
t.parent = null;
if (t.left != null)
t.left.parent = t;
if (t.right != null)
t.right.parent = t;
}
/* 3*/ else if(x.compareTo((T)t.element) < 0)
{
/* 4*/ t.left = insert(x, t.left);
t.left_count++;
t.left.parent = t;
}
/* 5*/ else if(x.compareTo((T) t.element) > 0)
{
/* 6*/ t.right = insert(x, t.right);
t.right.parent = t;
}
/* 7*/ else
/* 8*/ ; // Duplicate; do nothing
/* 9*/ return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
*/
private BinaryNode remove(Comparable<T> x, BinaryNode<T> t)
{
if(t == null)
return t; // Item not found; do nothing
if(x.compareTo((T)t.element) < 0)
{
t.left = remove(x, t.left);
}
else if(x.compareTo((T)t.element) > 0)
{
t.right = remove(x, t.right);
}
else if(t.left != null && t.right != null) // Two children
{
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
}
else
t = (t.left != null) ? t.left : t.right;
if (t != null)
{
if (t.left != null)
t.left.parent = t;
if (t.right != null)
t.right.parent = t;
}
return t;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private BinaryNode<T> findMin(BinaryNode<T> t)
{
if(t == null)
return null;
else if(t.left == null)
return t;
return findMin(t.left);
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode<T> findMax(BinaryNode<T> t)
{
if(t != null)
while(t.right != null)
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find(Comparable<T> x, BinaryNode<T> t)
{
if(t == null)
return null;
if(x.compareTo((T)t.element) < 0)
return find(x, t.left);
else if(x.compareTo((T)t.element) > 0)
return find(x, t.right);
else
return t; // Match
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree(BinaryNode<T> t)
{
if(t != null)
{
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
@Deprecated
//Updates nodes current parent
// Unfortunaetly to expensive as it is O(N) algorithm.
// Therefore it sadly didn't make the final cut and is a deprecated method can be removed in the near future.
private void update(BinaryNode<T> t)
{
if (t != null)
{
if (t.left != null)
t.left.parent = t;
if (t.right != null)
t.right.parent = t;
update(t.left);
update(t.right);
}
}
/**
* Returns an iterator pointing just before the
* item in the tree with the lowest value.
*
**/
public Iterator<T> iterator()
{
return new MyIterator();
}
/**
* Returns the element at a given index position.
* Throws an IndexOutOfBoundsException if the item is not found.
* Runs in average O(log N) time.
*/
public T get(int index)
{
return get(root, index);
}
private T get(BinaryNode<T> root, int index)
{
if (root == null) return null;
if (root.left_count == index-1) return (T)root.element;
if (root.left_count < index) return get(root.right, index - (root.left_count + 1));
else
{
return get(root.left, index);
}
}
/**
* Returns all elements falling within a range of indexes.
* The range is inclusive
*/
public Collection<T> getRange(int first, int last)
{
ArrayList<T> list = new ArrayList<>();
for(int i = first; i <= last; i++)
{
list.add(get(i));
}
return list;
}
/**
* Prints the tree in level-order, which means the root is printed,
* then all nodes at level 2, then nodes at level 3, and so on.
*/
public void printLevelOrder() throws InterruptedException
{
Queue Q = new Queue();
Q.enqueue(root);
while(!Q.isEmpty())
{
BinaryNode<T> node = (BinaryNode<T>)Q.dequeue();
System.out.print(node.element + ",");
if (node.left != null)
Q.enqueue(node.left);
if (node.right != null)
Q.enqueue(node.right);
}
System.out.println();
}
private class MyIterator implements Iterator<T>
{
private BinaryNode<T> nextNode = null;
private boolean firstCall;
public MyIterator()
{
nextNode = BinarySearchTree.this.findMin(root);
firstCall = true;
}
@Override
public boolean hasNext()
{
return !nextNode.equals(BinarySearchTree.this.findMax(root));
}
@Override
public T next()
{
if (firstCall)
{
firstCall = false;
return (T)nextNode.element;
}
if (!hasNext())
throw new IndexOutOfBoundsException("Cannot manke another next() call!!!!?!");
BinaryNode<T> node = successor(nextNode);
nextNode = node;
return (T)node.element;
}
@Override
public void remove()
{
BinarySearchTree.this.remove(nextNode.element);
}
/**
* Returns the next value in the sequence, starting at the
* node pointed to by the input parameter. This method
* is used by the iterator.
*/
private BinaryNode<T> successor(BinaryNode<T> p)
{
BinaryNode<T> n = p.right;
if (n != null)
{
return BinarySearchTree.this.findMin(n);
}
else
{
n = p.parent;
while(n != null && p == n.right)
{
p = n;
n = n.parent;
}
return n;
}
}
}
/** The tree root. */
private BinaryNode<T> root;
public static void main(String[] arguments) throws InterruptedException
{
BinarySearchTree<String> t = new BinarySearchTree<>();
String[] array = { "Harry","Maria","Bob","Dan","Sue","Ann","Jose" };
for(int i = 0; i < array.length; i++)
t.insert(array[i]);
print(t);
System.out.print("Level order: ");
t.printLevelOrder();
System.out.println("\n");
System.out.printf("The value at index %d is %s\n", 0, t.get(0));
System.out.printf("The value at index %d is %s\n", 2, t.get(2));
System.out.printf("The value at index %d is %s\n", 6, t.get(6));
System.out.print("\nRemoving ");
for(int i = 1; i < array.length; i+= 2) {
System.out.print(array[i] + ", ");
t.remove(array[i]);
}
System.out.println();
System.out.println("\nTree contents after removing elements:");
print(t);
// verify that the get method still works
System.out.printf("The value at index %d is %s\n", 0, t.get(0));
System.out.printf("The value at index %d is %s\n", 2, t.get(2));
System.out.printf("The value at index %d is %s\n", 3, t.get(3));
}
public static void print(BinarySearchTree<? extends Comparable<?>> t)
{
for(Object x : t)
System.out.print(x + ", ");
System.out.println("\n");
}
private static void test1() throws InterruptedException
{
BinarySearchTree<Integer> t = new BinarySearchTree<>();
int[] array = { 20, 10, 11, 30, 2, 29, 33, 28, 17, 4 };
for(int i = 0; i < array.length; i++)
t.add(array[i]);
print(t); // demonstrate the iterator
System.out.println("Level order");
t.printLevelOrder();
System.out.printf("The value at index %d is %d\n", 0, t.get(0));
System.out.printf("The value at index %d is %d\n", 1, t.get(1));
System.out.printf("The value at index %d is %d\n", 2, t.get(2));
System.out.printf("The value at index %d is %d\n", 3, t.get(3));
System.out.printf("The value at index %d is %d\n", 8, t.get(8));
System.out.printf("The value at index %d is %d\n", 9, t.get(9));
System.out.print("\nRemoving ");
for(int i = 1; i < array.length; i+= 2) {
System.out.print(array[i] + ", ");
t.remove(array[i]);
}
System.out.println();
System.out.println("\nTree contents after removing elements:");
print(t);
// verify that the get method still works
System.out.printf("The value at index %d is %d\n", 0, t.get(0));
System.out.printf("The value at index %d is %d\n", 1, t.get(1));
System.out.printf("The value at index %d is %d\n", 2, t.get(2));
System.out.printf("The value at index %d is %d\n", 3, t.get(3));
}
}
這裏是get方法的代碼：
/**
* Returns the element at a given index position.
* Throws an IndexOutOfBoundsException if the item is not found.
* Runs in average O(log N) time.
*/
public T get(int index)
{
return get(root, index);
}
private T get(BinaryNode<T> root, int index)
{
if (root == null) return null;
if (root.left_count == index-1) return (T)root.element;
if (root.left_count < index) return get(root.right, index - (root.left_count + 1));
else
{
return get(root.left, index);
}
}
這裏是不正確的輸出：
安，鮑勃，丹皮，哈里，Jose，Maria，Sue，
級別：Harry，Bob，Maria，Ann，Dan，Jose，Sue，
值在索引0處爲空 在索引2的值是Bob 在索引6的值是瑪利亞
卸下超羣，丹，安，
移除元素之後樹內容：鮑勃，哈利，聖何塞，蘇，
索引爲0的值是零，在指數2的值是鮑勃 指數3爲空
正如你可以看到指數值有一堆空的，並在有效的元素。其他一切正確輸出。所以得到是100％失敗，因爲我已經寫了最初使用一種天真的方法。但教授希望它是O（log（N））。
由於這是一項家庭作業，對於我的數據結構課程，請避免給出完整的工作代碼。我想要的只是一些指導，我知道這是錯誤的（從輸出中判斷），但我不明白爲什麼。我也還沒有完全理解算法，這使得我更難調試代碼。我假設node.left_count是正確的（但可能是錯誤的），所以我相信這個錯誤在get方法中。因爲我可能會誤解某些算法。
更新如果我改變這一點，如果（root.left_count ==索引-1）返回（T）根。元件;到這個 if（root.left_count == index）return（T）root.element;
我得到這樣的輸出：
Ann, Bob, Dan, Harry, Jose, Maria, Sue, Level order: Harry,Bob,Maria,Ann,Dan,Jose,Sue, The value at index 0 is Ann The value at index 2 is Dan The value at index 6 is Sue Removing Maria, Dan, Ann, Tree contents after removing elements: Bob, Harry, Jose, Sue, The value at index 0 is null The value at index 2 is null The value at index 3 is Harry
你貼絕望太多的代碼。請將其縮小爲[最小，完整，測試和可讀示例]（http://stackoverflow.com/help/mcve）。 – Dukeling
@Dukeling它已經過測試，它如何可能無法讀取？有很多有用的評論。相信我，我不是新來的，因爲你可以從我的個人資料中看到，所以不要以爲我是新人。我甚至給出了最有可能解決問題的方法。包括輸出並指出我最可能的問題是什麼。那麼爲什麼你打算關閉它？問題不是模糊的，我的解釋也不是。如果你想要我添加一些東西，請更具體。但只是說你張貼到很多代碼是你的一部分含糊不清。 –
你怎麼說你發佈了太多的代碼含糊不清？你有500多行代碼。在我的書中，這太無望了（好吧，高於50-200的任何東西，除外）。我並不認爲你是新人，但事實是你不關心我。我真的不打算通過你的所有代碼，並指出哪些事情與你的問題無關，你可以用什麼代替它們，因爲，那樣就會打破這個觀點，即 - 我不想在一個問題中處理（或查看）500多行代碼，並且我認爲使用這麼多代碼的問題對於該網站來說不是好事。 – Dukeling