1樓:匿名使用者
1. 面對這樣的場景,選擇父親孩子結構的方式組建二叉樹就很容易了。
2. 如果是普通的左右結內點結構組建的二叉樹容,那就遍歷吧。
int getfather(treenode *root, treenode *a, treenode *b)
}if (root == a || root == b)return 1 + num;
else
return num;}
如何計算兩個節點的公共父節點到兩個節點的最小距離
2樓:最愛秋天的傳說
由於有父節點指標,這道題目的難度一下子就降低了許多。
思路一:我們首先找到兩個節點的高度差,然後從較靠近根結點的一層開始向上找,若父節點為同一節點則該節點為解。
int getheight(treenode *node)return height;
}treenode* lowest***monancestor(treenode* first,treenode* second)
} else
}while (first != second)return first;
}思路二:若允許浪費空間,那麼可以用兩個stack來儲存從first和second到根結點的各個節點,然後出棧時比較地址是否一致,最後一個地址一致的節點為解。
如何快速的查詢到二叉樹中任意兩個節點的最底層的公共父節點
3樓:匿名使用者
如果二叉樹是三叉連結串列儲存或者順序儲存,從2個結點向著根走,可以很快找到
如果是二叉連結串列儲存,可以使用非遞迴的後序遍歷,分別遍歷到這2個結點時,比較一下當時棧裡的情況就可以了
在二叉樹中有兩個結點m和n,如果m是n的祖先,可以找到從m到n的路徑的遍歷方式是
4樓:匿名使用者
觀察棧中的序列。遍歷一棵二叉樹時會使用棧,當利用後序遍歷到目標結點n時,棧中的序列就為n結點的全部父結點(棧為一個陣列)。
結點總數n=n0+n1+n2。設b為分支總數,因為除根節點外,其餘結點都有一個分支進入,所以n=b+1。又因為分支是由度為1或2的結點射出,所以b=n1+2n2。
綜上:n=n0+n1+n2=b+1=n1+2n2+1,得出:n0=n2+1。
所以本題,度為2額節點有m個。
葉子節點n0=n2+1=m+1。
5樓:mighty之
大家可能有一個思維慣性就是在visit()時得到的序列為路徑,其實正確的思想應該是觀察棧中的序列。遍歷一棵二叉樹時會使用棧,當利用後序遍歷到目標結點n時,棧中的序列就為n結點的全部父結點(棧為一個陣列)。
可以自己畫一個二叉樹來後序遍歷一遍注意觀察棧中的元素而不是visit()的元素!
6樓:可靠的青春舞曲
四、遍歷二叉樹二叉樹是一種非線性的資料結構,在對它進行操作時,總是需要逐一對每個資料元素實施操作,這樣就存在一個操作順序問題,由此提出了二叉樹的遍歷操作。所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結點一次且僅一次的過程。這裡的訪問可以是輸出、比較、更新、檢視元素內容等等各種操作。
二叉樹的遍歷方式分為兩大類:一類按根、左子樹和右子樹三個部分進行訪問;另一類按層次訪問。下面我們將分別進行討論。
1、按根、左子樹和右子樹三部分進行遍歷遍歷二叉樹的順序存在下面6種可能:tlr(根左右),trl(根右左)ltr(左根右),rtl(右根左)lrt(左右根),rlt(右左根)其中,trl、rtl和rlt三種順序在左右子樹之間均是先右子樹後左子樹,這與人們先左後右的習慣不同,因此,往往不予採用。餘下的三種順序tlr、ltr和lrt根據根訪問的位置不同分別被稱為先序遍歷、中序遍歷和後序遍歷。
(1)先序遍歷若二叉樹為空,則結束遍歷操作;否則訪問根結點;先序遍歷左子樹;先序遍歷右子樹。(2)中序遍歷若二叉樹為空,則結束遍歷操作;否則中序遍歷左子樹;訪問根結點;中序遍歷右子樹。(3)後序遍歷若二叉樹為空,則結束遍歷操作;否則後序遍歷左子樹;後序遍歷右子樹;訪問根結點。
例如。以下是一棵二叉樹及其經過三種遍歷所得到的相應遍歷序列二叉樹的兩種遍歷方法:(1)對一棵二叉樹中序遍歷時,若我們將二叉樹嚴格地按左子樹的所有結點位於根結點的左側,右子樹的所有結點位於根右側的形式繪製,就可以對每個結點做一條垂線,對映到下面的水平線上,由此得到的順序就是該二叉樹的中序遍歷序列(2)任何一棵二叉樹都可以將它的外部輪廓用一條線繪製出來,我們將它稱為二叉樹的包線,這條包線對於理解二叉樹的遍歷過程很有用。
由此可以看出:(1)遍歷操作實際上是將非線性結構線性化的過程,其結果為線性序列,並根據採用的遍歷順序分別稱為先序序列、中序序列或後序序列;(2)遍歷操作是一個遞迴的過程,因此,這三種遍歷操作的演算法可以用遞迴函式實現。(1)先序遍歷遞迴演算法voidpreorder(btreebt)(2)中序遍歷遞迴演算法voidinorder(btreebt)}(3)後序遍歷遞迴演算法voidpostorder(btreebt)}2、按層次遍歷二叉樹實現方法為從上層到下層,每層中從左側到右側依次訪問每個結點。
下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。voidleveloreder(qbtreebt)}
五、典型二叉樹的操作演算法1、輸入一個二叉樹的先序序列,構造這棵二叉樹為了保證唯一地構造出所希望的二叉樹,在鍵入這棵樹的先序序列時,需要在所有空二叉樹的位置上填補一個特殊的字元,比如,'#'。在演算法中,需要對每個輸入的字元進行判斷,如果對應的字元是'#',則在相應的位置上構造一棵空二叉樹;否則,建立一個新結點。整個演算法結構以先序遍歷遞迴演算法為基礎,二叉樹中結點之間的指標連線是通過指標引數在遞迴呼叫返回時完成。
演算法:btreepre_create_bt()}2、計算一棵二叉樹的葉子結點數目這個操作可以使用三種遍歷順序中的任何一種,只是需要將訪問操作變成判斷該結點是否為葉子結點,如果是葉子結點將累加器加1即可。下面這個演算法是利用中序遍歷實現的。
演算法:voidleaf(btreebt,int*count)}3、交換二叉樹的左右子樹許多操作可以利用三種遍歷順序的任何一種,只是某種遍歷順序實現起來更加方便一些。而有些操作則不然,它只能使用其中的一種或兩種遍歷順序。
將二叉樹中所有結點的左右子樹進行交換這個操作就屬於這類情況。演算法:voidchange_left_right(btreebt)}4、求二叉樹的高度這個操作使用後序遍歷比較符合人們求解二叉樹高度的思維方式。
首先分別求出左右子樹的高度,在此基礎上得出該棵樹的高度,即左右子樹較大的高度值加1。演算法:inthight(btreebt)+1;}}
六、樹、森林與二叉樹的轉換1、樹、森林轉換成二叉樹將一棵樹轉換成二叉樹的方法:將一棵樹轉換成二叉樹實際上就是將這棵樹用孩子兄弟表示法儲存即可,此時,樹中的每個結點最多有兩個指標:一個指標指向第一個孩子,另一個指標指向右側第一個兄弟。
當你將這兩個指標看作是二叉樹中的左孩子指標和孩子右指標時,就是一棵二叉樹了。特點:一棵樹轉換成二叉樹後,根結點沒有右孩子。
將森林轉換成二叉樹的方法與一棵樹轉換成二叉樹的方法類似,只是把森林中所有樹的根結點看作兄弟關係,並對其中的每棵樹依依地進行轉換。2、二叉樹還原成樹或森林這個過程實際上是樹、森林轉換成二叉樹的逆過程,即將該二叉樹看作是樹或森林的孩子兄弟表示法。比如,若二叉樹為空,樹也為空;否則,由二叉樹的根結點開始,延右指標向下走,直到為空,途經的結點個數是相應森林所含樹的棵數;若某個結點的左指標非空,說明這個結點在樹中必有孩子,並且從二叉樹中該結點左指標所指結點開始,延右指標向下走,直到為空,途經的結點個數就是這個結點的孩子數目。
第3節哈夫曼樹及其應用1、哈夫曼樹的定義及特點在二叉樹中,一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。這三棵二叉樹的帶權路徑長度分別為:wpl1=10*2+11*2+3*3+6*3+7*3+9*3=117wpl2=3*1+6*2+7*3+9*4+10*5+11*5=177wpl3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼樹的一個重要特點是:
沒有度為1的結點。2、構造哈夫曼樹的過程:(1)將給定的n個權值作為n個根結點的權值構造一個具有n棵二叉樹的森林,其中每棵二叉樹只有一個根結點;(2)在森林中選取兩棵根結點權值最小的二叉樹作為左右子樹構造一棵新二叉樹,新二叉樹的根結點權值為這兩棵樹根的權值之和;(3)在森林中,將上面選擇的這兩棵根權值最小的二叉樹從森林中刪除,並將剛剛新構造的二叉樹加入到森林中;(4)重複上面(2)和(3),直到森林中只有一棵二叉樹為止。
這棵二叉樹就是哈夫曼樹。例如:假設有一組權值,下面我們將利用這組權值演示構造哈夫曼樹的過程。
它的帶權的路徑長度為:wpl=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713.判定樹在很多問題的處理過程中,需要進行大量的條件判斷,這些判斷結構的設計直接影響著程式的執行效率。例如,編制一個程式,將百分制轉換成五個等級輸出。
大家可能認為這個程式很簡單,並且很快就可以用下列形式編寫出來:if(socre<60)printf("bad");elseif(socre<70)printf("pass");elseif(score<80)printf("general");elseif(score<90)printf("good");esleprintf("verygood");在實際應用中,往往各個分數段的分佈並不是均勻的。下面就是在一次考試中某門課程的各分數段的分佈情況:
4.字首編碼在電文傳輸中,需要將電文中出現的每個字元進行二進位制編碼。在設計編碼時需要遵守兩個原則:(1)傳送方傳輸的二進位制編碼,到接收方解碼後必須具有唯一性,即解碼結果與傳送方傳送的電文完全一樣;(2)傳送的二進位制編碼儘可能地短。
下面我們介紹兩種編碼的方式。(1)等長編碼這種編碼方式的特點是每個字元的編碼長度相同(編碼長度就是每個編碼所含的二進位制位數)。假設字符集只含有4個字元a,b,c,d,用二進位制兩位表示的編碼分別為00,01,10,11。
若現在有一段電文為:abaccda,則應傳送二進位制序列:00010010101100,總長度為14位。
當接收方接收到這段電文後,將按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性,但編碼長度並不是最短的。(2)不等長編碼在傳送電文時,為了使其二進位制位數儘可能地少,可以將每個字元的編碼設計為不等長的,使用頻度較高的字元分配一個相對比較短的編碼,使用頻度較低的字元分配一個比較長的編碼。
例如,可以為a,b,c,d四個字元分別分配0,00,1,01,並可將上述電文用二進位制序列:000011010傳送,其長度只有9個二進位制位,但隨之帶來了一個問題,接收方接到這段電文後無法進行譯碼,因為無法斷定前面4個0是4個a,1個b、2個a,還是2個b,即譯碼不唯一,因此這種編碼方法不可使用。(1)利用字符集中每個字元的使用頻率作為權值構造一個哈夫曼樹;(2)從根結點開始,為到每個葉子結點路徑上的左分支賦予0,右分支賦予1,並從根到葉子方向形成該葉子結點的編碼。
假設有一個電文字符集中有8個字元,每個字元的使用頻率分別為,現以此為例設計哈夫曼編碼。哈夫曼編碼設計過程為:(1)為方便計算,將所有字元的頻度乘以100,使其轉換成整型數值集合,得到;(2)以此集合中的數值作為葉子結點的權值構造一棵哈夫曼樹,如圖5-27所示;(3)由此哈夫曼樹生成哈夫曼編碼,如圖5-28所示。
最後得出每個字元的編碼為:比如,傳送一段編碼:0000011011010010,接收方可以準確地通過譯碼得到:
667528。
二叉樹有結點，其中葉子結點有，該二叉樹的深度怎麼求？假設根結點在第一層
度為2的節點1 1 0個所以沒有度為2的節點共7層 二叉樹中 度為0的結點個數 度為2的結點個數 1 題目中葉子結點有1個，所以度為2的結點是0個 所以這7個結點是 每層一個 結點 一共7成 即深度為7 這就退化成一個連結串列了啊，一共7層，最後一層一個葉子節點。葉子節點就是度為0的結點，比度為2的...
設一棵完全二叉樹中有結點,則該完全二叉樹的深度為A,8 B,7 C,6 D
答案是 b,7 注 根結點的深度是1 分析過程如下 選項a,8 假設完全二叉樹的前7層都是滿二內叉樹,那麼容,這7層的結點數 2 7 1 127 65 注 2 7表示2的7次方 如果算上第8層的結點,總結點數會更多,不符合題目要求.選項b,7 假設完全二叉樹的前6層都是滿二叉樹,那麼,這6層的結點數...
設一棵完全二叉樹中有結點，則該二叉樹的深度為多少？若用二叉連結串列作為該完全二叉樹的儲存結構，則共
如圖完全二叉du樹 存在單分支zhi 對應的二叉連結串列求空dao指標域即求先孩子結點個數 版2再 1 此權處的1就是單分支結點的空指標域 深度為9的完全二叉樹前8層是滿二叉樹，共2 1 255個結點第9層有500 255 245個結點 245為奇數可知其父結點一定有單分支 其父結點個數為244 2...