Java算法：遞歸二叉樹(shù)算法

二叉樹(shù)的本質(zhì)是遞歸結(jié)構(gòu)，很多可以使用遞歸分治法完成的，推廣了遍歷算法。

在只給定指向樹(shù)的一個(gè)指針的前提下，經(jīng)常需要找到樹(shù)的各種結(jié)構(gòu)參數(shù)的值。

例1：樹(shù)參數(shù)的計(jì)算，樹(shù)的結(jié)點(diǎn)樹(shù)和高度

private?static?int?count(Node?h){???
????if(h?==?null){???
????????reutrn?0;???
????}???
????return?count(h.l)?+?count(h.r)?+?1;???
}???
int?count(){???
????return?count(root);???
}???
private?static?int?height(Node?h){???
????if(h?==?null){???
????????return?-1;???
????}???
????int?u?=?height(h.l),?v?=?height(h.r);???
????if(u?>?v){???
????????return?u?+?1;???
????}else{???
????????return?v?+?1;???
????}???
}???
int?height(){???
????return?height(root);???
}

例2：快速的輸出樹(shù)方法

static?void?printNode(Item?x,?int?h){???
????for(int?i?=?0;?i?<?h;?i++){???
????????System.out.println("???");???
????}???
????System.out.println("["?+?x?+?"]");???
}???
private?static?void?showR(Node?t,?int?h){???
????if(t?==?null){???
????????printNode(null,?h);???
????????return;???
????}???
????showR(t.r,?h?+?1);???
????printNode(t.item,?h);???
????showR(t.l,?h?+?1);???
}???
void?show(){???
????showR(root,?0);???
}

例3：競(jìng)標(biāo)賽樹(shù)的構(gòu)建（分支遞歸策略）

static?class?Node{???
????double?val;???
????Node?l;???
????Node?r;???
????Node(double?v,?Node?l,?Node?r){???
????????this.val?=?v;???
????????this.l?=?l;???
????????this.r?=?r;???
????}???
}???
static?Node?max(double?a[],?int?l,?int?r){???
????int?m?=?(l?+?r)/2;???
????Node?x?=?new?Node(a[m],?null,?null);???
????if(l?==?r){???
????????return?x;???
????}???
????x.l?=?max(a,?l,?m);???
????x.r?=?max(a,?m?+?1,?r);???
????double?u?=?x.l.val,?v?=?x.r.val;???
????if(u?>?v){???
????????x.val?=?u;???
????}else{???
????????x.val?=?v;???
????}???
????return?x;???
}

在某些情況下，構(gòu)建遞歸數(shù)據(jù)結(jié)構(gòu)可能要比通過(guò)掃描數(shù)據(jù)找到最大值好。

使二叉樹(shù)構(gòu)建前綴表達(dá)式。

例4：解析樹(shù)的構(gòu)建

static?Node?parse(){???
????char?t?=?a[i++];???
????Node?x?=?new?Node(t);???
????if((t?==?'+')?||?(t?==?'*')){???
????????x.l?=?parse();???
????????x.r?=?parse();???
????}???
????return?x;???
}

以上就是動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)的小編針對(duì)“Java二叉樹(shù)遞歸算法，初學(xué)者入門(mén)收藏”的內(nèi)容進(jìn)行的回答，希望對(duì)大家有所幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€(xiàn)咨詢(xún)，有專(zhuān)業(yè)老師隨時(shí)為你服務(wù)。