北京一家公司的笔试题，希望大家给个思路

Question

创建树，树上每一个节点都是Class Node的实例，Node有name, value属性，其中name和value是初始时已经设好的, 要求用数据结构中的树(不是二叉树)来实现，要求能够保持构造树时添加结点的顺序。构造树的时候可以在代码中写死各个节点值，不用动态输入进行构造树，不用汉字，拼音做类名，注释等等(用递归实现)
要求
1. 写一个方法Node searchNode(String searchName),实现节点查找. 要求在树中查找name值等于searchName的节点，如果找不到，返回NULL, 找到了就返回此节点.
2. 调用searchNode方法查找节点,没有找到节点输出"Not found", 如果找到了就输出此节点name,value值。
   构造如下的树，查找节点 Sub 22, Sub 3, Sub 10(找不到)
   依次调用
   searchNode("Sub 22");
     输出 Sub 22, 0
   searchNode("Sub 3");
     输出 Sub 3, 50
   searchNode("Sub 10");
     输出 Not foundRoot(value:0)--
|--Sub 1 (value:20)
|--Sub 2(value:10)
| |--
| |--Sub 21(value:5)
| |--Sub 22 (value:0)
|--Sub 3 (value:50)
|--
|--Sub 31(value:100)
|--Sub 32(value:200)题目我有点看不明白，这要用用什么实现呢？链表？又不是二叉树，怎样递归创建树呢？

Answer 1

public Class Node{
   private String name, value;
   List children=new List();
   public void addChild(Node child){
       children.add(child);
   }   public Node   searchNode(String   searchName){
      Node result=null;
      for(int i=0; i<children.size();i++){
         if (children.get(i).getName().equals(searchName)){
            result=children.get(i);
            break;
         }
      }
      //没找到，则递归查找
      if (result==null){
         for(int i=0; i<children.size();i++){
             result=children.get(i).searchNode(searchName);
             if (children!=null){                
                break;
             }
          }
      }
      return result;
   }
}

Answer 2

给你白话一下：创建一个树，这个树不是二叉树，树上的每个结点都是Node类的一个实例，在树构造的时候，构造结点的顺序是一定的：s1,s2,s21,s22,s3,s31,s32。在构造时，结点中的值自己定，不用让用户输入。Node类中有两个成员：name 和 value ，类似的，类的名字可以自定，但不能用中文，拼音。注释也不能使用中文和拼音要求
1、定义一个函数searchNode(String   searchName),实现节点查找，找到了就返回这个结点对象的指针，没找到就返回NULL
2、在调用searchNode函数后，再输出这个结果：找到：输出该结点的name、value，没找到输出信息："Not   found"

Answer 3

补充一下，searchNode函数用递归的方法实现

Answer 4

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Node {
public String name;
public String value;
public List list ;

public Node searchNode(String searchName){
if(this.name.equals(searchName))return this;

Node node = null;
Iterator iterator = list.iterator(); 
while(iterator.hasNext()){
node = (Node)iterator.next();
if(searchName.equals(node.name))
return node;
else if(node.list != null)
node.searchNode(searchName);
}
System.out.println("Not found");
return null;
}
public void addSubNode(String name ,String value){
if(list == null) list = new ArrayList();
Node node = new Node();
node.name = name;
node.value = value;
list.add(node);
}
public boolean hasNode(Node node){
if(list == null) return false;
return list.indexOf(node) > -1;
}

}

Answer 5

node.searchNode(searchName);
没有人接收，最终只能返回null，如果树大于二层

Answer 6

Lihongyang66 
 
等 级：
 发表于：2007-11-29 10:59:227楼 得分:0 
node.searchNode(searchName); 
没有人接收，最终只能返回null，如果树大于二层 
 
---------------
为什么不接受啊,就是只有1层也需要接受.

Answer 7

啊,不对,说错了,如果没有的话,if(this.name.equals(searchName))return this;肯定是走这个的.
我测试的代码.
Node node = new Node();
node.name = "Root";
node.value = "0";
node.addSubNode("Sub 1", "20");
node.addSubNode("Sub 2", "10");
((Node)node.list.get(1)).addSubNode("21", "5");
((Node)node.list.get(1)).addSubNode("22", "0");
node.addSubNode("Sub 3", "50");
node.addSubNode("Sub 22", "100");

Node find = node.searchNode("Sub 11");
if(find == null)System.out.println("Not found");
else{
System.out.println(find.name);
System.out.println(find.value);
}

Answer 8

啊,是不对,不好意思,这样
while(iterator.hasNext()){
            node = (Node)iterator.next();
            if(searchName.equals(node.name))
                return node;
            else if(node.list != null)
                return node.searchNode(searchName);
        }