二叉查找樹

一棵樹是n個節點和n-1條邊的集合。因為，每條邊都将某個節點連接配接到它的父親，而除去根節點外每一個節點都有一個父親。

二叉樹：每個節點都不能有多于兩個的兒子。深度平均值為o(logn)。

使二叉樹成為二叉查找樹的性質是，對于樹中的每個節點x，它的左子樹中所有關鍵字值小于x的關鍵字值，而它的右子樹中所有關鍵字值大于x的關鍵字值。

在程式中，一定要記得處理的根節點為空的情況。除了删除節點的操作外，其它操作都比較容易實作，通常是遞歸地編寫這些操作例程。删除節點的規則如下：

如果節點是樹葉，立即删除它。

如果節點有一個兒子，那麼将該節點的父節點調整為指向該兒子，然後删除該節點。

如果節點有兩個兒子，那麼查找該節點右子樹中的最小資料，用最小資料替換該節點的資料，然後删除擁有最小資料的那個節點。因為右子樹中最小資料的節點必定不會有做孩子，是以又回到了情況1或情況2.

例程：

<code>#include &lt;stdio.h&gt;</code>

<code>typedef</code> <code>int</code> <code>elementtype;</code>

<code>typedef</code> <code>struct</code> <code>treenode *position;</code>

<code>typedef</code> <code>struct</code> <code>treenode *searchtree;</code>

<code>struct</code> <code>treenode</code>

<code>{</code>

<code>    </code><code>// 自身資料加上指向左右子樹的指針</code>

<code>    </code><code>elementtype element;</code>

<code>    </code><code>searchtree left;</code>

<code>    </code><code>searchtree right;</code>

<code>};</code>

<code>searchtree makeempty(searchtree t)</code>

<code>    </code><code>if</code> <code>(t != null)</code>

<code>    </code><code>{</code>

<code>        </code><code>makeempty(t-&gt;left);</code>

<code>        </code><code>makeempty(t-&gt;right);</code>

<code>        </code><code>free</code><code>(t);</code>

<code>    </code><code>}</code>

<code>    </code><code>return</code> <code>t;</code>

<code>}</code>

<code>// 傳回包含查找元素的指針或null</code>

<code>position find(searchtree t, elementtype x)</code>

<code>    </code><code>if</code> <code>(t == null)</code>

<code>        </code><code>return</code> <code>null;</code>

<code>    </code><code>else</code> <code>if</code> <code>(t-&gt;element &lt; x)</code>

<code>        </code><code>return</code> <code>find(t-&gt;right, x);</code>

<code>    </code><code>else</code> <code>if</code> <code>(t-&gt;element &gt; x)</code>

<code>        </code><code>return</code> <code>find(t-&gt;left, x);</code>

<code>    </code><code>else</code>

<code>        </code><code>return</code> <code>t;</code>

<code>position findmin(searchtree t)</code>

<code>    </code><code>// 這個判斷是必須的</code>

<code>        </code><code>while</code> <code>(t-&gt;left)</code>

<code>            </code><code>t = t-&gt;left;</code>

<code>// 遞歸版本</code>

<code>position findmin_recurse(searchtree t)</code>

<code>    </code><code>else</code> <code>if</code> <code>(t-&gt;left == null)</code>

<code>        </code><code>return</code> <code>findmin(t-&gt;left);</code>

<code>position findmax(searchtree t)</code>

<code>        </code><code>while</code> <code>(t-&gt;right)</code>

<code>            </code><code>t = t-&gt;right;</code>

<code>// 相同節點已在樹中，則不做任何操作</code>

<code>// 傳回指向新樹根的指針</code>

<code>searchtree insert(searchtree t, elementtype x)</code>

<code>        </code><code>t = </code><code>malloc</code><code>(</code><code>sizeof</code><code>(</code><code>struct</code> <code>treenode));</code>

<code>        </code><code>if</code> <code>(t == null)</code>

<code>            </code><code>return</code> <code>null;</code>

<code>        </code><code>t-&gt;element = x;</code>

<code>        </code><code>t-&gt;left = t-&gt;right = null;</code>

<code>    </code><code>else</code> <code>if</code> <code>(x &lt; t-&gt;element)</code>

<code>        </code><code>t-&gt;left = insert(t-&gt;left, x);</code>

<code>    </code><code>else</code> <code>if</code> <code>(x &gt; t-&gt;element)</code>

<code>        </code><code>t-&gt;right = insert(t-&gt;right, x);</code>

<code>searchtree delete(searchtree t, elementtype x)</code>

<code>    </code><code>position tmp;</code>

<code>    </code><code>if</code> <code>(x &lt; t-&gt;element)</code>

<code>        </code><code>t-&gt;left = delete(t-&gt;left, x);</code>

<code>        </code><code>t-&gt;right = delete(t-&gt;right, x);</code>

<code>    </code><code>else</code>    <code>// 找到要删除的節點</code>

<code>        </code><code>if</code> <code>(t-&gt;left &amp;&amp; t-&gt;right)    </code><code>// 該節點有兩個兒子</code>

<code>        </code><code>{</code>

<code>            </code><code>tmp = findmin(t-&gt;right);</code>

<code>            </code><code>t-&gt;element = tmp-&gt;element;</code>

<code>            </code><code>t-&gt;right = delete(t-&gt;right, tmp-&gt;element);</code>

<code>        </code><code>}</code>

<code>        </code><code>else</code>    <code>// 有一個兒子或沒有兒子</code>

<code>            </code><code>tmp = t;</code>

<code>            </code><code>if</code> <code>(t-&gt;left == null)</code>

<code>                </code><code>t = t-&gt;right;</code>

<code>            </code><code>else</code> <code>if</code> <code>(t-&gt;right == null)</code>

<code>                </code><code>t = t-&gt;left;</code>

<code>            </code><code>free</code><code>(tmp);</code>

<code>searchtree createtree()</code>

<code>    </code><code>// 一定要初始化指針，因為insert函數根據指針是否為空進行插入</code>

<code>    </code><code>searchtree t = null;</code>

<code>int</code> <code>main()</code>

<code>    </code><code>searchtree tree = createtree();</code>

<code>    </code><code>int</code> <code>i;</code>

<code>    </code><code>for</code> <code>(i = 0; i &lt; 10; i++)</code>

<code>        </code><code>tree = insert(tree, i);</code>

<code>    </code><code>printf</code><code>(</code><code>"max = %d\n"</code><code>, findmin(tree)-&gt;element);</code>

<code>    </code><code>printf</code><code>(</code><code>"max = %d\n"</code><code>, findmax(tree)-&gt;element);</code>

<code>    </code><code>return</code> <code>0;</code>

<code></code>

普通的二叉查找樹期望的任意操作的平均時間為o(logn)，而由于在删除的時候，我們總是用右子樹的最小節點代替被删除節點，導緻左子樹比右子樹深度更深。

參考：

《資料結構于算法分析》 p70、p73.