樹結構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個子節點。 子節點引用：通過給每個節點分配一個容器儲存子節點引用。 運行效率：這種形式實現對應的運行效率較高，適用於大多數二叉樹操作。