二叉樹的儲存結構是怎樣的?有哪些型別的儲存結構?對應的c語言描述是

時間 2021-09-15 00:08:58

1樓:匿名使用者

樓上回答的是樹的儲存,不是二叉樹的儲存,主要如下:

1、順序儲存:適用於完全二叉樹,如果根從1開始編號,則第i結點的左孩子編號為2i,右孩子為2i+1,雙親編號為(i/2)下取整,空間緊密

2、二叉連結串列:適用於普通二叉樹,每個結點除了資料外,還有分別指向左右孩子結點的指標,儲存n個結點有n+1個空指標域,儲存密度小於順序儲存,但是適用範圍廣,缺陷是正常遍歷只能從雙親向孩子,退回來一般需要藉助棧(或者用遞迴,其實也是棧)

3、三叉連結串列:同樣適用於普通二叉樹,結點除了資料外,還有左右孩子與雙親的指標,儲存密度低於二叉連結串列,但是可以非常方便地在二叉樹中遍歷,不需要其他輔助工具

2樓:來自度假村有個性的無尾熊

1。對於完全二叉樹就用陣列表示法,結點i的左孩子為2*i,右孩子為2*i+1,雙親為i/2

2。雙親陣列表示法。這個我沒用過,大概是對每個結點記錄其雙親,但是結點不一定是連續的,比如:

結點 雙親

1 0

4 1

3 4

5 2

2 1

嘛,這個只是從底向上的遍歷比較簡單,所以一般不用

3。孩子連結串列表示法

對於每個結點給予兩個指標域分別指向其左孩子,右孩子,若指標域為空則表示沒有這邊的孩子。

詳細的實現比較長懶的寫了,隨便找點資料好了。

基礎的就這三種,一般用到的也是這樣,其他也就是沒有大改動只是加入一些域什麼的而已。。。

以上純手打

3樓:裡邊生

看些資料結構就好啦!連結串列,佇列,棧,樹,圖什麼的吧!都可以用c語言,c++也可以喲

c語言中.二叉樹的順序儲存結構和二叉連結串列,三叉連結串列儲存結構各自的優缺點及適用場合.以及2叉樹的順序儲存結

4樓:匿名使用者

鏈式結構優點bai都是便

du於定址,二叉連結串列缺點zhi結構性開銷隨著數dao據結構的回規模變大而答變大(尤其是葉子節點都有2個null,即損失2*sizeof(elemtype*))

線性結構優點沒有結構性開銷,缺點個人感覺是插入和刪除不夠方便?

試用場合估計取決問題規模大小,即空間複雜度和時間複雜度

兩個相互轉化很簡單,只需明白的就是順序儲存中:

當前節點的父節點parent(currentpos) = (currentpos - 1) / 2 取下界

左孩子left(currentpos) = 2*currentpos + 1

右孩子right(currentpos) = 2*currentpos + 2

左兄弟 = currentpos - 1

右兄弟 = currentpos + 1

轉換時只需講鏈式儲存結構的資料域的資料拷貝到順序儲存結構對應的位置即可

二叉樹是什麼,什麼是二叉樹?

在電腦科學中,二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作 左子樹 left subtree 和 右子樹 right subtree 二叉樹常被用於實現二叉查詢樹和二叉堆。二叉樹的每個結點至多隻有二棵子樹 不存在度大於2的結點 二叉樹的子樹有左右之分,次序不能顛倒。二叉樹的第i層至多有2 ...

什麼是二叉樹的順序儲存,為什麼說二叉樹是非線性儲存結構?不是說二叉樹可以順序儲存和鏈式儲存嗎?感覺順序儲存是線性的呀?怎麼

二叉樹的順序儲存是將二叉樹的所有結點,按照一定的次序,儲存到一片連續的儲存單元中 二叉樹的順序儲存必須將結點排成一個適當的線性序列,使得結點在這個序列中的相應位置能反映出結點之間的邏輯關係。這種結構特別適用於近似滿二叉樹。在一棵具有n個結點的近似滿二叉樹中,當從樹根起,自上層到下層,逐層從左到右給所...

構造平衡二叉樹,平衡二叉樹是二叉排序樹嗎?

從結點48向根回溯,依次計算各個結點的平衡因子,48的為0,37為 1 左減去右 53為 1,24為 2,產生不平衡,從24往來路看2個結點 路徑形態為先向右走再向左走,於是 和37進行先右後左雙旋 第一步 將 向右旋轉,37上,53變為37的右子樹,48交給53成為53的左子樹。第二步 將 向左旋...