1樓：
書上有啊！、
定義：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)。
2樓：陶梓絮
bst就是二叉查詢樹，一個節點的權值，它大於它的左兒子權值，小於右兒子權值。這樣如果是一棵平衡的二叉樹，那麼在二叉樹裡面搜尋一個數值的複雜度就是log2(n)，n是節點個數
其實很簡單，就是插入，刪除，查詢三個操作。理想複雜度都是log2(n)
這個演算法書上都有。
bst沒什麼意義，因為如果退化成一條鏈複雜度就變成n了。
建議去看一看平衡樹，類似於splay之類的。
pascal常見問題，關於Pascal語言問題 完整的
第一題是百錢百雞問題拓展，屬於列舉問題 program p1 vara,b,c integer begin for a 1 to 35 do for b 1 to 50 do begin c 90 a b if a 15 b 10 c 5 500 thenwriteln a,b,c end end....
pascal教程，怎麼使用pascal
第一節 pascal語言的特點。資訊學奧林匹克競賽是一項益智性的競賽活動，核心是考查參賽選手的智力和使用計算機程式設計解題的能力。資訊學奧林匹克競賽要求參賽選手有如下能力 針對競賽題目中的要求構建數學模型，構造出有效的演算法和選用相應的資料結構，寫出高階語言程式，上機除錯通過。程式設計是資訊學奧林匹...
pascal題。幫忙，pascal題。幫忙！！！
我這樣做 整數列嘛 首先就先輸入一個n來表示這個整數列有多少個整數varn integer a array 1.1000 of integer i,j,k integer begin readln n for i 1 to n do read a i j 1 k 0 repeat if a j a ...