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
}
二叉树1
2
3
4
5
6
7
这个二叉树的深度是3,树的深度是最大结点所在的层,这里是3.
应该计算所有结点层数,选择最大的那个。
根据上面的二叉树代码,递归过程是:
f
(1)=f
(2)+1
>
f
(3)
+1
?
f(2)
+
1
:
f(3)
+1
f(2)
跟f(3)计算类似上面,要计算左右结点,然后取大者
所以计算顺序是f(4.left)
=
0,
f(4.right)
=
0
f
(4)
=
f(4.right)
+
1
=
1
然后计算f(5.left)
=
0,f(5.right)
=
0
f
(5)
=
f(5.right)
+
1
=1
f(2)
=
f(5)
+
1
=2
f(1.left)
计算完毕,计算f(1.right)
f(3)
跟计算f(2)的过程一样。
得到f(3)
=
f(7)
+1
=
2
f(1)
=
f(3)
+
1
=3
12345if(depleft>depright){return depleft+1}else{return depright+1}
只有left大于right的时候采取left
+1,相等是取right
如果数据库是oracle,可以用递归的sql实现
如果想用java实现
第一步遍历节点放入map结构
再次遍历节点,取出当前节点的父节点,parentNode.setchild(courrentNode)
这样第二次遍历完后已经是树形结构了。
从map中取出root节点就行
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)