堆一定是完全二叉樹嗎？堆的邏輯結(jié)構(gòu)是一個完整的二叉樹，要求節(jié)點的關(guān)鍵字有一定的順序（最大的堆是父節(jié)點的關(guān)鍵字，大于等于子節(jié)點的關(guān)鍵字，最小的堆是父節(jié)點的關(guān)鍵字，小于或等于子節(jié)點的關(guān)鍵字）。對于完全二叉

堆一定是完全二叉樹嗎？

堆的邏輯結(jié)構(gòu)是一個完整的二叉樹，要求節(jié)點的關(guān)鍵字有一定的順序（最大的堆是父節(jié)點的關(guān)鍵字，大于等于子節(jié)點的關(guān)鍵字，最小的堆是父節(jié)點的關(guān)鍵字，小于或等于子節(jié)點的關(guān)鍵字）。對于完全二叉樹，即使節(jié)點有關(guān)鍵字，它不一定滿足順序要求完全二叉樹的定義：深度為K且節(jié)點數(shù)為N的二叉樹稱為完全二叉樹當(dāng)且僅當(dāng)每個節(jié)點對應(yīng)于深度為K的完全二叉樹中編號為1到N的節(jié)點時。特征：葉節(jié)點只能出現(xiàn)在樹的兩個最大級別上層次結(jié)構(gòu)；對于任何節(jié)點，如果其右分支的子代的最大級別為l，則其左分支的子代的最大級別必須為l或l1完全二叉樹：深度為K且冪為2（K）-1的二叉樹節(jié)點特征：每級上的節(jié)點數(shù)是完全二叉樹必須為的最大節(jié)點數(shù)一個完整的二叉樹。完全二叉樹不一定是完全二叉樹

在二叉排序樹中，每個節(jié)點的值都大于其左子樹上所有節(jié)點的值，小于其右子樹上所有節(jié)點的值。按中間順序遍歷二叉排序樹，得到有序序列。因此，二叉排序樹是滿足節(jié)點之間一定順序關(guān)系的二叉樹；堆是一個完整的二叉樹，每個節(jié)點的值都大于或等于其左右子節(jié)點的值（這里的討論以大根堆為例），所以堆是一個完整的二叉樹，滿足節(jié)點之間的某種順序關(guān)系。具有n個節(jié)點的二叉排序樹的深度取決于給定集合的初始順序。在最佳情況下，深度是logn（表示以2為底的對數(shù)），在最壞情況下，深度是n。在有n個節(jié)點的堆中，深度是堆對應(yīng)的完整二叉樹的logn。在二叉排序樹中，節(jié)點的右子節(jié)點的值必須大于該節(jié)點的左子節(jié)點的值；但不一定在堆中。堆僅將節(jié)點的值限制為大于（或小于）其左、右子節(jié)點的值，但不限制左、右子節(jié)點之間的大小關(guān)系。在二叉排序樹中，最小值節(jié)點是最左邊的底部節(jié)點，其左指針為空；最大值節(jié)點是最右邊的底部節(jié)點，其右指針為空。在大型根堆中，最小節(jié)點位于葉節(jié)點，而最大節(jié)點位于堆的頂部（根節(jié)點）。二叉排序樹是為動態(tài)搜索而設(shè)計的一種數(shù)據(jù)結(jié)構(gòu)。面向搜索操作。在二叉排序樹中搜索節(jié)點的平均時間復(fù)雜度為O（logn）；堆是為排序而設(shè)計的數(shù)據(jù)結(jié)構(gòu)，不面向搜索操作。因此，在堆中搜索節(jié)點需要遍歷，其平均時間復(fù)雜度為O（logn））。

完全二叉樹和滿二叉樹的區(qū)別？

區(qū)別在于最后一層。根據(jù)全二叉樹的定義，除最后一層外，每層中的所有節(jié)點都有兩個子節(jié)點。也就是說倒數(shù)第二層的每個節(jié)點都有兩個子節(jié)點，所以最后一層的節(jié)點數(shù)必須是倒數(shù)第二層的兩倍，所以最后一層不缺一個節(jié)點。樹右側(cè)的節(jié)點數(shù)可能是樹第二底部節(jié)點數(shù)的兩倍。