java樹遞歸
『壹』 java數據結構二叉樹深度遞歸調用演算法求內部演算法過程詳解
二叉樹
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
if(depleft>depright){
returndepleft+1;
}else{
returndepright+1;
}只有left大於right的時候採取left +1，相等是取right
『貳』 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
}
『叄』 用java遞歸方法實現
publicintfun(intn){
if(n==0||n==1)return1;
returnn*fun(n-1);
}
『肆』 java 目錄樹如何檢索子級返回
Java中使用遞歸演算法實現查找樹形結構中所有父級和子級節點，用遞歸加一個全局變數標記是否已經找到，然後返回。
截取後面的一段例子：
if (list[i].ID.Equals(id) || found)
found = true;
return;
拓展資料
遞歸查詢子級節點
1.一個節點可能有多個子級節點，每個自己節點可能還有更多的子級節點。
2.所以遞歸時的參數用一個list來接受，首先遍歷參數list，分別查詢pid為參數id的對象。
3.每一個參數id所查詢返回的數據是一個對象的list。
4.遍歷list獲取符合條件的對象的id值，一份存到temp中用作遞歸的參數，並存到全局變數中用來獲取所有符合條件的id。
『伍』 java 如何遞歸 給樹型結構的元素編號
insert tb_menu(id, name, parent) (640000000000,北京市 ,0);
insert tb_menu(id, name, parent) (640100000000,昌平區 ,1);
insert tb_menu(id, name, parent) (640101000000,霍營 ,2);
insert tb_menu(id, name, parent) (640101001000, 回龍觀東大街,3);
添加一個節點屬性， 根據數據不同代表的地位不同，0就代表父節點 ，1是0的子節點，2是1的子節點，以此類推。
『陸』 JAVA如何理解遞歸
1、遞歸做為一種演算法在程序設計語言中廣泛使用，是指函數/過程/子程序在運行過程中直接或間接調用自身而產生的重入現象。
2、遞歸演算法一般用於解決三類問題：
1）數據的定義是按遞歸定義的。（Fibonacci（斐波那契）的函數）
2）問題解法按遞歸演算法實現。（回溯）
3）數據的結構形式是按遞歸定義的。（樹的遍歷，圖的搜索）
『柒』 java樹級對象遞歸查找子集問題
packagecom.demo.dept;
/**
*@authordongbin.yu
*@from2016-05-06
*@sinceV1.0
*/
publicclassDept{
privateintid;
privateStringname;
privateintparentId;
publicintgetId(){
returnid;
}
publicvoidsetId(intid){
this.id=id;
}
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
publicintgetParentId(){
returnparentId;
}
publicvoidsetParentId(intparentId){
this.parentId=parentId;
}
publicDept(intid,Stringname,intparentId){
this.id=id;
this.name=name;
this.parentId=parentId;
}
}
packagecom.demo.dept;
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
/**
*@authordongbin.yu
*@from2016-05-06
*@sinceV1.0
*/
publicclassDeptTest{
privatestaticList<Dept>depts=newArrayList<>();
static{
depts.add(newDept(1,"部門1",0));
depts.add(newDept(2,"部門2",1));
depts.add(newDept(3,"部門3",1));
depts.add(newDept(4,"部門4",1));
depts.add(newDept(5,"部門5",2));
depts.add(newDept(6,"部門6",3));
depts.add(newDept(7,"部門7",2));
depts.add(newDept(8,"部門8",2));
depts.add(newDept(9,"部門9",1));
depts.add(newDept(10,"部門10",5));
}
publicstaticvoidmain(String[]args){
Map<Integer,List<Integer>>deptMap=newHashMap<>();
for(Deptdept:depts){
deptMap.put(dept.getId(),getChildDept(dept.getId()));
}
System.out.println(deptMap);
}
privatestaticList<Integer>getChildDept(intid){
List<Integer>ids=newArrayList<>();
for(Deptdept:depts){
if(dept.getParentId()==id){
//添加第一次父id符合的
ids.add(dept.getId());
//添加嵌套父id符合的
ids.addAll(getChildDept(dept.getId()));
}
}
Collections.sort(ids);
returnids;
}
}
『捌』 java 遞歸 算 二叉樹 層級
層次遍歷從方法上不具有遞歸的形式，所以一般不用遞歸實現。當然了，非要寫成遞歸肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("\n"); LevelOrder(level, rear); free(level); } 補充一下，在main裡面調用的時候就得用LevelOrder(T,1)了。