需要我的树(n 叉树)的搜索方法 [英] need a search method for my tree(n-ary tree)
问题描述
我已经为家谱编写了这个树类
i have written this tree class for a familytree
现在我需要一个搜索方法来在我的树中找到一个节点
now i need a search method to find a node in my tree
它是一个 n 叉树,每个节点可以有 0 到 n 个子节点
its a n-ary tree that each node can have 0 to n children
搜索方法可以搜索一个节点或两个名字,包括节点名和他/她的父亲名
the search method can search for a node or for two names includes node name and his/her father name
请帮帮我
public class FamilyNode {
public String name;
public String sex;
public FamilyNode Father;
public FamilyNode Mother;
public FamilyNode Spouse=null;
public String status="alive";
public int population;
public ArrayList<FamilyNode> children=new ArrayList<FamilyNode>() ;
public FamilyNode(String name1,String sex1){
this.name=name1;
this.sex=sex1;
this.population=this.children.size()+1;
}
public void SetParents(FamilyNode father,FamilyNode mother){
this.Father=father;
this.Mother=mother;
}
public void SetHW(FamilyNode HW){
this.Spouse=HW;
}
public void AddChild(FamilyNode child){
child.SetParents(this.Father, this.Spouse);
this.children.add(child);
this.Spouse.children.add(child);
}
public int Number (){
int number_of_descendants = this.population;
if(this.Spouse!=null) number_of_descendants++;
for(int index = 0; index < this.children.size(); index++)
number_of_descendants = number_of_descendants+ this.children.get(index).Number();
return number_of_descendants;
}
}
推荐答案
看看树遍历算法.这个文章很好地涵盖了它们(使用递归和出队)这是遍历树的一种方法
Have a look at Tree Traversal algorithms. This article covers them pretty well (using recursion and dequeues) Here is one way of traversing your tree
public class FamilyNode {
// ...
// ...
public void traverseNode(){
if(name.equals("NameWeAreLookingFor")){
// We found a node named "NameWeAreLookingFor"
// return here if your are not interested in visiting children
}
for(FamilyNode child : node.children){
child.traverseNode();
}
}
}
要遍历所有树,请执行以下操作:
To traverse all your tree, do the following:
FamilyNode root = ...;
root.traverseNode();
请注意,此方法使用递归.如果您的树非常大,那么我建议您改用队列,因为递归可能会导致 StackOverFlow 异常.
Note that this method is using recursion. If your tree is very big then I suggest you go for using queues instead as recursion might end up in a StackOverFlow exception.
这篇关于需要我的树(n 叉树)的搜索方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!