Java算法：遞歸二叉樹算法

二叉樹的本質是遞歸結構，很多可以使用遞歸分治法完成的，推廣了遍歷算法。

在只給定指向樹的一個指針的前提下，經常需要找到樹的各種結構參數的值。

例1：樹參數的計算，樹的結點樹和高度

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：快速的輸出樹方法

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：競標賽樹的構建（分支遞歸策略）

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;???
}

在某些情況下，構建遞歸數據結構可能要比通過掃描數據找到最大值好。

使二叉樹構建前綴表達式。

例4：解析樹的構建

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

以上就是動力節點java培訓機構的小編針對“Java二叉樹遞歸算法，初學者入門收藏”的內容進行的回答，希望對大家有所幫助，如有疑問，請在線咨詢，有專業老師隨時為你服務。