子樹檢視原始碼討論檢視歷史
| 子樹 |
 |
樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關係組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。
樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在數據庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關係的問題都可用樹來描述。滿二叉樹，完全二叉樹，排序二叉樹。
基本信息
中文名； 二叉樹
概述； 樹是一種重要的非線性數據結構
簡介； 每個結點最多有兩個子樹的有序樹
辨析； 樹中結點的最大度數沒有限制
樹； 樹的定義 樹的表示
二叉樹； 基本形態 重要概念 性質
基本介紹
樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關係組織起來的結構，很象自然界中的樹那樣。
樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源程序如下的語法結構。
又如在數據庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關係的問題都可用樹來描述。滿二叉樹，完全二叉樹，排序二叉樹。
詳細介紹
在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。
二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹是由一個或多個結點組成的有限集合，其中：
⒈必有一個特定的稱為根(ROOT)的結點；
⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次。
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
樹的表示 樹的表示方法有許多，常用的方法是用括號：先將根結點放入一對圓括號中，然後把它的子樹由左至右的順序放入括號中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最後用閉括號括起來。如右圖可寫成如下形式：
(a( b(d,e), c( f(g(h,i) ), )))
相關介紹
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：
(1)空二叉樹——(a)；
(2)只有一個根結點的二叉樹——(b)；
(3)只有左子樹——(c)；
(4)只有右子樹——(d)；
(5)完全二叉樹——(e)
注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
重要概念
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
(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，則無右兒子。
(6)給定N個節點，能構成h(N)種不同的二叉樹。
h(N)為卡特蘭數的第N項。h(n)=C(n,2*n)/(n+1)。
（7）設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2
存儲結構 (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; 普通樹轉換成二叉樹
二叉樹很像一株倒懸着的樹，從樹根到大分枝、小分枝、直到葉子把數據聯繫起來，這種數據結構就叫做樹結構，簡稱樹。樹中每個分叉點稱為結點，起始結點稱為樹根，任意兩個結點間的連接關係稱為樹枝，結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的"雙親"，結點的後趨結點稱為該結點的"子女"或"孩子"，同一結點的"子女"之間互稱"兄弟"。
普通樹轉二叉樹，一般採用左「子女」右「兄弟」的方式來轉化。
完全二叉樹 對滿二叉樹，從第一層的結點(即根)開始，由下而上，由左及右，按順序結點編號，便得到滿二叉樹的一個順序表示。據此編號，完全二叉樹定義如下：一棵具有n個結點，深度為K的二叉樹，當且僅當所有結點對應於深度為K的滿二叉樹中編號由1至n的那些結點時，該二叉樹便是完全二叉樹。
二叉樹遍歷 遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。
設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。
(1)先序遍歷
訪問根；按先序遍歷左子樹；按先序遍歷右子樹，C語言代碼如下：
void XXBL(tree* root)
{
//Do Something with root
if (root->lchild!=NULL)
XXBL(root->lchild);
if (root->rchild!=NULL)
XXBL(root->rchild);
}
(2)中序遍歷
先訪問左（右）子樹，然後訪問根，最後訪問右（左）子樹的遍歷方式，C語言代碼如下
void ZXBL(tree* root)
{
if(root->lchild!=NULL)
ZXBL(root->lchild);
//Do Something with root
if(root->rchild!=NULL)
ZXBL(root->rchild);
}
(3)後序遍歷
按後序遍歷左子樹；按後序遍歷右子樹；訪問根 ，C語言代碼如下
void HXBL(tree* root)
{
if (root->lchild!=NULL)
HXBL(root->lchild);
if (root->rchild!=NULL)
HXBL(root->rchild);
//Do Something with root
}
（4）層次遍歷
即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子女的子女（越往後的層次越低）（兩個子女的級別相同）
特殊的二叉樹
1. 完全二叉樹
Complete Binary Tree
若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若干結點，這就是完全二叉樹。
2. 滿二叉樹
Full Binary Tree：
一個高度為h的二叉樹包含正是2^h-1元素稱為滿二叉樹。
線索二叉樹 線索二叉樹(保留遍歷時結點在任一序列的前驅和後繼的信息)：若結點有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令rchild指示其後繼。還需在結點結構中增加兩個標誌域LTag和RTag。LTag=0時，lchild域指示結點的左孩子，LTag=1時，lchild域指示結點的前驅；RTag=0時，rchild域指示結點的右孩子，RTag=1時，rchild域指示結點的後繼。以這種結點結構構成的二叉線索鍊表，鍊表作為二叉樹的存儲結構，叫做其中指向結點前驅和後繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鍊表稱為為中序線索鍊表。線索二叉樹是一種物理結構。
在中序線索樹找結點後繼的規律是：若其右標誌為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。
在後序線索樹中找到結點的後繼分三種情況：
若結點是二叉樹的根，則其後繼為空；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。
數據結構定義為：
/* 二叉線索存儲表示*/
typedefenum{Link,Thread}PointerTag;/* Link(0)：指針，Thread(1)：線索 */
typedefstruct BiThrNode
{ TElemType data;
struct BiThrNode *lchild,*rchild;/*左右孩子指針*/
PointerTag LTag,RTag;/* 左右標誌 */
}BiThrNode,*BiThrTree;
計算機科學中的樹 二叉樹 二叉樹 二叉查找樹 笛卡爾樹 Top tree T樹 自平衡二叉查找樹 AA樹 AVL樹 紅黑樹 伸展樹 樹堆 節點大小平衡樹 B樹 B樹 B+樹 B*樹 Bx樹 UB樹 2-3樹 2-3-4樹 (a,b)-樹 Dancing tree H樹 Trie 前綴樹 後綴樹 基數樹 空間劃分樹 四叉樹 八叉樹 k-d樹 vp-樹 R樹 R*樹 R+樹 X樹 M樹 線段樹 希爾伯特R樹 優先R樹 非二叉樹 Exponential tree Fusion tree 區間樹 PQ tree Range tree SPQR tree Van Emde Boas tree 其他類型 堆 散列樹 Finger tree Metric tree Cover tree BK-tree Doubly-chained tree iDistance Link-cut tree 樹狀數組[1]