二叉樹 的 常用公式 誰能和新手 說說?。?/h1>

2022-08-10 01:34

要考試了 二叉樹 的 問題 挺多的 誰能幫幫忙啊 ?。。?！

1個(gè)回答

2022-08-10 05:56

(1) 在二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2^(i-1)；
(2) 深度為h的二叉樹最多有2^h-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；
(3) 對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，
則N0=N2+1；
(4) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int（log2n）+1
(5)有N個(gè)結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：
若I為結(jié)點(diǎn)編號(hào)則 如果I<>1，則其父結(jié)點(diǎn)的編號(hào)為I/2；
如果2*I<=N，則其左兒子（即左子樹的根結(jié)點(diǎn)）的編號(hào)為2*I；若2*I>N，則無左兒子；
如果2*I+1<=N，則其右兒子的結(jié)點(diǎn)編號(hào)為2*I+1；若2*I+1>N，則無右兒子。
(6)給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹。
h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(n,2*n)/(n+1)。