計(jì)算機(jī)中的叉樹是什么 c語言普通二叉樹的存儲(chǔ)結(jié)構(gòu)

什么是四叉樹，數(shù)據(jù)結(jié)構(gòu)的。有圖例最好，謝謝？計(jì)算機(jī)中的樹是什么？什么是二叉樹？二叉樹拿來干什么？計(jì)算機(jī)c語言中 什么是二叉樹？二叉樹是什么？什么是二叉樹？

本文導(dǎo)航

• 四叉樹結(jié)構(gòu)例子
• 計(jì)算機(jī)森林是什么
• 二叉樹是干嘛用的
• c語言普通二叉樹的存儲(chǔ)結(jié)構(gòu)
• 什么叫完全二叉樹
• 二叉樹的五種表示方法

四叉樹結(jié)構(gòu)例子

四叉樹是一種數(shù)據(jù)結(jié)構(gòu)，是一種每個(gè)節(jié)點(diǎn)最多有四個(gè)子樹的數(shù)據(jù)結(jié)構(gòu)。

　　四叉樹可以用來在數(shù)據(jù)庫中放置和定位文件（稱作記錄或鍵）。這一算法通過不停的把要查找的記錄分成4部分來進(jìn)行匹配查找直到僅剩下一條記錄為止?！?/p>

　　在樹中，記錄被存儲(chǔ)在葉子的位置上。這一名字的由來是因?yàn)橛涗洷淮鎯?chǔ)在端點(diǎn)上，它們上面再?zèng)]有節(jié)點(diǎn)了。分支被稱作節(jié)點(diǎn)。數(shù)的順序是每節(jié)點(diǎn)的分支（也稱孩子）數(shù)。在四叉樹中，每個(gè)節(jié)點(diǎn)通常有4個(gè)孩子，因此順序是4。四叉樹的葉子數(shù)也是4。為達(dá)到想要的記錄所進(jìn)行的查找操作次數(shù)成為樹的深度。下圖給出了深度為3的四叉樹。

　　在實(shí)際的樹中，可能有成千、成萬或數(shù)十億條記錄。不是所有的葉子必須有一條記錄，但至少要有一半包含記錄。不包含記錄的葉子稱為空。在上面例子中，第8、第12、第16個(gè)葉子是空的，用空白圓來指示。　

　　四叉樹是在二維圖片中定位像素的唯一適合的算法。因?yàn)槎S空間（圖經(jīng)常被描述的方式）中，平面像素可以重復(fù)的被分為四部分，樹的深度由圖片、計(jì)算機(jī)內(nèi)存和圖形的復(fù)雜度決定。

計(jì)算機(jī)森林是什么

樓主你好，因技術(shù)有限，所以在網(wǎng)上找了一些相關(guān)的資料，希望可以幫助到你。樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。

在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。

在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

二*樹的特點(diǎn)：（1）非空二*樹只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。

二*樹的基本性質(zhì)：

（1）在二*樹的第k層上，最多有2k-1(k≥1)個(gè)結(jié)點(diǎn)；

（2）深度為m的二*樹最多有2m-1個(gè)結(jié)點(diǎn)；

（3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)；

（4）具有n個(gè)結(jié)點(diǎn)的二*樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分；

（5）具有n個(gè)結(jié)點(diǎn)的完全二*樹的深度為[log2n]+1；

（6）設(shè)完全二*樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，….n給結(jié)點(diǎn)進(jìn)行編號（k=1,2….n），有以下結(jié)論：

①若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號為INT(k/2)；

②若2k≤n，則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（也無右子結(jié)點(diǎn)）；

③若2k+1≤n，則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。

滿二*樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿二*樹有2m-1個(gè)結(jié)點(diǎn)。

完全二*樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

二*樹存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對于滿二*樹與完全二*樹可以按層序進(jìn)行順序存儲(chǔ)。

二*樹的遍歷：

（1）前序遍歷（DLR），首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；

（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；

（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。

相關(guān)請?jiān)L問 http://jinyichun1566.blog.163.com

二叉樹是干嘛用的

　　1、二叉樹在圖論中是這樣定義的：二叉樹是一個(gè)連通的無環(huán)圖，并且每一個(gè)頂點(diǎn)的度不大于3。有根二叉樹還要滿足根結(jié)點(diǎn)的度不大于2。有了根結(jié)點(diǎn)之后，每個(gè)頂點(diǎn)定義了唯一的父結(jié)點(diǎn)，和最多2個(gè)子結(jié)點(diǎn)。然而，沒有足夠的信息來區(qū)分左結(jié)點(diǎn)和右結(jié)點(diǎn)。如果不考慮連通性，允許圖中有多個(gè)連通分量，這樣的結(jié)構(gòu)叫做森林。

　　2、二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

　　二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。

　　一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)稱之為滿二叉樹；深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號為1至n的節(jié)點(diǎn)對應(yīng)時(shí)，稱之為完全二叉樹。

c語言普通二叉樹的存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。

二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^(k) -1個(gè)結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 + 1。樹是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合，其中：⒈必有一個(gè)特定的稱為根(ROOT)的結(jié)點(diǎn)；二叉樹⒉剩下的結(jié)點(diǎn)被分成n>=0個(gè)互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個(gè)又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。樹的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹1.樹的度——也即是寬度，簡單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。2.樹的深度——組成該樹各結(jié)點(diǎn)的最大層次。3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；4.有序樹——指樹中同層結(jié)點(diǎn)從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。

什么叫完全二叉樹

二叉樹 (binary tree) 是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子 樹 (即二叉樹中不存在度大于 2的結(jié)點(diǎn) )，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒 . 二叉樹是一種數(shù)據(jù)結(jié)構(gòu) :

Binary_tree=(D,R)

其中： D是具有相同特性的數(shù)據(jù)元素的集合 ;若 D等于空 ,則 R等于空稱為空的二叉樹 ;若 D等于空則 R是 D上某個(gè)二元關(guān)系 H的集合，即 R={H}，且

(1) D 中存在唯一的稱為根的元素 r，它的關(guān)系 H下無前驅(qū) ;

(2) 若 D-{r}不等于空，則 D-{r}={Dl,Dr}，且 Dl交 Dr等于空 ;

(3) 若 Dl不等于空 ,則在 Dl中存在唯一的元素 xl,〈 r,xl〉屬于 H，且存在 Dl上的關(guān)系 Hl屬于 H； 若 Dr不等于空 ,則在 Dr中存在唯一的元素 xr,〈 r,xr〉 >屬于 H, 且存 Dr上的關(guān) 系 Hr屬于 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};

(4) (Dl, Hl) 是一棵合本定義的二叉樹，稱為根 r的左子樹 ,(Dr,Hr)是一棵符合定義的二叉樹，稱為根的右子樹。

其中，圖 6.2 是各種形態(tài)的二叉樹 .

(1) 為空二叉樹 (2)只有一個(gè)根結(jié)點(diǎn)的二叉樹 (3)右子樹為空的二叉樹 (4)左子樹為空的二叉樹 (5)完全二叉樹

二叉樹的基本操作：

(1)INITIATE(BT ） 初始化操作。置 BT為空樹。

(2)ROOT(BT)\ROOT(x) 求根函數(shù)。求二叉樹 BT的根結(jié)點(diǎn)或求結(jié)點(diǎn) x所在二叉樹的根結(jié)點(diǎn)。

若 BT是空樹或 x不在任何二叉樹上，則函數(shù)值為 “空 ”。

(3)PARENT(BT,x) 求雙親函數(shù)。求二叉樹 BT中結(jié)點(diǎn) x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn) x是二叉樹 BT 的根結(jié)點(diǎn)

或二叉樹 BT中無 x結(jié)點(diǎn)，則函數(shù)值為 “空 ”。

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子結(jié)點(diǎn)函數(shù)。分別求二叉樹 BT中結(jié)點(diǎn) x的左孩 子和右孩子結(jié)點(diǎn)。

若結(jié)點(diǎn) x為葉子結(jié)點(diǎn)或不在二叉樹 BT中，則函數(shù)值為 “空 ”。

(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函數(shù)。分別求二叉樹 BT中結(jié)點(diǎn) x的左兄弟和右兄弟結(jié)點(diǎn)。

若結(jié)點(diǎn) x是根結(jié)點(diǎn)或不在 BT中或是其雙親的左 /右子樹根 ,則函樹值 為 “空 ”。

(6)CRT_BT(x,LBT,RBT) 建樹操作。生成一棵以結(jié)點(diǎn) x為根，二叉樹 LBT和 RBT分別為左， 右子樹的二叉樹。

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子樹操作。將以結(jié)點(diǎn) x為根且右子樹為空的二叉樹

分別置為二叉樹 BT中結(jié)點(diǎn) y的左子樹和右子樹。若結(jié)點(diǎn) y有左子樹 /右子樹，則插入后是結(jié)點(diǎn) x的右子樹。

(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 刪除子樹操作。分別刪除二叉樹 BT中以結(jié)點(diǎn) x為根的左子樹或右子樹。

若 x無左子樹或右子樹，則空操作。

(9)TRAVERSE(BT) 遍歷操作。按某個(gè)次序依此訪問二叉樹中各個(gè)結(jié)點(diǎn)，并使每個(gè)結(jié)點(diǎn)只被訪問一次。

(10)CLEAR(BT) 清除結(jié)構(gòu)操作。將二叉樹 BT置為空樹。

5.2.2 二叉樹的存儲(chǔ)結(jié)構(gòu)

一 、順序存儲(chǔ)結(jié)構(gòu)

連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。例如圖 6.4(b)的完全二叉樹 , 可以向量 (一維數(shù)組 ) bt(1:6)作它的存儲(chǔ)結(jié)構(gòu)，將二叉樹中編號為 i的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量 bt[i]中 ,如圖 6.6(a) 所示。但這種順序存儲(chǔ)結(jié)構(gòu)僅適合于完全二叉樹 ,而一般二叉樹也按這種形式來存儲(chǔ) ,這將造成存 貯浪費(fèi)。如和圖 6.4(c)的二叉樹相應(yīng)的存儲(chǔ)結(jié)構(gòu)圖 6.6(b)所示，圖中以 “0”表示不存在此結(jié)點(diǎn) .

二、 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

由二叉樹的定義得知二叉樹的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向左右子樹的兩個(gè)分支構(gòu)成 ,則表 示二叉樹的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域 :數(shù)據(jù)域和左右指針域 ,如圖 (b)所示。有時(shí) ,為了便于找 到結(jié)點(diǎn)的雙親 ,則還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親受的指針域，如圖 6.7(c)所示。

5.3 遍歷二叉樹

遍歷二叉樹 (traversing binary tree)的問題， 即如何按某條搜索路徑巡訪樹中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。 其中常見的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和后 (根 )序遍歷。

5.3.1 前序遍歷

前序遍歷運(yùn)算：即先訪問根結(jié)點(diǎn)，再前序遍歷左子樹，最后再前序遍歷右子樹。前序遍歷運(yùn)算訪問二叉樹各結(jié)點(diǎn)是以根、左、右的順序進(jìn)行訪問的。例如：

按前序遍歷此二叉樹的結(jié)果為： Hello!How are you?

proc preorder(bt:bitreprtr)

if (bt>null)[

print(bt^);

preorder(bt^.lchild);

preorder(bt^.rchild);]

end;

5.3.2 中序遍歷

中序遍歷運(yùn)算：即先中前序遍歷左子樹，然后再訪問根結(jié)點(diǎn)，最后再中序遍歷右子樹。中序遍歷運(yùn)算訪問二叉樹各結(jié)點(diǎn)是以左、根、右的順序進(jìn)行訪問的。例如：

按中序遍歷此二叉樹的結(jié)果為： a*b-c

proc inorder(bt:bitreprtr)

if (bt>null)[

inorder(bt^.lchild);

print(bt^);

niorder(bt^.rchild);]

end;

5.3.3 后序遍歷

后序遍歷運(yùn)算：即先后序遍歷左子樹，然后再后序遍歷右子樹，最后訪問根結(jié)點(diǎn)。后序遍歷運(yùn)算訪問二叉樹各結(jié)點(diǎn)是以左、右、根的順序進(jìn)行訪問的。例如：

按后序遍歷此二叉樹的結(jié)果為： Welecome to use it!

proc postorder(bt:bitreprtr)

if (bt>null)[

postorder(bt^.lchild);

postorder(bt^.rchild);]

print(bt^);

end;

五、例：

1.用順序存儲(chǔ)方式建立一棵有31個(gè)結(jié)點(diǎn)的滿二叉樹，并對其進(jìn)行先序遍歷。

2.用鏈表存儲(chǔ)方式建立一棵如圖三、4所示的二叉樹，并對其進(jìn)行先序遍歷。

3.給出一組數(shù)據(jù)：R={10.18,3,8,12,2,7,3}，試編程序，先構(gòu)造一棵二叉樹，然后以中序遍歷訪問所得到的二叉樹，并輸出遍歷結(jié)果。

4.給出八枚金幣a,b,c,d,e,f,g,h，編程以稱最少的次數(shù)，判定它們蹭是否有假幣，如果有，請找出這枚假幣，并判定這枚假幣是重了還是輕了。

中山紀(jì)念中學(xué)三鑫雙語學(xué)校信息學(xué)競賽組編寫 2004.7.15

二叉樹的五種表示方法