如何得到一个树的最长路径（500分求救）？

Question

bluesmile979(笑着) 、 qiuwanbin(哈哈，我呀。) ：
能否说一下具体的步骤？？？
nc201(Bricklayer)
效率是个问题

Answer 1

先降所有节点主键和父节点存到一个数组里，
用循环队列实现，其长度为节点个数，
先将0进队列，var deepestID；while（如果队列不为空）
{
  队列头元素出队列currentID;
  if (存在以currentID为父节点的节点)//也就是说他不是叶子
  {
    找所有以currentID为父节点的节点ID进队列；
  }
  else //她为叶子节点
  {
    deepestID ＝ currentID。
  }
}当队列为空时，deepestID 为最深节点的ID，
然后根据父节点的关系，最后找到 0 ，求其深度。试试吧！应该可以。

Answer 2

你要的东西是不是用JTree实现的？？

Answer 3

我用JTree试了一下，并没有测试，思路是用每个节点的层次和根节点的深度相比较，
相等的就是符合条件的节点，然后再找这些节点对应的路径
可能有一堆概念上的错误，高手们帮我看看吧import java.util.ArrayList;
import javax.swing.JTree;
import javax.swing.tree.DefaultMutableTreeNode;public class TreeTools {
private static void getLongestPath(JTree aTree) {
DefaultMutableTreeNode aNode = (DefaultMutableTreeNode) aTree
.getModel().getRoot();
//存放最远路径字符串的集合
ArrayList path = new ArrayList();
if (aNode.isLeaf()) {
return;
}
//取得节点深度
int depth = aNode.getDepth();
//取得符合条件的子节点集合
ArrayList childNode = getNodes(aNode, depth);
//按照节点取得字符串,放入集合
for (int i = 0; i < childNode.size(); i++) {
String pathString = getPathString(
(DefaultMutableTreeNode)   childNode.get(i), depth);
path.add(pathString);
}
}

//取得符合条件的节点集合
private static ArrayList getNodes(DefaultMutableTreeNode aNode, int depth) {
//创建存放符合条件的节点对象的容器
ArrayList childNode = new ArrayList();
if (aNode.isLeaf()) {
return childNode;
}
//遍历子节点,将节点层次与根节点深度相等的节点,即最远节点放入数组
for (int i = 0; i < aNode.getChildCount(); i++) {
DefaultMutableTreeNode node = (DefaultMutableTreeNode) aNode
.getChildAt(i);
//取得节点层次
int nodeLevel = node.getLevel();
//如果层次和根节点深度相等,将节点加入字符串
if (nodeLevel == depth) {
childNode.add(node);
}
ArrayList aChildNode = getNodes(node, depth);
if (aChildNode.size() != 0) {
for (int j = 0; j < aChildNode.size(); j++) {
childNode.add(aChildNode.get(j));
}
}
}
return childNode;
}

//根据节点回溯到根节点,取得各个节点的显示值,组成字符串
private static String getPathString(DefaultMutableTreeNode aNode, int depth) {
StringBuffer pathBuffer = new StringBuffer();
for (int i = 0; i < depth; i++) {
TreeNodeData nodeData = (TreeNodeData) aNode.getUserObject();
pathBuffer.append(nodeData.getDisplayValue().toString());
aNode = (DefaultMutableTreeNode) aNode.getParent();
}
return pathBuffer.toString();
}
}public class TreeNodeData {
private Object displayValue;
private Object key;
private Object parentKey;
public TreeNodeData() {
}
public Object getKey() {
return key;
}
public void setKey(Object key) {
this.key = key;
}
public void setParentKey(Object parentKey) {
this.parentKey = parentKey;
}
public Object getParentKey() {
return parentKey;
}
public void setDisplayValue(Object displayValue) {
this.displayValue = displayValue;
}
public Object getDisplayValue() {
return displayValue;
}
public String toString() {
if (displayValue != null)
return displayValue.toString();
else
return key.toString();
}
}

Answer 4

我的思路里的队列变化大概是这样的
（因为同层的节点先找到谁不一定）：
根据你给的图,下面的队列最左边是队列头
A       deepestID = 0
DCB     deepestID = 0
EFDC    deepestID = 0
GEFD    deepestID = 0
HGEF    deepestID = F.ID
HGE     deepestID = F.ID
IJHG    deepestID = F.ID
KIJH    deepestID = F.ID
KIJ     deepestID = H.ID
KI      deepestID = J.ID
K       deepestID = I.ID
        deepestID = K.ID
跳出循环，K就是深度最深的叶子，或者最深的叶子之一，
然后根据 最深的K.ID 求深度，
这么做只能算出树的深度，不能求出所有最深的深度的叶子节点，
如果单纯的求树的深度应该够了。
 

Answer 5

andy100085(方丈)
我回去试试看，我现在头都想疼了：）Taelohn(点烟看帖)
我是在网页上用的，可惜了！

Answer 6

嘿嘿!又看了一下你的问题，在我的算法上加一点龌龊的处理方法就成了。
队列里存的对象为：ArrayList list //所有节点存放在这里。
 
class node
{
   int ID;
   int depth; //深度
}
class deepestID
{
   int depth;
   Arraylist IDs;
}
deepestID deepestIDs ;
node A = new node(0,0);//(ID, depth)
A进队列while（如果队列不为空）
{
  队列头元素出队列currentID;
  if (存在以currentID为父节点的节点)//也就是说他不是叶子
  {
    while（存在以currentID为父节点的节点）
    {
       找的节点 D
       node temp = new node（D.ID, currentID.depth + 1)
       进队列
       将该节点从list删除
    }
   }
  else //她为叶子节点
  {
    if（currentID.dept > deepestIDs.dept )
    {
      重新初始化 deepestIDs；
    }
    else if（currentID.dept = deepestIDs.dept )
    {
      将currentID加入到deepestIDs
     }
  }
}最后得到的对象deepestIDs.IDs保存着所有的最深的ID。