树结构java
1、准备表结构及对应的表数据
a、表结构：
create table TB_TREE
(
CID NUMBER not null,
CNAME VARCHAR2(50),
PID NUMBER //父节点
)
b、表数据：
insert into tb_tree (CID, CNAME, PID) values (1, '中国', 0);
insert into tb_tree (CID, CNAME, PID) values (2, '北京市', 1);
insert into tb_tree (CID, CNAME, PID) values (3, '广东省', 1);
insert into tb_tree (CID, CNAME, PID) values (4, '上海市', 1);
insert into tb_tree (CID, CNAME, PID) values (5, '广州市', 3);
insert into tb_tree (CID, CNAME, PID) values (6, '深圳市', 3);
insert into tb_tree (CID, CNAME, PID) values (7, '海珠区', 5);
insert into tb_tree (CID, CNAME, PID) values (8, '天河区', 5);
insert into tb_tree (CID, CNAME, PID) values (9, '福田区', 6);
insert into tb_tree (CID, CNAME, PID) values (10, '南山区', 6);
insert into tb_tree (CID, CNAME, PID) values (11, '密云县', 2);
insert into tb_tree (CID, CNAME, PID) values (12, '浦东', 4);
2、TreeNode对象，对应tb_tree
public class TreeNode implements Serializable {
private Integer cid;
private String cname;
private Integer pid;
private List nodes = new ArrayList();
public TreeNode() {
}
//getter、setter省略
}
3、测试数据
public class TreeNodeTest {
@Test
public void loadTree() throws Exception{
System.out.println(JsonUtils.javaToJson(recursiveTree(1)));
}
/**
* 递归算法解析成树形结构
*
* @param cid
* @return
* @author jiqinlin
*/
public TreeNode recursiveTree(int cid) {
//根据cid获取节点对象(SELECT * FROM tb_tree t WHERE t.cid=?)
TreeNode node = personService.getreeNode(cid);
//查询cid下的所有子节点(SELECT * FROM tb_tree t WHERE t.pid=?)
List childTreeNodes = personService.queryTreeNode(cid);
//遍历子节点
for(TreeNode child : childTreeNodes){
TreeNode n = recursiveTree(child.getCid()); //递归
node.getNodes().add(n);
}
return node;
}
}
输出的json格式如下：
{
"cid": 1,
"nodes": [
{
"cid": 2,
"nodes": [
{
"cid": 11,
"nodes": [
],
"cname": "密云县",
"pid": 2
}
],
"cname": "北京市",
"pid": 1
},
{
"cid": 3,
"nodes": [
{
"cid": 5,
"nodes": [
{
"cid": 7,
"nodes": [
],
"cname": "海珠区",
"pid": 5
},
{
"cid": 8,
"nodes": [
],
"cname": "天河区",
"pid": 5
}
],
"cname": "广州市",
"pid": 3
},
{
"cid": 6,
"nodes": [
{
"cid": 9,
"nodes": [
],
"cname": "福田区",
"pid": 6
},
{
"cid": 10,
"nodes": [
],
"cname": "南山区",
"pid": 6
}
],
"cname": "深圳市",
"pid": 3
}
],
"cname": "广东省",
"pid": 1
},
{
"cid": 4,
"nodes": [
{
"cid": 12,
"nodes": [
],
"cname": "浦东",
"pid": 4
}
],
"cname": "上海市",
"pid": 1
}
],
"cname": "中国",
"pid": 0
}
B. Java 数据结构 - 树与二叉树（一）
Java 数据结构 树与二叉树的核心概念如下：
1. 树的抽象数据类型 定义：使用position表示树中的节点，每个元素存储在position中，并遵守树结构中的parentchild关系。 方法：包含访问方法、查询方法和一些更通用的方法。如果树有序，则children将按照顺序返回节点P的子节点。
2. 树接口在Java中的实现 定义Tree接口：扩展Java的iterable类，并使用Position类表达位置概念。 功能：实现树的ADT中定义的各种方法。
3. 计算树的高度和深度 深度：节点p的深度表示从根节点到节点p的唯一路径上的边数。 高度：树的高度等于树中节点的最大深度，即从根节点到最远叶子节点的最长路径上的边数。
4. 二叉树的定义 有序结构：每个内部节点拥有0或2个子节点。 递归定义：二叉树是递归定义的，即一个二叉树要么为空，要么由一个根节点以及两个互不相交的、分别称作左子树和右子树的二叉树组成。
5. 二叉树的ADT 支持操作：除了树ADT支持的操作外，还支持额外的三种树结构数据操作，如获取左子节点、右子节点等。
6. 二叉树抽象基类的实现 方法：包含sibling方法，利用left和right方法提供numChildren和children方法。通过创建一个snapshot来实现children方法。
7. 二叉树的属性 节点数量：二叉树的高度与节点数量呈指数增长，第x层最多拥有2^x个节点。
8. 构建二叉树 方法：使用连接结构构建二叉树，节点追踪当前叶子节点的位置，树存储指向根节点的变量和子节点数量。
9. 更新二叉树方法 添加元素：提供添加元素的方法，操作复杂度为O。
10. 数组实现二叉树 存储：使用数组存储树结构，数据位置直接通过数字Index表达。 子节点父节点关系：通过公式计算子节点和父节点的位置关系。 空间使用：依赖于树形状，更新操作复杂度为O。
11. 链接结构实现二叉树 节点存储：每个节点显示保存左、右2个子节点。 子节点引用：通过给每个节点分配一个容器储存子节点引用。 运行效率：这种形式实现对应的运行效率较高，适用于大多数二叉树操作。