数据结构：树形结构的问题。

Question

现已有如下的数据结构：我是放在ArrayList中的，一行是一个HashTable
messageID parentID message
6         2        aa
5         3        bb
4         3        cc
3         1        dd
2         1        ee
1         -1       ff
因为想创建一个树形状结构，希望把上面的数据结构转换成如下：
messageID parentID message rank（阶层） x轴 y轴
1         -1       ff      0            0   0
2         1        ee      1            x   y
3         1        dd      1            x   3y
4         3        cc      2            2x  4y  
5         3        bb      2            2x  5y 
6         2        aa      2            2x  2y 
parentID == -1 是根结点，x轴 y轴是用来画线的，关键y轴比较难算，请问用什么方法实现啊！

Answer 1

没太明白你的意思，感觉可以用HashMap或HashTable实现。
key里放parentID，然后在value里放对象(你自己建一个类，类里有四个属性，message, rank, X-axis, Y-axis)

Answer 2

<?php
include("incClass.php");
/**
 *从数据库中读取类型，并且自动分类
 *
 */
class RsType2Menu{
private $menuArray;
private $findById;
function __construct($selcetedName=false,$selectedVal=false){
$this->findById=false;
if ($selcetedName and $selectedVal) {
$this->menuArray[$selcetedName]=$selectedVal;
}
else $this->menuArray["基本类型"]=0;
}
function getSqlWhere(){
$sqlWhere=" id=".$this->findById." or fatherId=".$this->findById;
foreach ($this->menuArray as $value) {
if ($value!=0) {
$sqlWhere.=" or fatherId=".$value;
}
}
return $sqlWhere;
}
function findInArr($arr,$fVal){
foreach ($arr as $value) {
if ($value['fatherId']==$fVal) {
return $value;
}
}
return false;
} function addMenuArrayElt($element){
$this->menuArray[$element['name']]=$element['id'];
}
function getTypeMenuArray($rsAssoc,$fatherId=false){
if ($fatherId) {
$this->findById=$fatherId;
}
//$menuArray数组生成以后停止循环。
$stack=array();
$="";//父子元素之间的标记
$temp="";
while (count($rsAssoc)) {
//查找指定fatherId的所有子类型
if ($fatherId and count($stack)==0) {
$temp=$this->findInArr($rsAssoc,$fatherId);
if ($temp) {
array_push($stack,$temp);
$this->addMenuArrayElt($temp);
unset($rsAssoc[$temp['id']]);
$="";
continue;
}
else break;
}
//如果堆栈没有内容，从$rsAssoc读取一个fatherId=0的元素
elseif (count($stack)==0 and $fatherId==false) {
$temp=$this->findInArr($rsAssoc,0);
array_push($stack,$temp);
$this->addMenuArrayElt($temp);
unset($rsAssoc[$temp['id']]);
$="";
continue;
}
//否则，查找栈顶元素是否有子类型
if ($temp=$this->findInArr($rsAssoc,$stack[count($stack)-1]['id'])) {//有子类型，进栈
$.="--";
$temp['name']=$.$temp['name'];
array_push($stack,$temp);
$this->addMenuArrayElt($temp);
unset($rsAssoc[$temp['id']]);
}
else {//没有子类型，叶子出栈
$=substr($,0,strlen($)-2);
array_pop($stack);

}
}
return $this->menuArray;
}
}
/**
 * eg:
 * $conn=getConn();
$rs=$conn->execute("select * from articletypedb");
//getTypeMenuArray($rs);
$temp=$rs->GetAssoc();
$objT2menu=new RsType2Menu();
$objField=new FieldManager("articleType",'类型','A',$objT2menu->getTypeMenuArray($temp));print $objField->field2Html();
 */
?>

Answer 3

以上是用php写的，数据结构和你的几乎一样。

Answer 4

不用把表转化.
  构造树的时候,是从节点小的开始.如从数据库取的数据,可以直接按父节点、子节点分组
即(order by ParentID,ID)
  新增节点时,判断是增兄弟节点,还是子节点.下面附上以前写的代码.import java.awt.*;   
import java.awt.event.*;   
import javax.swing.*;   
import javax.swing.tree.*;   
import java.sql.*;   
import java.util.*;   
public class drawing{   
 public static void main(String[] args) {   
  JFrame frame = new TreeEditFrame();   
  frame.setLocationRelativeTo(null);   
  frame.show();   
 }   
}   
class TreeEditFrame extends JFrame {   
 private DefaultTreeModel model;   
 private JTree tree;   
 public TreeEditFrame() {   
  setTitle("Build Tree");   
  setSize(300, 200);   
  addWindowListener(new WindowAdapter() {   
   public void windowClosing(WindowEvent e) {   
    System.exit(0);   
   }   
  });   
  // construct tree   
  TreeNode root = makeSampleTree();   
  model = new DefaultTreeModel(root);   
  tree = new JTree(model);   
  // tree.setEditable(true);   
  // add scroll pane with tree to content pane   
  Container contentPane = getContentPane();   
  JScrollPane scrollPane = new JScrollPane(tree);   
  contentPane.add(scrollPane, "Center");   
 }   
 public TreeNode makeSampleTree() {   
  DefaultMutableTreeNode root = new DefaultMutableTreeNode("所有节点");   
  String JDriver = "sun.jdbc.odbc.JdbcOdbcDriver";   
  String connectionURL = "jdbc:odbc:OracleTest";   
  Map staff = new HashMap();   
  try {   
   Class.forName(JDriver);   
  } catch (ClassNotFoundException e) {   
   System.out.println("ForName:" + e.getMessage());   
  }   
  try {   
   Connection con = DriverManager.getConnection(connectionURL,   
     "scott", "tiger");   
   Statement stmt = con.createStatement();   
   ResultSet rs = stmt   
     .executeQuery("select * from scott.tree order by ParentID,ID");   
   while (rs.next()) {   
    int i = rs.getInt("ID");   
    int j = rs.getInt("ParentID");   
    String str = rs.getString("Text");   
    DefaultMutableTreeNode ParentId = (DefaultMutableTreeNode) staff   
      .get(new Integer(j));   
    DefaultMutableTreeNode newNode = new DefaultMutableTreeNode(str);   
    if (ParentId != null)   
     ParentId.add(newNode);   
    else  
     root.add(newNode);   
    staff.put(new Integer(i), newNode);   
   }   
   stmt.close();   
   con.close();   
  } catch (SQLException e) {   
   System.out.println("SQLException:" + e.getMessage());   
  }   
  return root;   
 }   
}   
/*  
 * create table SCOTT.TREE ( ID INTEGER not null, PARENTID INTEGER not null,  
 * TEXT VARCHAR2(50) default '' not null, EXPLAIN VARCHAR2(100));  
 */