計(jì)算機(jī)中的叉樹(shù)是什么意思 二叉樹(shù)一般用來(lái)干什么

什么是二叉樹(shù)？二叉樹(shù)拿來(lái)干什么？計(jì)算機(jī)c語(yǔ)言中 什么是二叉樹(shù)？什么是二叉樹(shù)？計(jì)算機(jī)中的樹(shù)是什么？什么是二叉樹(shù)？

本文導(dǎo)航

• 二叉樹(shù)詳細(xì)講解圖解
• c語(yǔ)言二叉樹(shù)入門教程
• 二叉樹(shù)使用在什么地方
• 計(jì)算機(jī)的算法是指
• 二叉樹(shù)一般用來(lái)干什么

二叉樹(shù)詳細(xì)講解圖解

在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的有序樹(shù)。通常子樹(shù)的根被稱作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）。二叉樹(shù)常被用作二叉查找樹(shù)和二叉堆。二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)(不存在度大于2的結(jié)點(diǎn))，二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒。二叉樹(shù)的第i層至多有2的（i-1）次方個(gè)結(jié)點(diǎn)；深度為k的二叉樹(shù)至多有2^(k) -1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 + 1。

樹(shù)和二叉樹(shù)的2個(gè)主要差別：

1. 樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，而二叉樹(shù)結(jié)點(diǎn)的最大度數(shù)為2；

2. 樹(shù)的結(jié)點(diǎn)無(wú)左、右之分，而二叉樹(shù)的結(jié)點(diǎn)有左、右之分?！?/p>

樹(shù)是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹(shù)中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來(lái)的結(jié)構(gòu)，很象自然界中的樹(shù)那樣。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹(shù)形象表示。樹(shù)在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序時(shí)，可用樹(shù)表示源程序的語(yǔ)法結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)也是信息的重要組織形式之一。一切具有層次關(guān)系的問(wèn)題都可用樹(shù)來(lái)描述。

樹(shù)的概述

樹(shù)結(jié)構(gòu)的特點(diǎn)是：它的每一個(gè)結(jié)點(diǎn)都可以有不止一個(gè)直接后繼，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨。以下具體地給出樹(shù)的定義及樹(shù)的數(shù)據(jù)結(jié)構(gòu)表示。

樹(shù)的定義

樹(shù)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合，其中：

⒈必有一個(gè)特定的稱為根(ROOT)的結(jié)點(diǎn)；

⒉剩下的結(jié)點(diǎn)被分成n>=0個(gè)互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個(gè)又都是樹(shù)。樹(shù)T1、T2、......Tn被稱作根的子樹(shù)(Subtree)。

樹(shù)的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹(shù)

1.樹(shù)的度——也即是寬度，簡(jiǎn)單地說(shuō)，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹(shù)各結(jié)點(diǎn)中最大的度作為該樹(shù)的度，如上圖的樹(shù)，其度為3;樹(shù)中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹(shù)中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

2.樹(shù)的深度——組成該樹(shù)各結(jié)點(diǎn)的最大層次，如上圖，其深度為3；

3.森林——指若干棵互不相交的樹(shù)的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來(lái)的二棵子樹(shù)T1、T2、T3的集合{T1,T2,T3}就為森林；

4.有序樹(shù)——指樹(shù)中同層結(jié)點(diǎn)從左到右有次序排列，它們之間的次序不能互換，這樣的樹(shù)稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。

樹(shù)的表示

樹(shù)的表示方法有許多，常用的方法是用括號(hào)：先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)由左至右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣的方法處理；同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)隔開(kāi)，最后用閉括號(hào)括起來(lái)。如上圖可寫成如下形式：

(A(B(E(K,L),F),C(G),D(H(M),I,J)))

二叉樹(shù)

1.二叉樹(shù)的基本形態(tài)

二叉樹(shù)也是遞歸定義的，其結(jié)點(diǎn)有左右子樹(shù)之分，邏輯上二叉樹(shù)有五種基本形態(tài)：

(1)空二叉樹(shù)——(a)；

(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)——(b)；

(3)只有左子樹(shù)——(c)；

(4)只有右子樹(shù)——(d)；

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

注意：盡管二叉樹(shù)與樹(shù)有許多相似之處，但二叉樹(shù)不是樹(shù)的特殊情形。

2.兩個(gè)重要的概念

(1)完全二叉樹(shù)——若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。

(2)滿二叉樹(shù)——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉結(jié)點(diǎn)都處在最底層的二叉樹(shù),。

3.二叉樹(shù)的性質(zhì)

(1) 在二叉樹(shù)中，第i層的結(jié)點(diǎn)總數(shù)不超過(guò)2^(i-1)；

(2) 深度為h的二叉樹(shù)最多有2^(h)-1個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；

(3) 對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，

則N0=N2+1；

(4) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int（log2n）+1

(5)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：

若I為結(jié)點(diǎn)編號(hào)則 如果I<>1，則其父結(jié)點(diǎn)的編號(hào)為I/2；

如果2*I<=N，則其左兒子（即左子樹(shù)的根結(jié)點(diǎn)）的編號(hào)為2*I；若2*I>N，則無(wú)左兒子；

如果2*I+1<=N，則其右兒子的結(jié)點(diǎn)編號(hào)為2*I+1；若2*I+1>N，則無(wú)右兒子。

(6)給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹(shù)。

h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(n,2*n)/(n+1)。

4.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

(1）順序存儲(chǔ)方式

type node=record

data:datatype

l,r:integer;

end;

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

(2)鏈表存儲(chǔ)方式，如：

type btree=^node；

node=record

data:datatye;

lchild,rchild:btree;

end;

5.普通樹(shù)轉(zhuǎn)換成二叉樹(shù)

二叉樹(shù)很象一株倒懸著的樹(shù)，從樹(shù)根到大分枝、小分枝、直到葉子把數(shù)據(jù)聯(lián)系起來(lái)，這種數(shù)據(jù)結(jié)構(gòu)就叫做樹(shù)結(jié)構(gòu)，簡(jiǎn)稱樹(shù)。樹(shù)中每個(gè)分叉點(diǎn)稱為結(jié)點(diǎn)，起始結(jié)點(diǎn)稱為樹(shù)根，任意兩個(gè)結(jié)點(diǎn)間的連接關(guān)系稱為樹(shù)枝，結(jié)點(diǎn)下面不再有分枝稱為樹(shù)葉。結(jié)點(diǎn)的前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的"雙親"，結(jié)點(diǎn)的后趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的"子女"或"孩子"，同一結(jié)點(diǎn)的"子女"之間互稱"兄弟"。

普通樹(shù)轉(zhuǎn)二叉樹(shù)，一般采用左“子女”右“兄弟”的方式來(lái)轉(zhuǎn)化。

完全二叉樹(shù)

對(duì)滿二叉樹(shù)，從第一層的結(jié)點(diǎn)(即根)開(kāi)始，由下而上，由左及右，按順序結(jié)點(diǎn)編號(hào)，便得到滿二叉樹(shù)的一個(gè)順序表示。據(jù)此編號(hào)，完全二叉樹(shù)定義如下：一棵具有n個(gè)結(jié)點(diǎn)，深度為K的二叉樹(shù)，當(dāng)且僅當(dāng)所有結(jié)點(diǎn)對(duì)應(yīng)于深度為K的滿二叉樹(shù)中編號(hào)由1至n的那些結(jié)點(diǎn)時(shí)，該二叉樹(shù)便是完全二叉樹(shù)。圖4是一棵完全二叉樹(shù)。

二叉樹(shù)遍歷

遍歷是對(duì)樹(shù)的一種最基本的運(yùn)算，所謂遍歷二叉樹(shù)，就是按一定的規(guī)則和順序走遍二叉樹(shù)的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次。由于二叉樹(shù)是非線性結(jié)構(gòu)，因此，樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來(lái)表示。

設(shè)L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)和遍歷右子樹(shù)， 則對(duì)一棵二叉樹(shù)的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為后根次序遍歷）。

(1)前序遍歷

訪問(wèn)根；按前序遍歷左子樹(shù)；按前序遍歷右子樹(shù)

(2)中序遍歷

按中序遍歷左子樹(shù)；訪問(wèn)根；按中序遍歷右子樹(shù)

(3)后序遍歷

按后序遍歷左子樹(shù)；按后序遍歷右子樹(shù)；訪問(wèn)根

（4）層次遍歷

即按照層次訪問(wèn)，通常用隊(duì)列來(lái)做。訪問(wèn)根，訪問(wèn)子女，再訪問(wèn)子女的子女（越往后的層次越低）（兩個(gè)子女的級(jí)別相同）

特殊的二叉樹(shù)

1. 完全二叉樹(shù)

Complete Binary Tree

若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。

2. 滿二叉樹(shù)

Full Binary Tree：

一個(gè)高度為h的二叉樹(shù)包含正是2-1元素稱為滿二叉樹(shù)。

c語(yǔ)言二叉樹(shù)入門教程

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

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

樹(shù)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合，其中：

⒈必有一個(gè)特定的稱為根(ROOT)的結(jié)點(diǎn)；二叉樹(shù)

⒉剩下的結(jié)點(diǎn)被分成n>=0個(gè)互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個(gè)又都是樹(shù)。樹(shù)T1、T2、......Tn被稱作根的子樹(shù)(Subtree)。

樹(shù)的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹(shù)

1.樹(shù)的度——也即是寬度，簡(jiǎn)單地說(shuō)，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹(shù)各結(jié)點(diǎn)中最大的度作為該樹(shù)的度，如上圖的樹(shù)，其度為2;樹(shù)中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹(shù)中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

2.樹(shù)的深度——組成該樹(shù)各結(jié)點(diǎn)的最大層次。

3.森林——指若干棵互不相交的樹(shù)的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來(lái)的二棵子樹(shù)T1、T2、T3的集合{T1,T2,T3}就為森林；

4.有序樹(shù)——指樹(shù)中同層結(jié)點(diǎn)從左到右有次序排列，它們之間的次序不能互換，這樣的樹(shù)稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。

二叉樹(shù)使用在什么地方

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

Binary_tree=(D,R)

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

(1) D 中存在唯一的稱為根的元素 r，它的關(guān)系 H下無(wú)前驅(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) 是一棵合本定義的二叉樹(shù)，稱為根 r的左子樹(shù) ,(Dr,Hr)是一棵符合定義的二叉樹(shù)，稱為根的右子樹(shù)。

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

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

二叉樹(shù)的基本操作：

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

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

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

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

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

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

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

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

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

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

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

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

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

若 x無(wú)左子樹(shù)或右子樹(shù)，則空操作。

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

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

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

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

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

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

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

5.3 遍歷二叉樹(shù)

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

5.3.1 前序遍歷

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

按前序遍歷此二叉樹(shù)的結(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)算：即先中前序遍歷左子樹(shù)，然后再訪問(wèn)根結(jié)點(diǎn)，最后再中序遍歷右子樹(shù)。中序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、根、右的順序進(jìn)行訪問(wèn)的。例如：

按中序遍歷此二叉樹(shù)的結(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)算：即先后序遍歷左子樹(shù)，然后再后序遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。后序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、右、根的順序進(jìn)行訪問(wèn)的。例如：

按后序遍歷此二叉樹(shù)的結(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)的滿二叉樹(shù)，并對(duì)其進(jìn)行先序遍歷。

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

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

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

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

計(jì)算機(jī)的算法是指

樹(shù)：數(shù)據(jù)結(jié)構(gòu)名詞。

1、樹(shù)狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。

2、它具有以下的特點(diǎn)，每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；每一個(gè)非根結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)。

擴(kuò)展資料：

一、種類：

1、無(wú)序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒(méi)有順序關(guān)系，這種樹(shù)稱為無(wú)序樹(shù),也稱為自由樹(shù)。

2、有序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹(shù)稱為有序樹(shù)。

3、二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱為二叉樹(shù)。

4、完全二叉樹(shù)，滿二叉樹(shù)。

5、霍夫曼樹(shù)：帶權(quán)路徑最短的二叉樹(shù)稱為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。

二、符號(hào)表達(dá)法：

1、號(hào)先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)由左至右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣的方法處理。

2、樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)隔開(kāi)，最后用閉括號(hào)括起來(lái)。

3、文樹(shù)形表示法可以表示為：（1（2（5（9，10）），3（6，7），4（8）））。

參考資料：百度百科-樹(shù)（數(shù)據(jù)結(jié)構(gòu)名詞）

二叉樹(shù)一般用來(lái)干什么

二叉樹(shù)（Binary tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型。是指樹(shù)中節(jié)點(diǎn)的度不大于2的有序樹(shù)，它是一種最簡(jiǎn)單且最重要的樹(shù)。

二叉樹(shù)的遞歸定義為：二叉樹(shù)是一棵空樹(shù)，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù)；左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)。

1. 許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。

2. 二叉樹(shù)特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分。

3. 二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根（root）的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。當(dāng)集合為空時(shí)，稱該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。