关于树及搜索

Question

假定在一个树,即其根结点为A,有多个数目不定的子节点,如B C D E---.其中每个子节点又有数目不等的多个子节点,如B子节点有B1 B2 B3 B4--,C节点下有子节点C1 C2 C3 C4 C5---,以此类推.假定每个节点都包括字符串数据.1.这类树应该用什么样的数据结构描述.2.假如有str1,str2,str3.要求与各层节点中的数据比较,寻找具备相应的字符串的节点,并打印其路径.
如A中如包括有str1,那么再在 B C D E--中寻找包涵 str2的节点,假定B C中存在str2,再在B C的子节点 B1 B2 B3 B4-- C1 C2 C4 C5 --查找包涵str3的子节点,假如B1 B4,C2 C4 C5中包涵str3.那么,打印出其路径
1.A B B1
2.A B B4
3.A C C2
4.A C C4
5.A C C5

Answer 1

这是树遍历的问题,你可以直接用树的遍历,或者你将树转换成二叉树,再进行二叉树的遍历.
这个算法你可以参考严蔚敏的<数据结构>.里面有算法,研究一下,不是很难.

Answer 2

楼上的兄弟有说用二差树的，我感觉够呛把。
可以用这样的。
这样定义节点类。
class Node
{
pubic String s;
public List<Node> children=new LinkedList<Node>();
public Node(String t)
{
s=t;
}
public boolean equals(Object t)
{
return s.equals((Node)t.s);
}
}根据你自己的要求构造出树来，然后深度搜索就可以了

Answer 3

先定义节点的数据结构
/*
 * Created on 2005-6-13
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package simple;import java.util.ArrayList;/**
 * @author handle
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class Node {
private ArrayList childs;
private String value=null;
private Node father=null;
private String nodeName=null; /**
 * @return Returns the nodeName.
 */
public String getNodeName() {
return nodeName;
}
/**
 * @param nodeName The nodeName to set.
 */
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
/**
 * @return Returns the father.
 */
public Node getFather() {
return father;
}
/**
 * @param father The father to set.
 */
public void setFather(Node father) {
this.father = father;
}
/**
 * @return Returns the value.
 */
public String getValue() {
return value;
}
/**
 * @param value The value to set.
 */
public void setValue(String value) {
this.value = value;
}
/**
 * @return Returns the childs.
 */
public ArrayList getChilds() {
return childs;
}
/**
 * @param childs The childs to set.
 */
public void setChilds(ArrayList childs) {
this.childs = childs;
}

public void add(Node node){
if(childs==null){
childs=new ArrayList();
}
childs.add(node);
}
public boolean del(Node node){
boolean flag=true;
try {
childs.remove(node);
} catch (Exception e) {
flag=false;
}
return flag;
}
}
测试节点
/*
 * Created on 2005-6-13
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package simple;import java.util.Iterator;/**
 * @author handle
 * 
 * TODO To change the template for this generated type comment go to Window -
 * Preferences - Java - Code Style - Code Templates
 */
public class TestNode { private Node root = new Node(); private void init() {
//初始化树
} public static void main(String[] args) {
String[] values = { "str1", "str2", "str3" };
TestNode app = new TestNode();
app.init();
app.search(app.root, values, 0);
} private void search(Node node, String[] values, int index) { if (node.getValue().equals(values[index])) {
System.out.println(root.getNodeName());
if (node.getChilds() != null) {
Iterator itr = node.getChilds().iterator();
Node tmp;
while (itr.hasNext()) {
tmp = (Node) itr.next();
search(tmp, values, index + 1);
}
}
} else {
if (node.getChilds() != null) {
Iterator itr = node.getChilds().iterator();
Node tmp;
while (itr.hasNext()) {
tmp = (Node) itr.next();
search(tmp, values, index);
}
}
}
}
}

Answer 4

我把测试类修改了一下，这样就可以显示所要找的值对应树中的绝对路径。
/*
 * Created on 2005-6-13
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package simple;import java.util.Iterator;/**
 * @author handle
 * 
 * TODO To change the template for this generated type comment go to Window -
 * Preferences - Java - Code Style - Code Templates
 */
public class TestNode { private Node root = new Node(); private void init() {
//初始化树
} public static void main(String[] args) {
String[] values = { "str1", "str2", "str3" };
TestNode app = new TestNode();
app.init();
app.search(app.root, values, 0, "");
System.out.println("The End!");
} private void search(Node node, String[] values, int index, String path) {
if (node.getValue().equals(values[index])) {
path = path + root.getNodeName();
System.out.println(path + "--->" + root.getNodeName()
+ "--->values" + values[index]);
if (node.getChilds() != null) {
Iterator itr = node.getChilds().iterator();
Node tmp;
while (itr.hasNext()) {
tmp = (Node) itr.next();
search(tmp, values, index + 1, path);
}
}
} else {
if (node.getChilds() != null) {
Iterator itr = node.getChilds().iterator();
Node tmp;
while (itr.hasNext()) {
tmp = (Node) itr.next();
search(tmp, values, index, path);
}
}
}
}
}

Answer 5

TO： faen(发恩) 
你的写法是JDK1.5的写法，对于底版本的JDK这种写法编译是不通过的

Answer 6

TO: hxshandle(有妖怪啊) 
是的用jdk1.5的范型编程，不过这不是本质问题，只是可以简化装箱，拆箱的操作

Answer 7

C++我只用了很少的一段时间，现在主要是xml方面的编成，对socket也有兴趣，以后可以多交流交流啊

Answer 8

TO  faen发恩
是的用jdk1.5的范型编程，不过这不是本质问题，只是可以简化装箱，拆箱的操作
这里的资料能否介绍一下?

Answer 9

TO: WinFastNcr(随她去吧!) 
关于范型编程我在这里一句两句也说不清楚，建议你看看csdn网站的java杂志的第二期，将得很好的

Answer 10

To:WinFastNcr(随她去吧!) 
关于泛型的好坏还有待时间的考证，不过个人觉得，1.5的泛型只是写法上有别于以前的版本，本质还是没变。