konhon

忘掉過去，展望未來。找回自我，超越自我。
逃避不一定躲的过, 面对不一定最难过, 孤单不一定不快乐, 得到不一定能长久, 失去不一定不再拥有, 可能因为某个理由而伤心难过, 但我却能找个理由让自己快乐.

Google

BlogJava 首页 新随笔 联系 聚合 管理
  203 Posts :: 0 Stories :: 61 Comments :: 0 Trackbacks
[轉]樹形 算法
我喜欢解决算法问题 哈哈
为了解决这个问题 我写了一个树状数据结构
根节点为世界(我想这个根够大了吧)
下面有两个子节点 分别为亚洲 欧洲
亚洲的下面还有几个节点分别是中国 韩国......
中国下面的几个节点分别是 福建省 湖北省......
以次类推
就是一个树啦 (不知道这个树是不是楼主需要的 反正没事写着玩呗 起码能对楼主有所启发吧)
下面是代码

首先是 Type (一个对象是一条记录)

package beans;

public class Type {
        private int id;

        private String name;

        private int parentid;

        public int getId() {
                return id;
        }

        public void setId(int id) {
                this.id = id;
        }

        public String getName() {
                return name;
        }

        public void setName(String name) {
                this.name = name;
        }

        public int getParentid() {
                return parentid;
        }

        public void setParentid(int parentid) {
                this.parentid = parentid;
        }

}


然后是 TypeTree 继承与Type 比Type 多一个ArrayList属性是 childtype 里面的每一个元素应该是 其子节点TypeTree
(arrayList 里面可能有多个元素,每个元素都是个TypeTree  也可能没有)


package beans;

import java.util.ArrayList;

public class TypeTree extends Type {

        private ArrayList childtype;

        public ArrayList getChildtype() {
                return childtype;
        }

        public void setChildtype(ArrayList childtype) {
                this.childtype = childtype;
        }
}

然后是最重要的 生成TypeTree 的类  这个类可以把 Type[] 转换成一个 TypeTree 对象
这个TypeTree 对象是模拟树状结构的  每一个节点都是一个Type
树的结构也都是按照 数据库表中  id  与parentid 结构的

package beans;

import java.util.ArrayList;

public class Tree {
        private Type[] type;

        private TypeTree typeTree;

        public ArrayList getTree(int parentid) {
                ArrayList arrayList = new ArrayList();
                for (int i = 0; i < type.length; i++) {
                        if (type[i].getParentid() == parentid) {
                                TypeTree t = new TypeTree();
                                t.setId(type[i].getId());
                                t.setName(type[i].getName());
                                t.setParentid(type[i].getParentid());
                                t.setChildtype(getTree(type[i].getId()));
                                arrayList.add(t);
                                System.out.println("Tree" + t.getId() + " " + t.getName() + " "
                                                + t.getParentid());
                        }
                }
                return arrayList;
        }

        public TypeTree createTree() {
                this.typeTree = new TypeTree();
                this.typeTree.setId(0);
                this.typeTree.setName("world");
                this.typeTree.setParentid(-1);
                this.typeTree.setChildtype(this.getTree(0));
                return this.typeTree;
        }

        public Type[] getType() {
                return type;
        }

        public void setType(Type[] type) {
                this.type = type;
        }
}


最后是我测试用的 类 连接数据库写的很简单 别见笑啊
这个类可以直接运行 只要你建立了数据源 呵呵
其中 把树中所有元素显示出来 也是用了一个递归的方法( public static void display(TypeTree typeTree) )
这个递归的方法在你的JSP显示的时候可能有用

package beans;

import java.sql.*;
import java.util.ArrayList;

public class TreeTest {
        Connection con = null;

        Statement sta = null;

        ResultSet res = null;

        String sql = "select * from treetable";

        public Type[] qiaolian() {
                ArrayList arrayList = new ArrayList();
                try {
                        Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");
                } catch (ClassNotFoundException e) {
                        System.out.println(e);
                }
                try {
                        con = DriverManager.getConnection("jdbc:odbc:hib", "sa", "");
                } catch (SQLException e) {
                        System.out.println(e);
                }
                try {
                        sta = con.createStatement();
                        res = sta.executeQuery(sql);
                        while (res.next()) {
                                Type t = new Type();
                                t.setId(res.getInt("id"));
                                t.setName(res.getString("name"));
                                t.setParentid(res.getInt("parentid"));
                                arrayList.add(t);
                        }
                } catch (SQLException e) {
                        System.out.println(e);
                }
                Type[] type = new Type[arrayList.size()];
                for (int i = 0; i < arrayList.size(); i++) {
                        type[i] = (Type) arrayList.get(i);
                }
                return type;
        }

        public static void main(String[] args) {
                TreeTest treeTest = new TreeTest();
                Type[] ty = treeTest.qiaolian();
                Tree tree = new Tree();
                tree.setType(ty);
                TypeTree typeTree = tree.createTree();
                display(typeTree);
        }

        public static void display(TypeTree typeTree) {
                TypeTree now = typeTree;
                System.out.println(now.getId() + "\t" + now.getName() + "\t"
                                + now.getParentid() + "\t" + "child num"
                                + now.getChildtype().size());
                if (now.getChildtype() != null) {
                        ArrayList arrayList = now.getChildtype();
                        for (int i = 0; i < arrayList.size(); i++) {
                                display((TypeTree) arrayList.get(i));
                        }
                }
        }
}
posted on 2006-03-31 02:54 konhon 优华 阅读(458) 评论(0)  编辑  收藏 所属分类: JSP/Servlet

只有注册用户登录后才能发表评论。
网站导航: