『壹』 刪除二叉查找樹BST中某一特定范圍中的所有元素
一開始檢查該樹的根節點是否在刪除范圍內，如果在則檢查它的左子樹和右子樹，對於左子樹而言，如果根節點還在范圍內，刪除該左子樹跟節點以及它的右子樹，繼續向左檢查，直到子樹的跟節點不再范圍內為止，然後子樹向下和它的右子樹檢查，如果右子樹跟在范圍內，則刪除右子樹跟和它的右子樹，然後子樹的右子樹連接到它原始右子樹的左子樹，直到為跟節點為止，對於該樹的右子樹而言，只需使用同樣方法反過來即可，最後全部子樹處理好了之後，對跟節點進行處理，只需刪除根節點然後重新建立二叉查找樹，這個方法的時間復雜度是O(h)，其中h代表樹的高度
『貳』 二叉搜索樹和最優二叉搜索樹的時間復雜度各是多少
二叉查找樹（BST，Binary Search Tree） ，又名二叉搜索樹或二叉檢索樹，是一顆滿足如下條件的樹：
1、每個節點包含一個鍵值
2、每個節點有最多兩個孩子
3、對於任意兩個節點x和y，它們滿足下述搜索性質:
a、如果y在x的左子樹里，則key[y] <= key[x]
b、如果y在x的右子樹里，則key[y] >= key[x]
最優二叉查找樹（Optimal BST，Optimal Binary Search Tree）
最優二叉查找樹是使查找各節點平均代價最低的二叉查找樹。具體來說就是：給定鍵值序列 K = <k1 , k2 , . . . , kn >，k1 < k2 <· · · < kn ，其中鍵值ki ,被查找的概率為pi ，要求以這些鍵值構建一顆二叉查找樹T，使得查找的期望代價最低（查找代價為檢查的節點數）。
下面是對於查找期望代價的解釋：
對於鍵值ki , 如果其在構造的二叉查找樹里的深度（離開樹根的分支數）為depthT(ki )，則搜索該鍵值的代價= depthT(ki ) +1（需要加上深度為0的樹根節點）。由於每個鍵值被查找的概率分別為pi ，i=1,2,3…,n。所以查找期望代價為：
E[T的查找代價] = ∑i=1~n (depthT(ki ) +1) · pi
時間復雜度
1、窮舉
窮舉構造最優二叉查找樹，其實就是這樣的一個問題：
給一個擁有n個數的已排序的節點，可以將其構造成多少種不同的BST（用來找到一個最優的二叉查找樹）？
設可以構造成T(n)個，那麼枚舉每一個元素作為根節點的情況，當第一個元素作為根節點時，其餘n-1個構成右子樹，無左子樹，是n-1情況時的子問題， 共T(n-1)種；當第二個元素作為根節點時，左子樹有1個元素，右子樹有n-2個元素，根據乘法原理共有T(1)T(n-2)種情況……依此類推得 到：T(n) = T(0)T(n-1) + T(1)T(n-2) + T(2)T(n-3) + ...... + T(n-2)T(1) + T(n-1)T(0)；此外，有T(0)=T(1)=1。
下面來求解T(n)：
定義函數 f(x) = T(0) + T(1) · x + T(2) · x2 + ......
那麼有：
f(x)2 = (T(0)2 ) + (T(0)T(1) + T(1)T(0)) · x + (T(0)T(2) + T(1)T(1) + T(2)T(0)) · x2 + ......
= T(1) + T(2) · x + T(3) · x2 + ......
= (f(x) - T(0)) / x
= (f(x) - 1) / x
這樣解方程得到 f(x) = [1 - (1 - 4x)1/2 ] / 2x
右邊進行泰勒展開，再與定義式比較最終得到： T(n) = (2n)! / (n!(n+1)!)
然後根據Stirling公式：n! ～ (2πn)1/2 · (n/e)n
於是有(2n)! / n!(n+1)! ～ (4n1/2 · 2n2n ) / (2n1/2 · nn · (2(n+1))1/2 · (n+1)n )
～ 4n · (n+1)-3/2 · (n/(n+1))n
～ 4n · n-3/2
因此最後得到窮舉方法構造最優二叉查找樹的時間復雜度： T(n) = O(4n · n-3/2 )
2、遞歸
實際上左右子樹是互不影響的，不需要窮舉所有左右子樹的組合，所以不需要用乘法原理，加法原理就可以了，這樣式子變為：
T(n) = T(0) + T(n-1) + T(1) + T(n-2) + T(2) + T(n-3) + ...... + T(n-2) + T(1) + T(n-1) + T(0)
= 2(T(0) + T(1) + T(2) + ...... + T(n-1))
= 3T(n-1)
所以得到T(n) = O(3n ) ，還是指數級的一個演算法
3、動態規劃
上面得到指數級演算法的原因在於，計算了很多重復的子樹情況，一些子樹的查找代價被計算了很多遍；而一棵樹如果是最優二叉搜索樹，那麼要麼它是空樹，要麼它 的左、右子樹也是最優二叉搜索樹，因此只需要將子樹的查找代價記錄下來，採用記憶化搜索或者是自底向上的動態規劃的方法，雖然需要消耗一定的空間，但可以 把時間復雜度從指數級降到多項式級，這些空間消耗也是可以接受的。
以下是採用自底向上的解法：
輸入：鍵值序列 K = <k1 , k2 , . . . , kn >，概率序列 P = <p1 , p2 , . . . , pn >
輸出：兩個二維數組，Price[i][j]表示ki 到kj 構成的最優子樹的查找代價，Root[i][j]表示表示ki 到kj 構成的最優子樹的根節點位置（用於重構最優二叉查找樹）
演算法1 ：
For 子樹大小size = 1 to n
For 子樹的起點start = 1 to (n - size + 1) //這樣子樹的終點即為 end = start + size - 1，長度為size
For 該子樹的所有節點作為根節點root = start to end
對於每個root，根據之前計算過的Price數組得到左右最優子樹的代價，可直接得到該子樹的代價price為：
左右子樹的最優子樹代價之和 + 所有節點的訪問概率之和（因為所有節點都下降了一層）
在內層循環中找到代價最小的price和root分別記錄在Price[start][end]和Root[start][end]中
下面分析這個演算法的時間復雜度：
由於除了計算出我們最後需要得到的Price和Root二維數組，還產生了部分冗餘的子樹，因此不能簡單的將演算法歸結為O(n2 )的演算法。
對於子樹大小為1時，我們考察了n個子樹；
對於子樹大小為2時，一共產生了(n - 1)個最優子樹，但是在我們的每次考察中，都將子樹的所有節點作為根節點考慮過一次，因此每得到1個大小為2的子樹，我們需要考察2個不同的子樹來找到一 個代價最小的，因此最後我們實際上考察了2(n - 1)個子樹；
對於子樹大小為3時，類似的，我們考察了3(n - 2)個子樹；
……
對於子樹大小為n時，我們考察了n個子樹。
最後，我們一共考察了T(n) = n + 2(n - 1) + 3(n - 2) + ...... + n個子樹。
求解這個公式依然可以借用之前的方法，定義函數 f(x) = 1 + 2x + 3x2 + ...... = (1 - x)-2
這樣一來 f(x)2 = T(1) + T(2) · x + T(3) · x2 + ......
再借用泰勒展開得到 T(n) = (n + 2)(n + 1)n/6 = O(n3 )
或者把所有項視為n2，則有 T(n) ≤ n2 + n2 + n2 + n2 + ...... = (n+1)n2 ≤ 2n3
把中間n/2項都視為n/4 · 3n/4的話，則有 T(n) ≥ n/2 · n/4 · 3n/4 = (3/32)n3
根據時間復雜度的定義有 T(n) = O(n3 )
下面介紹一個定理，可以藉此把動態規劃演算法的時間復雜度進一步降到O(n2 )，詳細的證明參見參考文獻：
定理1 ：Root[i][j-1] ≤ Root[i][j] ≤ Root[i+1][j] （Root數組定義見演算法1）
也就是說，演算法1的第3個For就可以不用循環子樹中的所有節點了，只要循環另兩個子樹的根節點之間的范圍就可以了。演算法如下，紅色的為修改的部分：
演算法2 ：
For 子樹大小size = 1 to n
For 子樹的起點start = 1 to (n - size + 1) //這樣子樹的終點即為 end = start + size - 1，長度為size
For 該子樹的所有節點作為根節點root = Root[start][end-1] to Root[start+1][end]
對於每個root，根據之前計算過的Price數組得到左右最優子樹的代價，可直接得到該子樹的代價price為：
左右子樹的最優子樹代價之和 + 所有節點的訪問概率之和（因為所有節點都下降了一層）
在內層循環中找到代價最小的price和root分別記錄在Price[start][end]和Root[start][end]中
在分析該演算法的時間復雜度時應注意，考察的子樹是與考察的內層循環中root數量一一對應的，而當start遞進時，前一個root的終點正好等於後一個root的起點（演算法中的紅色部分），也就是說對於固定的size來說，考察的root的范圍加起來應當首位相接 而且至多剛好覆蓋 所有節點，因此對於每個size，最多隻考察2n個root（這里縮放了一下），因此總共最多考察了2n · n = 2n2 個子樹；另一方面，Root數組中每一個值對應得到的一個最優二叉查找樹，也即至少需要考察n2 個子樹。因此根據定義得到 T(n) = O(n2 )
『叄』 pascal演算法問題
書上有啊！、
定義：
BST 待遍歷的二叉樹；
postorder 後序遍歷規則；
first_node 按後序遍歷規則遍歷時將訪問的第一個結點；
current_node 當前將要訪問的結點；
next_node 根據postorder規則，在current_node之後即將訪問的後繼結點；
parent(node) 結點node的父結點；
lchild(node) 結點node的左孩子；
rchild(node) 結點node的右孩子。
演算法步驟：
1 找到BST中以postorder方式遍歷時將訪問的第一個結點，即first_node；
2 令current_nodeçfirst_node；
3 查找current_node的後繼結點next_node：
3.1 若current_node之父結點為空，演算法結束；
3.2 若current_node為其父結點的左孩子，且其父結點無右子樹，則next_nodeçparent(current_node)；
3.3 若current_node為其父結點的左孩子，且其父結點有右子樹，則令pçparent(current_node)，於是next_node為結點p之右子樹中以postorder方式遍歷時將訪問的第一個結點；
3.4 若current_node為其父結點之右子樹，則next_nodeçparent(current_node)；
4 訪問current_node；
5 令current_nodeçnext_node，轉到3。
滿二叉樹時之復雜度
不妨令滿二叉樹的深度為k（二叉樹的層數記為i=1, 2, …, k-1），則總的結點數n=2k-1。對於一棵深度為k的滿二叉樹，按後序遍歷規則查找第一個結點的操作步驟數為k-1。對滿二叉樹的第i層結點(i=1, 2, …, k-1)，有2i-1個結點是其父結點的左孩子，有2i-1個結點是其父結點的右孩子。對於第i層的每個左孩子結點，需要按後序遍歷規則查找其後繼結點，此時父結點之右子樹的深度為k-i，根據前述說明，則每個左孩子結點需要執行k-i-1次查找後繼結點的操作，總的操作次數為2i-1 * (k-i-1)次。對於第i層的每個右孩子結點，其父結點即為其後繼結點，因此對每個右孩子結點所需要執行的操作為1，因此第i層右孩子總的操作數為2i-1 * 1。由此，第i層總的操作數為2i-1 * (k-i-1) + 2i-1 * 1=2i-1 * (k-i)。將以上所有層累加起來即得到除根結點之外的所有層上的操作數(i=1, 2, …, k-1)，不妨設為α：
α= 21-1 * (k-1) + 22-1 * (k-2) + … + 2k-2 * 1 = 20 * (k-1) + 21 * (k-2) + … + 2k-2 * 1
則有
α= 2α-α= … = 2k – k – 1
以上就是除根結點之外所有結點上的操作總數。當處理根結點時，實際上只需要做一次判斷即可。於是演算法總的操作次數T = α+1 = 2k – k。又由前面的假設可知n=2k-1，因此2k=n+1，k=lg(n+1)。故可得演算法總的操作數為：
T = n+1-lg(n+1)
故，該演算法的復雜度為O(n)。
『肆』 求基於BST技術的PCB測試方法
目前隨著使用大規模集成電路的產品不斷出現，相應的PCB的安裝和測試工作已越來越困難。雖然PCB的測試仍然使用在線測試技術這一傳統方法，但是這種方法由於晶元的小型化及封裝而變得問題越來越多。現在一種新的測試技術——邊界掃描測試技術已逐步得到發展，大多數的ASIC電路和許多中等規模的設備已開始利用邊界掃描測試技術進行設計。BST技術是按照IEEE1149.1標准，提供了一套完整的測試方案。在實際的測試中，它不需要藉助於復雜和昂貴的測試設備，並且提供一種獨立於電路板技術的測試方法。採用邊界掃描測試技術進行集成電路設計和PCB設計，其最大的優點是測試過程簡單，顯著地減少了生產、實驗、使用和維修過程中的測試診斷時間，從而極大地降低了成本。文章引自深圳宏力捷電子！
1 BST的基本組成
BST電路按照IEEE1149.1標准構成，其中含有測試存取通道TAP及控制器、指令寄存器IR和測試數據寄存器組TDR。測試存取通道TAP是一個5芯引腳(其中l芯為復位端)的連接器。TAP控制器是一個16狀態的狀態機，可產生時鍾信號和各種控制信號(即產生測試、移位、捕獲和更新等信號)，從而使指令或測試數據移入相應的寄存器，並控制邊界掃描測試的各種工作狀態。
1.1測試時鍾輸入端TCK
TCK信號允許集成電路IC的邊界掃描部分與系統內的時鍾同步並獨立工作。
1.2測試方式選擇輸入端TMS
測試方式選擇TMS引腳為控制信號，其決定TAP控制器的工作狀態。TMS須在TCK的上升沿之前建立。
1.3測試數據輸入端TDI
在測試時鍾脈沖TCK的上升沿，通過TDI串入的數據移入指令寄存器或測試數據寄存器，TAP控制器決定移入的數據是指令或測試數據。
1.4測試數據輸出端TDO
在測試時鍾脈沖TCK的下降沿，通過TDO從指令寄存器或測試數據寄存器串出數據，TAP控制器決定串出的數據是指令或測試數據。
2 PCB的測試系統
2.1 測試系統結構
其硬體包含通用的PC機、BST測試儀和串列BST信號電纜(含有4路信號的匯流排，其圖中數字含義如下:1為TDI、2為TCK、3為TMS、4為TDO)。測試儀通過標准並口與PC機連接，通過串列信號電纜與PCB上的測試存取口TAP相連。
假設PCB上有A、B、C三個模塊，模塊可以是由單個晶元或多個晶元構成的。它們是按IEEE1149.1標准設計的，即在晶元的I/O管腳處增加BS寄存器(模塊中虛線經過的位置)，可進行邊界掃描測試。若所設計的數字系統或設備有多塊PCB，可通過串列信號電纜與PCB相連。使用者可以通過編程來靈活選擇需測試的晶元、模塊或整個PCB。
2.2 測試系統原理
測試者可根據PCB的網表和器件模型，利用PC機軟體編程自動生成檢測電路故障的測試圖形。PC機應有兩個至少32位I/O管腳的插板，這樣可形成32位讀/寫管腳，方便讀和寫操作。
測試軟體應包括預處理器和執行單元。其中預處理器讀出測試圖形並獲取這些圖形可能的關系，得到的結果是一組文件，包括存儲和控制信息。執行單元裝入上述文件，然後執行測試。過程為先讀存儲信息，把數據置於輸入埠，從適當的輸出埠讀取數據，並同預期的結果進行比較。若發現故障，將產生一個故障報告，並標明故障的位置，最後加入診斷程序，給出故障的具體位置。
2.3測試內容
·測試PCB的I/O管腳的連線。因為PCB的I/O管腳為測試儀提供了唯一的存取通道;
·測試PCB上IC晶元的完整性，在晶元的裝配過程中，IC晶元或許己損壞。可採用內建自測試和內部測試，以驗證晶元的好壞;
·測試PCB上IC晶元互連的開路與短路故障，可採用外部測試加以驗證:
·測試PCB上匯流排的完整性，通過其測試可檢測與匯流排相連的IC晶元I/O管腳是否存在開路故障。
隨著BST技術的不斷發展，PCB測試將逐步完善。由於可編程集成電路的大量使用，PCB測試的靈活性和適用性將會提高，而相應的測試系統的成本將會減少。設計者可以在PCB上全部採用可編程邏輯的集成電路，只要通過軟體編程即可修改晶元邏輯，從而做成通用的PCB，使PCB電路板可以完成不同的功能。這樣邊界掃描測試技術將使得PCB測試更加方便快捷，極大地降低測試成本。
『伍』 數據結構問題
很久沒碰樹了，不知道是不是這意思。
這個是普通的二叉樹么，左邊的小，右邊的大。
現在變成左邊的大，右邊的小而已，取原來根節點，把原來的節點重新插入變新樹
最大的就在最左邊。
/***************
定義結構體tree
****************/
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
}tree;
tree* creat_leaf(int value)
{
tree* new=(tree *)malloc(sizeof(tree));
new->data=value;
new->left=NULL;
new->right=NULL;
return new;
}
/*************
樹的插入
*************/
void *insert_tree(tree* root,int value)
{
if(root != NULL)
{
if(value < root->data) //這是原來樹的插入方法，改此處判斷條件就可以了啊
{
root->left = (tree*)insert_tree(root->left,value);
}
else if(value > root->data)//.....
{
root->right = (tree*)insert_tree(root->right,value);
}
return root;
}
creat_leaf(value);
}
『陸』 二叉搜索樹（BST）滿足一下條件：1滅個節點包含一個鍵值 2每個節點最多兩個孩子 3對於任意兩個節點滿足
您插入順序從0 size-1個。根據該方案，始終是大於當前值。那麼，到底是總是正確的。
所以你總是會產生變形正確的樹枝。
前太深了，所以，當你的價值超過一定數量的堆棧溢出。
如果我說是，你的程序將永遠不會崩潰的開始，但在運行，相當於在4705-4706崩潰時壓入。你的程序復雜度為O（N ^ 2），所以它是緩慢的。
如果您使用的是VC，或顯示當前堆棧崩潰，gdb調試器，你可以看到一個壯觀的千層UIinsert。哈哈！
『柒』 三， 解釋下列術語 1， 靜態鏈表 2， 無向連通圖 3， 排序 4， 堆棧 5， 二叉排序樹
靜態鏈表：用數組描述的鏈表，即稱為靜態鏈表。但是這種存儲結構，仍需要預先分配一個較大的空間，但在作為線性表的插入和刪除操作時不需移動元素，僅需修改指針，故仍具有鏈式存儲結構的主要優點。
無相連通圖：撤去任意一個節點的信息，求出剩下的(n-1)*(n-1)矩陣的行列式，此值即為這個無向連通圖的生成樹個數。復雜度為O(n^3)
排序是計算機內經常進行的一種操作，其目的是將一組「無序」的記錄序列調整為「有序」的記錄序列。分內部排序和外部排序。
堆棧都是一種數據項按序排列的數據結構，只能在一端(稱為棧頂(top))對數據項進行插入和刪除。要點：堆：順序隨意棧：後進先出。
二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：
①若它的左子樹非空，則左子樹上所有結點的值均小於根結點的值；
②若它的右子樹非空，則右子樹上所有結點的值均大於根結點的值；
③左、右子樹本身又各是一棵二叉排序樹。
上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹實際上是滿足BST性質的二叉樹。
『捌』 BST是什麼意思!
1、BST（貝斯特），公司原名：深圳貝斯特機械電子有限公司，成立於一九九一年，是專門從事貝斯特點鈔機、點驗鈔機、驗鈔儀、票據鑒別儀、復點機、捆紮機、扎鈔機、錢箱開箱鉗、反假貨幣宣傳工作站等金融機具的開發、生產、銷售的中外合資企業，注冊資金2600萬港幣。
2、二叉搜索樹（BST）又稱二叉查找樹或二叉排序樹。一棵二叉搜索樹是以二叉樹來組織的，可以使用一個鏈表數據結構來表示，其中每一個結點就是一個對象。
二叉搜索樹性質
設x是二叉搜索樹中的一個結點。如果y是x左子樹中的一個結點，那麼y.key≤x.key。如果y是x右子樹中的一個結點，那麼y.key≥x.key。
在二叉搜索樹中：
1、若任意結點的左子樹不空，則左子樹上所有結點的值均不大於它的根結點的值。
2、若任意結點的右子樹不空，則右子樹上所有結點的值均不小於它的根結點的值。
3、任意結點的左、右子樹也分別為二叉搜索樹。
以上內容參考：網路-二叉搜索樹、網路-BST