如何穿越N-Ary树 [英] How to Traverse a N-Ary Tree

问题描述

我的树/节点类：

import java.util.ArrayList;
import java.util.List;

public class Node<T> {
   private T data;
   private List<Node<T>> children;
   private Node<T> parent;

   public Node(T data) {
      this.data = data;
      this.children = new ArrayList<Node<T>>();
   }

   public Node(Node<T> node) {
      this.data = (T) node.getData();
      children = new ArrayList<Node<T>>();
   }

   public void addChild(Node<T> child) {
      child.setParent(this);
      children.add(child);
   }

   public T getData() {
      return this.data;
   }

   public void setData(T data) {
      this.data = data;
   }

   public Node<T> getParent() {
      return this.parent;
   }

   public void setParent(Node<T> parent) {
      this.parent = parent;
   }

   public List<Node<T>> getChildren() {
      return this.children;
   }
}

我知道如何遍历二叉树，但是遍历N-Ary似乎更棘手。

I know how to traverse a Binary Tree, but traversing a N-Ary seems much more tricky.

我将如何遍历这棵树。我想要一个计数器，同时我遍历树，以编号/计算树中的每个节点。

How would I go about traversing through this tree. I want a counter whilst I traverse the tree as to number/count each node in the tree.

然后在特定计数，我可以停止并返回该节点count（可能删除该子树或在该位置添加子树）。

Then at a specific count, I can stop and return the node at that count (perhaps remove that subtree or add a subtree at that position).

推荐答案

最简单的方法是实现一个访问者模式，如这个：

The simplest way is to implement a Visitor pattern like this:

public interface Visitor<T> {
    // returns true if visiting should be cancelled at this point
    boolean accept(Node<T> node);
}

public class Node<T> {
    ...

   // returns true if visiting was cancelled
   public boolean visit(Visitor<T> visitor) {
       if(visitor.accept(this))
           return true;
       for(Node<T> child : children) {
           if(child.visit(visitor))
               return true;
       }
       return false;
   }
}

现在你可以像这样使用它：

Now you can use it like this:

treeRoot.visit(new Visitor<Type>() {
    public boolean accept(Node<Type> node) {
        System.out.println("Visiting node "+node);
        return false;
    }
});

或者您的特定任务：

class CountVisitor<T> implements Visitor<T> {
    int limit;
    Node<T> node;

    public CountVisitor(int limit) {
        this.limit = limit;
    }

    public boolean accept(Node<T> node) {
        if(--limit == 0) {
            this.node = node;
            return true;
        }
        return false;
    }

    public Node<T> getNode() {
        return node;
    }
}

CountVisitor<T> visitor = new CountVisitor<>(10);
if(treeRoot.visit(visitor)) {
    System.out.println("Node#10 is "+visitor.getNode());
} else {
    System.out.println("Tree has less than 10 nodes");
}

这篇关于如何穿越N-Ary树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！