二叉樹,圖怎麼理解

時間 2021-06-13 06:39:23

1樓:匿名使用者

1.二叉樹的基本形態:

二叉樹也是遞迴定義的,其結點有左右子樹之分,邏輯上二叉樹有五種基本形態:

(1)空二叉樹——(a);

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意:儘管二叉樹與樹有許多相似之處,但二叉樹不是樹的特殊情形。

2.兩個重要的概念:

(1)完全二叉樹——只有最下面的兩層結點度小於2,並且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹;

(2)滿二叉樹——除了葉結點外每一個結點都有左右子女且葉結點都處在最底層的二叉樹,。

3.二叉樹的性質

(1) 在二叉樹中,第i層的結點總數不超過2^(i-1);

(2) 深度為h的二叉樹最多有2^h-1個結點(h>=1),最少有h個結點;

(3) 對於任意一棵二叉樹,如果其葉結點數為n0,而度數為2的結點總數為n2,

則n0=n2+1;

(4) 具有n個結點的完全二叉樹的深度為int(log2n)+1

(5)有n個結點的完全二叉樹各結點如果用順序方式儲存,則結點之間有如下關係:

若i為結點編號則 如果i<>1,則其父結點的編號為i/2;

如果2*i<=n,則其左兒子(即左子樹的根結點)的編號為2*i;若2*i>n,則無左兒子;

如果2*i+1<=n,則其右兒子的結點編號為2*i+1;若2*i+1>n,則無右兒子。

4.二叉樹的儲存結構:

(1)順序儲存方式

type node=record

data:datatype

l,r:integer;

end;

var tr:array[1..n] of node;

(2)連結串列儲存方式,如:

type btree=^node;

node=record

data:datatye;

lchild,rchild:btree;

end;

5.普通樹轉換成二叉樹:凡是兄弟就用線連起來,然後去掉父親到兒子的連線,只留下父母到其第一個子女的連線。

二叉樹很象一株倒懸著的樹,從樹根到大分枝、小分枝、直到葉子把資料聯絡起來,這種資料結構就叫做樹結構,簡稱樹。樹中每個分叉點稱為結點,起始結點稱為樹根,任意兩個結點間的連線關係稱為樹枝,結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的"雙親",結點的後趨結點稱為該結點的"子女"或"孩子",同一結點的"子女"之間互稱"兄弟"。

二叉樹:二叉樹是一種十分重要的樹型結構。它的特點是,樹中的每個結點最多隻有兩棵子樹,即樹中任何結點的度數不得大於2。

二叉樹的子樹有左右之分,而且,子樹的左右次序是重要的,即使在只有一棵子樹的情況下,也應分清是左子樹還是右子樹。定義:二叉樹是結點的有限集合,這個集合或是空的,或是由一個根結點和兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。

(三)完全二叉樹

對滿二叉樹,從第一層的結點(即根)開始,由下而上,由左及右,按順序結點編號,便得到滿二叉樹的一個順序表示。據此編號,完全二叉樹定義如下:一棵具有n個結點,深度為k的二叉樹,當且僅當所有結點對應於深度為k的滿二叉樹中編號由1至n的那些結點時,該二叉樹便是完全二叉樹。

圖4是一棵完全二叉樹。

三、二叉樹的遍歷

遍歷是對樹的一種最基本的運算,所謂遍歷二叉樹,就是按一定的規則和順序走遍二叉樹的所有結點,使每一個結點都被訪問一次,而且只被訪問一次。由於二叉樹是非線性結構,因此,樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

設l、d、r分別表示遍歷左子樹、訪問根結點和遍歷右子樹, 則對一棵二叉樹的遍歷有三種情況:dlr(稱為先根次序遍歷),ldr(稱為中根次序遍歷),lrd (稱為後根次序遍歷)。

(1)先序遍歷

訪問根;按先序遍歷左子樹;按先序遍歷右子樹

(2)中序遍歷

按中序遍歷左子樹;訪問根;按中序遍歷右子樹

(3)後序遍歷

按後序遍歷左子樹;按後序遍歷右子樹;訪問根

2樓:匿名使用者

最多兩個孩子,分左右,

資料結構中,圖與樹,二叉樹比線性表有什麼優點?

3樓:涼念若櫻花妖嬈

二叉樹二叉樹能夠說是人們假想的一個模型,因此,允許有空的二叉樹是無爭議的。二叉樹是有序的,左邊有一個孩子和右邊有一個的二叉樹是不同的兩棵樹。做這個規定,是因為人們賦予了左孩子和右孩子不同的意義,在二叉樹的各種應用中,會清楚的看到。

看各種講資料結構的書,會發現一個有趣的現象:在二叉樹這裡,基本操作有計算樹高、各種遍歷,就是沒有插入、刪除——樹是怎麼建立起來的,其實這很好理解,對於非線性的樹結構,插入刪除操作不在一定的法則規定下,是毫無意義的。因此,只有在具體的應用中,才會有插入刪除操作。

節點結構,資料域、左指標、右指標肯定是必須的。除非很少用到節點的雙親,或是資源緊張,建議附加一個雙親指標,這將會給很多演算法帶來方便,尤其是在這個“空間換時間”的時代。

4樓:匿名使用者

你好,圖:非線性結構 點與點是多對多的關係 之間是平等的 沒有父節點 兄弟 孩子之分

樹:非線性結構 點與點是一對多的關係 有父節點 孩子節點 兄弟節點 (注意*樹不能為空**** 所以二叉樹不是樹)

儲存: 雙親表示法 孩子表示法 孩子兄弟表示法)二叉樹:有左右方向之分 可以為空 ,二叉樹可以順序儲存(主要用於完全二叉是樹的儲存)也可用二叉連結串列 三叉連結串列 索引表

線性表:線性結構

可以順序表示 也可以用連結串列表示

希望能夠幫到你,望採納

二叉樹和樹的區別到底是什麼,例如用三個結點畫出二叉樹和樹的不同結構圖,謝謝!!!

5樓:匿名使用者

二叉樹是指一個樹的父節點最多隻有兩個子節點構成的樹,樹是不限制子節點的個數的。

二叉樹是樹的一種特例,是樹的子集。

三個節點是無法表示出二叉樹和樹的區別的,需要三個以上的節點。

二叉樹的表示如下圖。

樹的表示如下圖。

樹狀圖是一種資料結構,它是由n(n>=1)個有限結點組成一個具有層次關係的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:

每個結點有零個或多個子結點;沒有父結點的結點稱為根結點;每一個非根結點有且只有一個父結點;除了根結點外,每個子結點可以分為多個不相交的子樹。

相關術語

節點的度:一個節點含有的子樹的個數稱為該節點的度;

葉節點或終端節點:度為0的節點稱為葉節點;

非終端節點或分支節點:度不為0的節點;

雙親節點或父節點:若一個節點含有子節點,則這個節點稱為其子節點的父節點;

孩子節點或子節點:一個節點含有的子樹的根節點稱為該節點的子節點;

兄弟節點:具有相同父節點的節點互稱為兄弟節點;

樹的度:一棵樹中,最大的節點的度稱為樹的度;

節點的層次:從根開始定義起,根為第1層,根的子節點為第2層,以此類推;

樹的高度或深度:樹中節點的最大層次;

堂兄弟節點:雙親在同一層的節點互為堂兄弟;

節點的祖先:從根到該節點所經分支上的所有節點;

子孫:以某節點為根的子樹中任一節點都稱為該節點的子孫。

森林:由m(m>=0)棵互不相交的樹的集合稱為森林;

6樓:匿名使用者

1、樹是一種分值結構的總稱。看看我們生活中 有的樹分值很多 如榕樹,梧桐樹。很奇怪的是這些樹的一個分支還是一棵樹。

而有的數分支很少 如水杉,白楊。 但是樹有共同的特點【分支及層次關係】

2、二叉樹是一種特殊的樹形結構,每個節點之多又2個分支。既然二叉,所以有左右子樹的區別。

3、二叉樹的結構3個節點:

a/ \

b ca/

b/ca

\b\c

a/b\

ca\b

/c而數沒有左右之分。所以只有2中形態

a/ \

b ca|

b|c注意這裡是求樹的形狀(形態,而不是樹中節點的排列組合)嚴蔚敏:資料結構那本書一定要吃透,個人建議看5遍以上。基本演算法都要用c實現一遍。

樓主好運!

二叉樹遍歷,二叉樹遍歷問題?

這個說起來 很煩 不過可以 用遞迴的思想做。因為根為1左4 2 右5 7 3 6 遞迴的思想。再在左子樹的前序中 2 為根 當然 4 就是葉子 再看中序 在右邊。右3 為根 所以子樹的左子樹 還有5 7 右 為6在遞迴。不打了 根結點為1,則左為42,右5736,再看先根序列24 3576 左邊42...

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

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

二叉樹後續線索樹的問題,後序後繼線索二叉樹中找後繼的集中情況

後序遍歷 若二叉樹非空,則依次執行如下操作 遍歷左子樹 遍歷右子樹 訪問根結點。所以從根結點開始 樹的判斷都是從根開始 如這裡的a,這裡有左右子樹b c,但是在訪問b的時候,發現b有左子樹d,所以d比b先,d有左子樹e e有右子樹f,所以f比e先,e比d先,訪問完b後,訪問c,c有右子樹g,先訪問g...