二叉樹,圖怎麼理解

時間 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實現一遍。

樓主好運!

什麼是二叉樹,舉二叉樹的例子,什麼是二叉樹,舉一個二叉樹的例子

二叉樹樹是一種重要的非線性資料結構,直觀地看,它是資料元素 在樹中稱為結點 按分支關係組織起來的結構,很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在,如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用,如在編譯源程式如下時,可用樹表示源源程式如下的語法結構。又如在資...

r語言如何二叉樹,如何構建二叉樹

define telemtype inttypedef struct bitnodebitnode,bitree 先序建立二叉樹 void createbitree bitree t t data c createbitree t lchild createbitree t rchild 先序遞迴建...

二叉樹,跪求答案

手機使用者 includestdlib.h 在二叉樹中,已知中序後序序列求先序序列 對於這個問題,和 在二叉樹中,已知前序中序序列求後序序列 求解思路差不多,只是要對後序序列從後向前依次讀取字元,插入到二叉樹中,再判斷插入當前節點與讀入的字元在中序序列中的先後關係,若讀入字元先,則插入當前節點左子樹...