K-树与Java中的对称搜索/访问

Question

我正在处理一个大问题:我几乎完成了我的一周年纪念项目，但现在我被困住了。

我需要创建一种方法(用java语言)来对称地访问ak-ary树(这是我的教授的话: k-ary树的对称访问是从第一个到(k/2)-th的对称访问子树，然后是根的访问，然后是从(k/2)-th到k-th的子树的对称访问(“访问节点”意味着访问其中包含的信息，“访问子树”指的是子树中所有节点的访问)。

我创建了两个类来实现k叉树:节点和树。

Node.java:

Field Summary:

List<Node<T>> children; //the children of the current node
T info; //property that the node contain
static int maxNrOfChildren; //equals to k-arity of the tree
Node<T> parent; //the parent of current node

Constructor Summary:
Node(T info) //creates a node containing some informations

Method Summary
void addChild(Node<T> childNode) //add a child to a node
void addChildAtIndex(Node<T> childNode, int index) //add a child to a node at a specific index
List<Node<T>> getChildren() //returns a list of the children of a node
T getInfo() //returns the informations contained in a node
void setInfo(T info) //set an information to a node
java.util.List<T> getInfoChildrenOfNode() //returns a list containing all the infos conitaned in the children of a node
int getNumberOfChildren() //return the number of children of a node
Node<T> getParent() //returns the parent of a node
boolean isLeaf() //returns true if a node is a leaf

Tree.java:

Field Summary:

int ar; //equals to k-arity of the tree (int k of the constructor)
Node<T> root; //the root node of a tree

Constructor Summary:
Tree(int k) //creates a Tree of k arity

Method Summary:
void addRoot(T info) //add a root to a tree
void changeRoot(T info) //changes the root of a tree creating a new one with new info
Node<T> getRoot() //return the root of the current tree
void addNewNodeVasithChildOfNodeU(Node<T> u, T info, int i) //add a new node as it is the i-th child of the node u
int getHeight() //returns the height of the tree
int getHeight(Node<T> n) //returns the height from a specific node
void innesta(Node<T> u, Tree<T> subTree) //add a tree (subtree) as a child of a node of the principal tree
int numberOfNodesInTree() //returns the number of the nodes in the tree
int numberOfNodesInTree(Node<T> node) //returns the number of the nodes in the tree starting from a specific node
LinkedList<T> visitaBFS() //returns a list of the infos obtained with a BFS
LinkedList<T> visitaDFSA() //returns a list of the infos obtained with a DFS (pre-order)
LinkedList<T> visitaDFSP() //returns a list of the infos obtained with a DFS (post-order)
LinkedList<T> visitaSIM()//THE ONE I DON'T KNOW HOW TO DO! should return the infos obtained with a symmetrical visit of the tree

我非常感谢每一个能帮我写出最后一种方法的人。

Answer 1

对于每个节点有一个循环，递归地访问第一个k/2子树。返回后，访问当前节点，然后在循环中递归访问其余的子树。