浙江大學-數據結構-選講Complete Binary Search Tree-7.3.1

02-25

Complete Binary Search

完全二叉搜索樹

在這個標題裡面有兩個關鍵的概念，一個是完全二叉樹，一個是二叉搜索樹，這兩個概念都巧妙的融合到一道題裡面。

首先我們來花一點時間來回顧一下，什麼是二叉搜索樹，什麼是完全二叉樹。

二叉搜索樹就是一個二叉樹，然後以它的根節點為中心，左邊元素的關鍵字全部都小於根結點，而右邊的都比它大，就是左邊小，右邊大。

雖然這棵樹畫起來好像是一棵平衡樹的樣子，但是其實二叉搜索樹完全可能是一棵非常不平衡的樹，在極端情況下，它有可能是完全左斜的，或者是完全右斜的

那完全二叉樹呢，就是一棵真正的，非常平衡的二叉樹了，那它之所以被稱為完全二叉樹，是因為如果我們把它的結點從上到下，從左到右，一層一層的來標號的話，那麼這個標號從0標到9，一個都不能少，如果8這個結點缺掉的話，就不是完全的，完全二叉樹的意思就是一棵樹都不少，那題目的要求是我輸入了一系列的整數，要求我們把一系列的整數填到一個完全二叉樹的結構裡面去，同時這棵樹還應滿足二叉搜索樹的性質，也就是左子樹的值都比根結點要小，右邊的全部要比它大。而且它的左右子樹也分別都滿足二叉搜索樹遞歸的定義，那麼顯然現在這樣亂七八糟的填法肯定是不對的。最明顯的是根結點肯定不對，0是最小的數，如果0放在根節點的位置的話，左邊根本就不能有任何的子樹存在，因為它是最小的，就這個樣例而言，正確的填法應該如下：

我們看根結點填的是6，它的左子樹裡面所有的關鍵字都比它小，右邊的關鍵字都比它大，那遞歸的來看，它的左子樹根節點是3，左邊的3個元素都比它小，右邊的都比它大。以此類推，最後我們要求輸出的是這棵完全二叉樹層序遍歷的結果。也就是6，3，8，1，5，7，9，0，2，4，這是我們最後要得到的答案。

在解決這道題目之前，很重要的一個事情是決定，到底我們要用什麼數據結構去表示最後的這棵樹呢？那麼我們知道通常表示樹都有兩種方法，一種是用鏈表，一種是用數組。在這道題裡頭哪一種數據結構更好呢？在決定數據結構的時候，我們通常跟我們要做的事情是有關聯的。我們在這道題裡面要做什麼樣的操作呢？兩個基本的操作要做，一個是要把數字填到樹裡面去，換言之就是對這棵樹裡面的每一個結點訪問一次填寫一個數字，也就對應的某種遍歷，而最後我們要求是對這個樹做一個層序遍歷的輸出，所以基本的操作基本上都是在對這棵樹做遍歷。就遍歷這個操作而言，是用鏈表或者數組好像都是差不多的。在這個問題上分不出什麼高下來，那如果兩種數據結構在時間上沒有誰有明顯優勢的話，那我們就要來看一下這個空間。為什麼在很多情況下，我們都願意用鏈表去表示一棵樹，而不用數組呢？用數組是可以的，用數組的好處是不涉及任何指針的操作，指針的操作通常是比較危險比較耗時的，但是如果一棵樹，例如極端一點，它是一棵左斜的一棵樹的話，數組去存，你需要把不存在的結點空間也保留，這樣就很浪費空間，而鏈表就沒有這個問題，但是在我們這道題裡面，我們要解決的是完全二叉樹，是從根結點到最後一個葉子結點一層一層的走下來，沒有一個結點是空的，所以沒有一個元素的空間是浪費的，從這點上來說，用數組來表示這棵樹，還是相當合算的，另外一個合算的點，我們最後要求的是一個層序遍歷的輸出，如果我們用鏈表實現這棵樹的話，我們當然有層序遍歷的模板，就是得用一個隊列，有一堆進隊，出隊，各種操作去完成它的層序遍歷，但是用數組的話呢，它本來就是按照層序遍歷的順序存的，所以我其實什麼都不用做。最後直接把這個數組按照它的下標順序輸出就完了。從這一點上來說，數組完勝。於是我們就這麼愉快的決定了，要用數組來表示我們最後結果的這棵樹。