首页 > 程序开发 > 软件开发 > 其他 >

普通树的广度搜索和深度搜索java实现

2017-04-21

普通树的广度搜索和深度搜索java实现:数据结构中的树搜索方式可以分为广搜和深搜,顾名思义,广搜就是一层一层的搜索,深搜就是先搜索左子树从左节点搜索一直到叶子节点,然后搜索右子树。

普通树的广度搜索和深度搜索java实现:数据结构中的树搜索方式可以分为广搜和深搜,顾名思义,广搜就是一层一层的搜索,深搜就是先搜索左子树从左节点搜索一直到叶子节点,然后搜索右子树。

下面用java实现广搜和深搜:

广搜采用队列的结构,java API提供了双端队列的类ArrayDeque

public static Tree find(int value, Tree tree){
Deque deque = new ArrayDeque();
deque.add(tree);
Tree result = null;
while(!deque.isEmpty()){
Tree temp = deque.pop();
if(temp.element == value){
result = temp;
break;
}

List children = temp.getChildren();
if(children != null && children.size() > 0){
for(Tree child : children){
deque.add(child);
}
}
}
return result;
}


class Tree{
private int element;
private List children = new ArrayList();
public int getElement() {
return element;
}
public void setElement(int element) {
this.element = element;
}
public List getChildren() {
return children;
}
public void setChildren(List children) {
this.children = children;
}

}



深搜采用栈的数据结构:

public static Tree find2(int value, Tree tree){
Stack stack = new Stack();

stack.add(tree);
Tree result = null;
while(!stack.isEmpty()){
Tree temp = stack.pop();
if(temp.element == value){
result = temp;
break;
}

List children = temp.getChildren();
if(children != null && !children.isEmpty()){
for(Tree child : children){
stack.add(child);
}
}
}
return result;
}
相关文章
最新文章
热点推荐