0

我试图为树遍历实现迭代器接口。我收到以下错误。“for(Integer node : tr) 的不兼容类型”和“treeIterator.java 使用未经检查或不安全的操作。” 我无法修复此错误。有人可以指出问题所在。

//class to implement the Iterator interace.
class InorderItr implements Iterator {



    public InorderItr(Node root) {
       st = new Stack<Node>();
       this.root = root;
    }

    @Override
    public boolean hasNext() {
        //has Next
    }

    @Override
    public Integer next(){
          //next node
    }

    @Override 
    public void remove(){
        throw new java.lang.UnsupportedOperationException("Remove not supported.");
    }
}

//This class just makes sure that we use the foreach loop.
class InorderTreeIterator implements Iterable {

    Node root = null;

    public InorderTreeIterator(Node root){
        this.root = root;
    }

    @Override
    public Iterator<Integer> iterator(){
        try{
            return new InorderItr(this.root);
        } catch(UnsupportedOperationException e){
            System.out.println(e.getMessage());
            return null;
        }
    }
}


class treeIterator {

    public static void main(String arg[]){
        treeIterator obj = new treeIterator();
        //create tree.
        InorderTreeIterator tr = new InorderTreeIterator(obj.root);
        for(Integer node : tr ){
            System.out.println(node);
        }
    }
}

PS：这是我第一次尝试实现迭代器接口。如果有任何我不遵循的标准做法，请指出。

谢谢你

4

4 回答 4

2

Iterable是一个通用接口。这意味着，除非您给它一个类型参数，否则它将是一个原始类型，并且基础数据将被视为Object.

改变这个：

class InorderItr implements Iterator
class InorderTreeIterator implements Iterable

到以下：

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

这样，它不再是原始类型（并且消除了编译器当前给您的未经检查和不安全操作的警告），并且它告诉编译器Iterator它将具有其基础数据类型Integer（因为类型参数在接口是它的Iterator底层数据类型），所以类型匹配。

于 2013-05-09T14:05:11.117 回答
0

在 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;
}
于 2014-11-11T13:22:40.840 回答
0

假设 Java 5 或更高版本： Iterator 实际上被声明为 Iterator，其中“E”代表 Iterator 上 next() 返回的类。我想你想要的是

InOrderIterator implements Iterator<Node>

并且 next() 应该被声明为

public Node next()

我不明白为什么你的代码中有 Integer；您显然是在尝试遍历 Node.js 的树。

于 2013-05-09T14:08:22.217 回答
0

迭代器是泛型类型。如果使用原始Iterator类型，迭代器返回对象，循环应该是

for (Object node : tr)

您应该改用类型安全的泛型Iterator<Integer>：

class InorderItr implements Iterator<Integer> {

...

class InorderTreeIterator implements Iterable<Integer> {

此外，为您的课程选择更好的名称。InorderItr应该是InOrderIterator。并且InorderTreeIterator应该是InorderTreeIterable。不要将不是迭代器的名称命名为“迭代器”。类名以大写字母开头，方法名以小写字母开头。

于 2013-05-09T14:06:24.383 回答