在Java中實現我自己的樹Iterator

Question

我試圖爲樹遍歷實現Iterator接口。我收到以下錯誤：「（Integer節點：tr）」和「treeIterator.java使用未經檢查或不安全的操作時，不兼容的類型」。我無法修復這個錯誤。有人可以指出這個問題。 PS：這是我第一次嘗試實現迭代器接口。這是我第一次嘗試實現迭代器接口。如果有任何我不遵循的標準做法，請指出。

謝謝

Answer 1

Iterable是一個generic接口。這意味着，除非您給它一個類型參數，否則它將是一個原始類型，並且基礎數據將被視爲Object。

更改此：

class InorderItr implements Iterator 
class InorderTreeIterator implements Iterable 

以下幾點：

class InorderItr implements Iterator<Integer> 
class InorderTreeIterator implements Iterable<Integer> 

這種方式，它不再是一個原始類型（以及獲得的未經檢查的警告和不安全的操作的編譯器的RID它會告訴編譯器Iterator的基礎數據類型爲Integer（因爲Iterator接口中的類型參數是其基礎數據類型），因此類型匹配。

Answer 2

迭代器是泛型類型。如果您使用原始Iterator類型，迭代器返回的對象，並且循環應該是

for (Object node : tr) 

你應該使用類型安全的通用Iterator<Integer>：

class InorderItr implements Iterator<Integer> { 

... 

class InorderTreeIterator implements Iterable<Integer> { 

此外，選擇更好的名稱您類。 InorderItr應該是InOrderIterator。而InorderTreeIterator應該是InorderTreeIterable。不要將「迭代器」命名爲什麼不是迭代器。用大寫字母開始類名，用小寫字母開始方法名。

Answer 3

假設Java 5或更高版本：Iterator實際上聲明爲Iterator，其中「E」表示Iterator上的next（）返回的類。我想你想要的是

InOrderIterator implements Iterator<Node> 

和next（）應被聲明爲

public Node next() 

我不明白你爲什麼在你的代碼有整數;你顯然正在嘗試迭代Node的一棵樹。

Answer 4

在太空中的C（有點）實現++

#include<iostream> 
using namespace std; 
struct node 
{ 
    node *left; 
    node *right; 
    node *parent; 
    int data; 
} ; 

class bst 
{ 
public: 
    node *root; 
    node *currNode; 

    bst() 
    { 
     root=NULL; 
     currNode = NULL; 
    } 
    int isempty() 
    { 
     return(root==NULL); 
    } 
    void insert(int item); 
    void inordertrav(); 
    void inorder(node *); 
    int next(); 
    node *nextNode(node *root); 
    void bft(); 
}; 
void bst::insert(int item) 
{ 
    node *p=new node; 
    node *parent; 
    p->data=item; 
    p->left=NULL; 
    p->right=NULL; 
    p->parent = NULL; 
    parent=NULL; 
    if(isempty()) 
     root=p; 
    else 
    { 
     node *ptr; 
     ptr = root; 
     while(ptr!=NULL) 
     { 
      parent = ptr; 
      if(item > ptr->data)   
       ptr = ptr->right; 
      else 
       ptr=ptr->left; 
     } 
     if(item < parent->data) 
     { 
      parent->left = p; 
     } 
     else 
      parent->right = p; 
     p->parent = parent; 
    } 
} 
void bst::inordertrav() 
{ 
    inorder(root); 
} 
void bst::inorder(node *ptr) 
{ 
    if(ptr!=NULL) 
    { 
     inorder(ptr->left); 
     cout<<" "<<ptr->data<<"  "; 
     inorder(ptr->right); 
    } 
} 

int bst::next() 
{ 
// If currNode is NULL and find the left most node using a while loop. 
    if (currNode == NULL) 
    { 
     cout << "First node data" << endl; 
     node *tmp = root; 
     while (tmp->left != NULL) 
      tmp = tmp->left; 

     currNode = tmp; 
     return currNode->data; 
    } 
    cout << endl << "Current Node is - " << currNode->data << endl; 
    if (currNode->right) 
    { 
     node *tmp = currNode->right; 
     while (tmp->left) // find the leftmost node for this right subtree in recursive way without recursion 
      tmp = tmp->left; 
     currNode = tmp; 
     return currNode->data; 
    } 

    if (! currNode->right) // currNode does not have right child 
    { 
     if (currNode->parent->left && currNode->data == currNode->parent->left->data) // CurrNode is the left child 
     { 
      currNode = currNode->parent; 
      return currNode->data; 
     } 
     if (currNode->parent->right && currNode->data == currNode->parent->right->data) //CurrNode is the right child of the parent 
     { 
      //If the parent of the currNode (which is right child) is also a right child 
      //then this currNode is actually a leaf node and it nothing should be returned. 
      if (currNode->parent->parent->right && 
        currNode->parent->parent->right->data == currNode->parent->data) 
      { 
       cout << "The tree has been travered fully"; 
       return -1; 
      } 
      currNode = currNode->parent->parent; 
      return currNode->data; 
     } 
    } 
} 


int main() 
{ 
    bst b; 
    b.insert(52); 
    b.insert(25); 
    b.insert(50); 
    b.insert(40); 
    b.insert(45); 
    b.insert(20); 
    b.insert(75); 
    b.insert(65); 
    b.insert(78); 
    b.insert(23); 
    b.insert(15); 

    cout << "---- In order traversal using iterator -----" << endl; 
    int i; 
    do 
    { 
     i = b.next(); 
     cout << " " << i << " "; 
    }while (i != -1); 
    cout << endl; 
    cout<<endl; 
}