二叉樹的查詢效率為什么比鏈表高？

這里的二叉樹是指二叉排序樹。二叉樹也是常用的數(shù)據(jù)結構。一棵二叉樹由根節(jié)點（可以為空）和左右子樹（也是二叉樹）構成。

通常情況下，二叉樹的效率比線性鏈表高，因為二叉樹上的查詢、插入等操作即相當于二分法操作，時間復雜度為 O ( log ? 2 N ) O(\log_{2}{N}) O(log 2N)。但二叉樹也很容易失衡，極端情況下將退化為線性鏈表。

二叉樹用遞歸定義，其上的操作基本也是基于遞歸定義的。編程比較方便。

1、遍歷。二叉樹上的遍歷分為前序、中序和后序遍歷。本文只討論中序遍歷。

2、搜索。二叉樹的天生優(yōu)勢就在于搜索。相當于二分法查詢。效率比較高。

3、插入。在二叉樹的合適位置插入節(jié)點。當然，插入后必須仍然是二叉排序樹。

4、刪除。節(jié)點的刪除是二叉樹操作中比較難一點的。難點在于刪除節(jié)點后新節(jié)點的選取以及要保持該數(shù)據(jù)結構仍然是二叉排序樹。