二叉排序樹演算法空間復雜度

⑴ 二叉搜索樹和最優二叉搜索樹的時間復雜度各是多少

二叉查找樹（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 )

⑵ 數據結構的排序演算法中，哪些排序是穩定的，哪些排序是不穩定的

一、穩定排序演算法

1、冒泡排序

2、雞尾酒排序

3、插入排序

4、桶排序

5、計數排序

6、合並排序

7、基數排序

8、二叉排序樹排序

二、不穩定排序演算法

1、選擇排序

2、希爾排序

3、組合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

一個排序演算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。

做這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個對象間之比較，就會被決定使用在原先數據次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。

(2)二叉排序樹演算法空間復雜度擴展閱讀：

排序演算法的分類：

1、通過時間復雜度分類

計算的復雜度（最差、平均、和最好性能），依據列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且壞的性能是 O(n^2)。對於一個排序理想的性能是 O(n)。

而僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要 O(nlogn)。

2、通過空間復雜度分類

存儲器使用量（空間復雜度）（以及其他電腦資源的使用）

3、通過穩定性分類

穩定的排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。

⑶ 遞歸遍歷二叉樹的時間空間復雜度

時間復雜度和空間復雜度都是O(n)，n是結點個數

⑷ 前序遍歷二叉樹的空間復雜度是多少

因為都是要遍歷每一個節點，所以時空復雜度是一樣的。 時間復雜度O(n); 空間復雜度O(n)； （n為節點數）

⑸ 二叉排序樹為什麼不用來排序

我覺得是太浪費空間了，如果你需要排序[8，2，10，4]四個元素，你需要在堆區依次malloc四個節點的結構體，然後再把這些結構體構建成一棵二叉排序樹，之後中序輸出，得到有序的結果。但是這個過程malloc結構體消耗的空間可不少

⑹ 請問構造二叉搜索樹的時間復雜度下限是多少

時間復雜度是一個籠統的定義，因為演算法的時間復雜度不僅與語句頻度有關，還與問題規模及輸入實例中各元素的取值有關。具體而言，時間復雜度可以分為：最壞時間復雜度、最好時間復雜度、平均時間復雜度。
你舉的例子是最好情況下的時間復雜度，但是一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。

⑺ 計算機二級C語言主要考點

引用。。：
數據結構與演算法

1 演算法

演算法：是指解題方案的准確而完整的描述。
演算法不等於程序，也不等計算機方法，程序的編制不可能優於演算法的設計。
演算法的基本特徵：是一組嚴謹地定義運算順序的規則，每一個規則都是有效的，是明確的，此順序將在有限的次數下終止。特徵包括：
（1）可行性；
（2）確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性；
（3）有窮性，演算法必須能在有限的時間內做完，即能在執行有限個步驟後終止，包括合理的執行時間的含義；
（4）擁有足夠的情報。
演算法的基本要素：一是對數據對象的運算和操作；二是演算法的控制結構。
指令系統：一個計算機系統能執行的所有指令的集合。
基本運算和操作包括：算術運算、邏輯運算、關系運算、數據傳輸。
演算法的控制結構：順序結構、選擇結構、循環結構。
演算法基本設計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術、回溯法。
演算法復雜度：演算法時間復雜度和演算法空間復雜度。
演算法時間復雜度是指執行演算法所需要的計算工作量。
演算法空間復雜度是指執行這個演算法所需要的內存空間。

2 數據結構的基本基本概念

數據結構研究的三個方面：
（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構；
（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；
（3）對各種數據結構進行的運算。
數據結構是指相互有關聯的數據元素的集合。
數據的邏輯結構包含：
（1）表示數據元素的信息；
（2）表示各數據元素之間的前後件關系。
數據的存儲結構有順序、鏈接、索引等。
線性結構條件：
（1）有且只有一個根結點；
（2）每一個結點最多有一個前件，也最多有一個後件。
非線性結構：不滿足線性結構條件的數據結構。

3 線性表及其順序存儲結構

線性表由一組數據元素構成，數據元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在復雜線性表中，由若干項數據元素組成的數據元素稱為記錄，而由多個記錄構成的線性表又稱為文件。
非空線性表的結構特徵：
（1）且只有一個根結點a1，它無前件；
（2）有且只有一個終端結點an，它無後件；
（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個後件。結點個數n稱為線性表的長度，當n=0時，稱為空表。
線性表的順序存儲結構具有以下兩個基本特點：
（1）線性表中所有元素的所佔的存儲空間是連續的；
（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
ai的存儲地址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第一個元素的地址，k代表每個元素占的位元組數。
順序表的運算：插入、刪除。 （詳見14--16頁）

4 棧和隊列

棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織數據，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。
棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指針無變化。
隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。rear指針指向隊尾，front指針指向隊頭。
隊列是「先進行出」（fifo）或「後進後出」（lilo）的線性表。
隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。
循環隊列：s=0表示隊列空，s=1且front=rear表示隊列滿

5 線性鏈表

數據結構中的每一個結點對應於一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。
結點由兩部分組成：（1）用於存儲數據元素值，稱為數據域；（2）用於存放指針，稱為指針域，用於指向前一個或後一個結點。

2008-2-21 10:07 回復 鬥牛士 黛石Sara 2樓在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。
鏈式存儲方式即可用於表示線性結構，也可用於表示非線性結構。
線性鏈表，head稱為頭指針，head=null（或0）稱為空表，如果是兩指針：左指針（llink）指向前件結點，右指針（rlink）指向後件結點。
線性鏈表的基本運算：查找、插入、刪除。

6 樹與二叉樹

樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
二叉樹的基本性質：
（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結點；
（2）深度為m的二叉樹最多有2m-1個結點；
（3）度為0的結點（即葉子結點）總是比度為2的結點多一個；
（4）具有n個結點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數部分；
（5）具有n個結點的完全二叉樹的深度為[log2n]+1；
（6）設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數1，2，….n給結點進行編號（k=1,2….n），有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為int(k/2)；
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（也無右子結點）；
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
滿二叉樹是指除最後一層外，每一層上的所有結點有兩個子結點，則k層上有2k-1個結點深度為m的滿二叉樹有2m-1個結點。
完全二叉樹是指除最後一層外，每一層上的結點數均達到最大值，在最後一層上只缺少右邊的若干結點。
二叉樹存儲結構採用鏈式存儲結構，對於滿二叉樹與完全二叉樹可以按層序進行順序存儲。
二叉樹的遍歷：
（1）前序遍歷（dlr），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；
（2）中序遍歷（ldr），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；
（3）後序遍歷（lrd）首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點。

7 查找技術

順序查找的使用情況：
（1）線性表為無序表；
（2）表採用鏈式存儲結構。
二分法查找只適用於順序存儲的有序表，對於長度為n的有序線性表，最壞情況只需比較log2n次。

8 排序技術

排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法：（1）冒泡排序法，需要比較的次數為n(n-1)/2； （2）快速排序法。
插入類排序法：（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要o(n1.5)次比較。
選擇類排序法：（1）簡單選擇排序法,
最壞情況需要n(n-1)/2次比較；（2）堆排序法，最壞情況需要o(nlog2n)次比較。

⑻ 數據結構題目求答案

1 、在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找法查找關鍵字值20，需做的關鍵字比較次數為 4 。
2、抽象數據類型的三大要素為 數據 、 數據之間結構 和 操作 。
3、空格串的長度等於 0 。
4 、棧和隊列的區別僅在於 插入&&刪除 操作定義不相同。
5、設一個線性表的長度為50，P是指向線性鏈表的第10個元素，且P->next->next 指向第 11 元素。
6、二叉樹的第i層最多有 2^(i-1) 個結點，深度為k的二叉樹最多有 2^k-1 個結點。
7、利用MST性質來構造最小生成樹的兩種常用演算法為______PRIM___和___KRUSKAL_______。
8、常見的四類基本數據結構有：__棧______、____隊列_____、____樹______、______鏈表_____。（不確定，數據結構太多，究竟要寫那幾個？）
明天再打
二、判斷(對的打∨,錯誤打×, 10×2 = 20 分)
1、 由於鏈式存儲結構不要求邏輯上相鄰的元素在物理位置上也相鄰，因此，它具有隨機存取的優點( y)。
2、 赫夫曼樹是指帶權路徑長度WPL最小的二叉樹。一般而言，在給定條件下構造出的赫夫曼樹不是唯一的 (y )。
3、 非空完全二叉樹的一個任意結點的右子樹深度與其左子樹深度的差值或者為0或者為1( y )。
4、 先序遍歷二叉排序樹可得到一個關鍵字有序的序列( n) 。
5、 在n個結點的無向圖,若邊數大於n-1,則該圖必是連通圖 ( n )。
6、 在n個元素進棧後，它們的出棧順序和進棧順序一定正好相反( n )。
7、 往順序表中插人一個元素，平均要移動大約一半的元素(y )。
8、 類似於演算法的時間復雜度，空間復雜度可以作為演算法所需存儲空間的量度( y )。
9、 赫夫曼樹一定是滿二叉樹( n )。
10、 隊列的基本特徵是先進後出( n )。
三、選擇題（10×2=20分）
1、 有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？( B )
A. 2 3 4 1 5 6 B. 1 2 4 5 3 6
C. 6 4 5 1 2 3 D. 4 5 3 1 2 6
2、 一棵完全二叉樹上有1001個結點，其中葉子結點的個數是B
A. 254 B. 500
C. 250 D. 以上答案都不對
3、線性鏈表不具有的特點(A ).
A.隨機訪問 B.不必事先估計所需存儲空間大小
C.插入與刪除時不必移動元素 D.所需空間與線性表長度成正比
4、向順序棧中壓入新元素時,應當(B ).(此題需看書上棧定義)
A.先移動棧頂指針,再存入元素 B.先存入元素,再移動棧頂指針
C.先後次序無關緊要 D.同時進行
5、 具有65個結點的完全二叉樹的高度為( B). (根的層次號為1)
A.8 B.7
C.6 D.5
6、 由權值分別為3，8，10，2，6的葉子結點生成一棵哈夫曼樹，則其中非終端結點數為(A )。
A. 2 B. 3
C. 4 D. 5
7、 n個頂點的有向完全圖中含有向邊的數目最多為( D )
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
8、一個對象序列的排序碼為{46,79,56,38,40,84},採用快速排序以位於最左位置的對象為基準而得到的第一次劃分結果為(C ).
A.{38,46,79,56,40,84} B.{38,79,56,46,40,84}
C.{40,38,46,56,79,84} D.{38,46,56,79,40,84}
9、長度為11的哈希表中已經填有關鍵字17，60，29的記錄，採用二次探測再散列方法解決沖突，則填入關鍵字38其地址應該為( D)（哈希函數為h(key)=key mod 11）
A.4 B.5
C.3 D.6
10、在一個無向圖中,所有頂點的度數之和等於所有邊數的(B )倍.
A.3 B.2
C.1 D.1/2
打完了，為了數據結構考試攢人品~

⑼ 二叉樹的層次遍歷演算法

二叉樹的層次遍歷演算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：

之後大家就可以自己畫圖了，下面給出程序代碼：

[cpp] view plain

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

最後給出完成代碼的測試用例：124##57##8##3#6##

[cpp] view plain

#include<iostream>

#include<vector>

#include<deque>

using namespace std;

typedef struct tree_node_s {

char data;

struct tree_node_s *lchild;

struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

char c = getchar();

if (c == '#') {

*T = NULL;

} else {

*T = (tree_node_t*)malloc(sizeof(tree_node_t));

(*T)->data = c;

create_tree(&(*T)->lchild);

create_tree(&(*T)->rchild);

}

}

void print_tree(Tree T) {

if (T) {

cout << T->data << " ";

print_tree(T->lchild);

print_tree(T->rchild);

}

}

int print_at_level(Tree T, int level) {

if (!T || level < 0)

return 0;

if (0 == level) {

cout << T->data << " ";

return 1;

}

return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);

}

void print_by_level_1(Tree T) {

int i = 0;

for (i = 0; ; i++) {

if (!print_at_level(T, i))

break;

}

cout << endl;

}

void print_by_level_2(Tree T) {

deque<tree_node_t*> q_first, q_second;

q_first.push_back(T);

while(!q_first.empty()) {

while (!q_first.empty()) {

tree_node_t *temp = q_first.front();

q_first.pop_front();

cout << temp->data << " ";

if (temp->lchild)

q_second.push_back(temp->lchild);

if (temp->rchild)

q_second.push_back(temp->rchild);

}

cout << endl;

q_first.swap(q_second);

}

}

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

int main(int argc, char *argv[]) {

Tree T = NULL;

create_tree(&T);

print_tree(T);

cout << endl;

print_by_level_3(T);

cin.get();

cin.get();

return 0;

}

⑽ n個節點 高為H的二叉樹遍歷的時間復雜度和空間復雜度

因為都是要遍歷每一個節點，所以時空復雜度是一樣的。

如果所討論的網路是Internet或一個Intranet，許多物理網路節點是主機（即通過IP地址來標識的Internet節點）。所有的主機都是物理網路節點。

但是，一些數據鏈路層設備，如交換機、橋接器和WLAN接入點不擁有IP主機地址（除了有時用於管理目的），這些設備不認為是Internet節點或主機，但它們是物理網路節點和LAN節點。

(10)二叉排序樹演算法空間復雜度擴展閱讀：

電信網路節點：

在固定電話網路中，一個節點可能是公開或私有的電話交換局、遠程集線器或計算機，提供了一些智能網路服務。

在蜂窩通信中，交換點和資料庫，如基站控制器、歸屬位置寄存器、網關GPRS支持節點（GGSN）和GPRS服務支持節點（SGSN）都是節點的例子。蜂窩網路基站在此上下文中不被認為是節點。

在有線電視系統（CATV）中，這個術語有較廣的語境，通常與光纖節點相關。這可以被定義為由一個公共光纖接收器提供服務的特定地理范圍內的家庭或辦公地點。一個光纖節點通常使用特定光纖節點所服務的"家園通過"數來描述。