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

核心演算法

上次講到用鏈表或者數組去寫完全二叉搜索樹的利弊，接下來就要考慮核心演算法了。

首先我們來解決一下樣例輸入對應的問題，然後再從解決樣例問題的過程中去找規律，來得到我們真正的核心演算法，那麼這個題一開始要怎麼想呢？首先要看一下二叉搜索樹的概念，在一棵二叉搜索樹裡面，根結點左邊所有的元素都比它小，右邊的都比它大，那換言之，如果我知道它的左子樹一共包含了多少個結點，那我就知道根結點上要放的數字一定是從小到大排第幾位的那個數字，那我怎麼能夠確定的知道左子樹有多少個結點呢？這就用到了完全二叉樹的概念，因為給定了一個固定的n以後，這個完全二叉樹的結構是固定的，所以我可以非常準確的算出來它的左邊一共有多少個結點，那在這種情況下呢，首先我把我的輸入的序列從小到大排一個序，然後根據這棵完全二叉樹一共有多少個結點，這個總結點的個數，我是可以導出一個公式，來精確的計算它的左子樹，一共有多少個結點，那比如說在這個問題裡面，n是等於10的，我一共有10個結點，那麼我可以很準確的算出來，它的左子樹必定含有6個結點，也就是說根結點一定是從小到大排第7位的那個數字，那在這裡頭我先數過6個數，第7個數就一定是它的根結點，同時也就決定了後面的3個數一定是屬於它的右子樹的，於是在這個位置上呢(指根結點)我實際上應該填的就是6

在填完這個6以後呢，你應該已經看出來了，我們就可以很容易的，遞歸的去分別解決左邊和右邊的問題，因為什麼呢？因為如果這棵樹是一棵完全二叉樹的話，它的左子樹和右子樹，一定也是完全二叉樹，於是我們就完全變成了左邊和右邊完全小一號的問題，比如說左邊就含有6個結點，6個結點的完全二叉樹，它根結點的左子樹一定包含3個結點，於是呢，我從這數前面3個數，我就知道3一定要被填到根結點這個位置的

同時它的右子樹一定包含4和5，然後就可以把3填在根結點處，然後遞歸去解決它的左子樹的問題，這個左子樹包含3個結點，作為一棵完全二叉樹來說它的結構是非常簡單的，

它的根節點應該是中間的1，左邊是0，右邊是2，然後遞歸的去考慮它的右子樹，具有兩個結點的完全二叉樹一定是長成(4,9)這個樣子的，就是一個根結點加一個左子樹，所以根結點一定是5，左子樹一定是4。右子樹就更簡單，3個結點，然後它是完全對稱的，所以它的根結點是中間的8，左邊是7，右邊是9。

這樣就完成了我們的填寫，從剛才我們填寫的過程中，這實際上是對這棵樹的一種先序遍歷，每到一個根結點的時候，我就要先從這個序列裡面找到誰應該是根結點，先把它填上，然後再遞歸的解決左邊，遞歸的去解決右邊，這就是一個非常典型的先序遍歷的應用，那麼代碼要怎麼寫呢？

傳進去的參數主要有這麼3個，我們來分別的看一下，假設在調用這個solve之前，我已經把輸入序列存在一個數組A裡面，然後把這個數組A做了一個從小到大的排序，就是排序以後的輸入序列是放在A裡面的，當我在遞歸調用去解決這個問題的時候呢，我對應的是A這個序列裡面的某一小段，這個ALeft存的就是當前這一段最左邊元素的下標，ARight就是存的是最右邊元素的下標，TRoot是什麼東西呢？我們把最後結果生成的那棵樹也存在另外一個數組叫做T裡面，TRoot對應的是當前我們要考慮的這棵子樹，它的根結點所在的位置，這個元素的下標存在TRoot裡面，在main函數裡面最開始調用solve這個函數的時候，在A的起始點，就是A的第0個元素，A的終止點就是A的最後一個元素，就是N-1是它的下標，對應這棵結果樹它是一個完全二叉樹，它的根結點一定存在T0這個位置，所以TRoot最開始傳進去的是0，整個函數要完成的任務，就是從A傳進去的這一段裡面選出一個正確的數字填到結果樹TRoot的位置上，好了，做好了一切準備工作，就開始幹活了。要乾的第一件事，要想到solve是一個遞歸的函數，遞歸函數必須要有一個停止的條件，什麼時候停止呢？先計算一下n當前傳進來這一段數組元素一共有多少個，那麼就是最右邊的下標減去最左邊的下標加上1，就得到了這一段裡面元素的總個數(n=ARight - ALeft + 1),如果n等於0，那就沒有任何元素可以處理了，這是它的最小情況，直接return什麼事情都不做，如果n不等於0的話，那我們要選一個正確的數字，填在根結點的位置上，這個正確的數字要怎麼選呢？首先要算出來它的左子樹到底包含多少個結點，然後那個左子樹右端點的下一個元素就應該放在根結點的位置上，要怎麼樣知道左子樹的規模呢？這還不是一個很簡單的事情，在這呢，我就先把它記成一個函數(L = GetLeftLength(n)),傳進去的這個n呢，是當前這棵完全二叉樹總結點的個數，返回的就應該是有n個結點的樹，就不是一棵普通的樹，就是一棵完全二叉樹，它左子樹一共有多少個結點，現在先不管它是怎麼做的，總之它把這個樹給返回來了，也就是左邊一共有L個元素(L = GetLeftLength(n)),那麼根結點的元素就應該填什麼呢？A[ALeft + L]這個位置上這個源應該被填到T的根結點位置上去(T[TRoot] = A[ALeft + L]),到此為止，我們就應該把這個函數應該乾的活幹完了，接下來就是要遞歸的解決左邊遞歸的解決右邊，於是我們得把左邊給定義好，右邊也要定義好，左邊的A的元素值是很明顯的，就是從ALeft一直指到哪裡呢？指到這個元素的前一個，把這一段作為A的左段，傳到下一個solve裡面去，但是左邊要傳進去的TRoot應該傳什麼呢？當前的根結點的下標是TRoot，這個結點在完全二叉樹裡面左孩子的下標應該是多少呢？那麼在之前講堆的時候，應該講過，如果根結點是TRoot的話，那麼它的左孩子的下標應該是TRoot乘以2，但是你要小心，那是在堆裡面，堆的特點是它的第0個元素，是不存真實值的，它只存一個哨兵，但是在我們這個結果樹裡面，我的根結點是直接放在0裡面的，是從0開始算下標的，而在這個微小的差別之下，它的左孩子就不是TRoot乘以2，而是TRoot乘以2再加1，在頭腦里想一下，我從0開始，第0個元素它的左孩子下標應該是1，也就是2乘以0再加上1，它的右孩子的TRoot的下標就很簡單，就是左孩子加1，就是它的右孩子，如果你不放心，在往下推一下看看，1它的左孩子下標應該是什麼，應該是3對不對，就是1乘以2再加1得到3，右孩子下標就是4，以此類推，這樣我們就得到了在T這棵樹裡面，當前這個根結點左孩子的下標和右孩子的下標，現在我們就可以遞歸的去解決左邊，遞歸的去解決右邊，解決左邊的時候呢，它的左端點還是ALeft不變，右端點是你剛才取掉了根結點那個元素的前一個值，所以是ALeft+L-1,然後這邊傳的是TRoot左孩子的下標(solve(ALeft, ALeft+L-1, LeftTRoot)),LeftTRoot是下一個要填的根結點，右邊呢，對應的應該是剛才那個根結點加1，是右邊的左端點，然後右邊的右端點是不變的，傳進去根結點的下標就是TRoot它的右孩子，

那麼到此為止，我們這個核心演算法就描述完了，

但是真的要去實現這個程序的時候，還有兩個很關鍵的步驟，第一件事先得會排序，排序演算法會在很後面的時候才給大家專門的介紹，那在這裡頭要用到排序呢，先給大家介紹一個比較簡單的現成的庫函數，可以先湊合著用著。

這裡要跟大家介紹的是C語言里很好用的庫函數叫做qsort，你要用qsort的話，你先要#include <stdlib.h>,把這個頭文件包進去，然後就可以在main函數裡面去對這個數組做預處理，調用qsort，要傳進去的參數是有這麼4個關鍵的參數，qsort的第一個參數要傳進去的是待排序序列的首元素的位置，也就是說如果我們把讀進來的原始的輸入存在一個叫A的數組裡面，那我只要把這個數組的名字放在這就可以了，後面這個N呢，是你待排序列的總長度，也就是一共要排n個元素，第三個參數傳的是你要排的那個元素的大小，那在這道題裡面，我們只是要對整數做一個排序，所以傳進去的就是sizeof(int),如果在後面我們調用qsort做更複雜的排序的時候，有的時候我們需要傳入一個結構體，那麼這個就應該是sizeof那個結構體的大小，有趣的是最後一個參數，這個最後一個參數不是一個變數，它是一個函數的名字，這個函數我在這給它取一個名字叫做compare,你可以給它取叫別的名字，這個compare要做的事情是什麼呢，就是要比較兩個元素的大小，因為qsort是通過比較一對元素的大小來決定哪個元素在前面，哪個元素應該在後面，就我們這道題裡面，compare應該怎麼寫呢？

這是compare的標準介面，不管前面給它取什麼名字，它應該返回一個整數，讓它傳進去的是兩個待比較元素的指針，它應該返回的整數，是返回3種整數之一，可以返回一個負數，可以返回一個0，也可以返回一個正數，然後qsort就根據這個compare返回來的是負數，是0，還是正數，來決定這兩個元素誰應該在前面，誰應該在後面，還是徹底的不做交換，那麼在我們這個問題裡面，我可以非常簡單的把這個return值就寫成a減去b的值，將來你要用qsort對更複雜的數據結構做排序的時候，這個compare可以寫的非常複雜，總之這個compare函數是要你自己根據實際情況來實現的。