二叉樹的一些算法<未完>判斷二叉樹是否平衡二叉樹

本文中二叉樹結構定義為：

1

2

3

4

5

6

<code>本文中二叉樹結構定義為：</code>

<code>struct</code> <code>Node {</code>

<code> </code><code>Node* left;</code>

<code> </code><code>Node* right;</code>

<code> </code><code>int</code> <code>data;</code>

<code>};</code>

定義：空二叉樹的高度為-1，隻有根節點的二叉樹高度為0，根節點在0層，深度為0。

兩個節點的距離為兩個節點間最短路徑的長度。

求兩節點的最遠距離，實際就是求二叉樹的直徑。假設相距最遠的兩個節點分别為A、B，它們的最近共同父節點（允許一個節點是其自身的父節點）為C，則A到B的距離 = A到C的距離 + B到C的距離。

節點A、B分别在C的左右子樹下（假設節點C的左右兩子樹均包括節點C），不妨假設A在C的左子樹上，由假設“A到B的距離最大”，先固定B點不動（即B到C的距離不變），根據上面的公式，可得A到C的距離最大，即點A是C左子樹下距離C最遠的點，即：

A到C的距離 = C的左子樹的高度。

同理，   B到C的距離 = C的右子樹的高度。

   是以，本問題可以轉化為：“二叉樹每個節點的左右子樹高度和的最大值”。

7

8

9

10

11

12

13

14

15

<code>static</code> <code>int</code> <code>tree_height(</code><code>const</code> <code>Node* root, </code><code>int</code><code>&amp; max_distance)</code>

<code>{</code>

<code> </code><code>const</code> <code>int</code> <code>left_height = root-&gt;left ? tree_height(root-&gt;left,  max_distance) + 1 : 0;</code>

<code> </code><code>const</code> <code>int</code> <code>right_height = root-&gt;right ? tree_height(root-&gt;right, max_distance)  + 1 : 0;</code>

<code> </code><code>const</code> <code>int</code> <code>distance = left_height + right_height;</code>

<code> </code><code>if</code> <code>(max_distance &lt; distance) max_distance = distance;</code>

<code> </code><code>return</code> <code>(left_height &gt; right_height ? left_height : right_height);</code>

<code>}</code>

<code> </code> 

<code>int</code> <code>tree_diameter(</code><code>const</code> <code>Node* root)</code>

<code> </code><code>int</code> <code>max_distance = 0;</code>

<code> </code><code>if</code> <code>(root) tree_height(root, max_distance);</code>

<code> </code><code>return</code> <code>max_distance;</code>

　　

根據平衡二叉樹的定義：每個結點的左右子樹的高度差小等于1，隻須在計算二叉樹高度時，同時判斷左右子樹的高度差即可。

16

17

18

19

<code>static</code> <code>int</code> <code>tree_height(</code><code>const</code> <code>Node* root, </code><code>bool</code><code>&amp; balanced)</code>

<code> </code><code>const</code> <code>int</code> <code>left_height = root-&gt;left ? tree_height(root-&gt;left, balanced) + 1 : 0;</code>

<code> </code><code>if</code> <code>(!balanced) </code><code>return</code> <code>0;</code>

<code> </code><code>const</code> <code>int</code> <code>right_height = root-&gt;right ? tree_height(root-&gt;right, balanced) + 1 : 0;</code>

<code> </code><code>const</code> <code>int</code> <code>diff = left_height - right_height;</code>

<code> </code><code>if</code> <code>(diff &lt; -1 || diff &gt; 1) balanced = </code><code>false</code><code>;</code>

<code>bool</code> <code>is_balanced_tree(</code><code>const</code> <code>Node* root)</code>

<code> </code><code>bool</code> <code>balanced = </code><code>true</code><code>;</code>

<code> </code><code>if</code> <code>(root) tree_height(root, balanced);</code>

<code> </code><code>return</code> <code>balanced;</code>

==============================================================================

本文轉自被遺忘的部落格園部落格，原文連結：http://www.cnblogs.com/rollenholt/archive/2012/05/12/2497299.html，如需轉載請自行聯系原作者