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

什么是二叉樹？二叉樹拿來干什么？計(jì)算機(jī)c語言中 什么是二叉樹？什么是二叉樹？計(jì)算機(jī)中的樹是什么？什么是二叉樹？

本文導(dǎo)航

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

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

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

樹和二叉樹的2個主要差別：

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

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

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

樹的概述

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

樹的定義

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

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

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

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

1.樹的度——也即是寬度，簡單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結(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；

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

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

樹的表示

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

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

二叉樹

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

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

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

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

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

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

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

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

2.兩個重要的概念

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

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

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

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

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

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

則N0=N2+1；

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

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

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

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

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

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

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

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

(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.普通樹轉(zhuǎn)換成二叉樹

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

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

完全二叉樹

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

二叉樹遍歷

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

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

(1)前序遍歷

訪問根；按前序遍歷左子樹；按前序遍歷右子樹

(2)中序遍歷

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

(3)后序遍歷

按后序遍歷左子樹；按后序遍歷右子樹；訪問根

（4）層次遍歷

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

特殊的二叉樹

1. 完全二叉樹

Complete Binary Tree

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

2. 滿二叉樹

Full Binary Tree：

一個高度為h的二叉樹包含正是2-1元素稱為滿二叉樹。

c語言二叉樹入門教程

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

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

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

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

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

樹的遞歸定義如下：（1）至少有一個結(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)是每個結(jié)點(diǎn)至多只有二棵子 樹 (即二叉樹中不存在度大于 2的結(jié)點(diǎn) )，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒 . 二叉樹是一種數(shù)據(jù)結(jié)構(gòu) :

Binary_tree=(D,R)

其中： D是具有相同特性的數(shù)據(jù)元素的集合 ;若 D等于空 ,則 R等于空稱為空的二叉樹 ;若 D等于空則 R是 D上某個二元關(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)只有一個根結(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) 遍歷操作。按某個次序依此訪問二叉樹中各個結(jié)點(diǎn)，并使每個結(jié)點(diǎn)只被訪問一次。

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

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

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

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

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

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

5.3 遍歷二叉樹

遍歷二叉樹 (traversing binary tree)的問題， 即如何按某條搜索路徑巡訪樹中每個結(jié)點(diǎn)，使得每個結(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.用順序存儲方式建立一棵有31個結(jié)點(diǎn)的滿二叉樹，并對其進(jìn)行先序遍歷。

2.用鏈表存儲方式建立一棵如圖三、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

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

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

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

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

擴(kuò)展資料：

一、種類：

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

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

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

4、完全二叉樹，滿二叉樹。

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

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

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

2、樹與它的根結(jié)點(diǎn)用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。

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

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

二叉樹一般用來干什么

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

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

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

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

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