二叉查找树

一棵树是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.