在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; 
}