是資料結構中，用來描述“樹”型結構的名詞。這種結構像一根倒著的樹。每片樹葉都長在一個結點上，這個結點就叫做這個葉子的父結點，這個葉子叫做你結點的子結點，也叫這棵樹的葉結點，它再沒有子結點了。而葉子的父結點一定還會有上面的父結點，這樣一級一級上去就到了根結點，它就像是樹的根，它上面再沒有“叉兒”了樹的相關術語一個結點的兒子結點的個數稱為該結點的度。一棵樹的度是指該樹中結點的最大度數。 樹中度為零的結點稱為葉結點或終端結點。 樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。例如在圖1中，結點A，B和E的度分別為3，2，0。其中A為根結點,B為內部結點，E為葉結點，樹的度為3。 如果存在樹中的一個結點序列K1,K2,..,Kj，使得結點Ki是結點Ki+1的父結點(1≤i≤j)，則稱該結點序列是樹中從結點K1到結點Kj的一條路徑或道路。我們稱這條路徑的長度為j-1，它是該路徑所經過的邊(即連線兩個結點的線段)的數目。樹中任一結點有一條到其自身的長度為零的路徑。例如，在圖1中，結點A到結點I有一條路徑ABFI，它的長度為3。 如果在樹中存在一條從結點K到結點M的路徑，則稱結點K是結點M的祖先，也稱結點M是結點K的子孫或後裔。例如在圖1中，結點F的祖先有A，B和F自己，而它的子孫包括它自己和I,J。注意，任一結點既是它自己的祖先也是它自己的子孫。 我們將樹中一個結點的非自身祖先和子孫分別稱為該結點的真祖先和真子孫。在一棵樹中，樹根是唯一沒有真祖先的結點。葉結點是那些沒有真子孫的結點。子樹是樹中某一結點及其所有真子孫組成的一棵樹。 樹中一個結點的高度是指從該結點到作為它的子孫的各葉結點的最長路徑的長度。樹的高度是指根結點的高度。例如圖1中的結點B，C和D的高度分別為2，0和1，而樹的高度與結點A的高度相同為3。 從樹根到任一結點n有唯一的一條路徑，我們稱這條路徑的長度為結點n的深度或層數。根結點的深度為0，其餘結點的深度為其父結點的深度加1。深度相同的結點屬於同一層。例如，在圖1中，結點A的深度為0；結點B，C和D的深度為1；結點E，F，G，H的深度為2；結點I和J的深度為3。在樹的第二層的結點有E，F，J和H，樹的第0層只有一個根結點A。 樹的定義在某些結點之間確定了父子關係，我們又將這種關係延拓為祖先子孫關係。但是樹中的許多結點之間仍然沒有這種關係。例如兄弟結點之間就沒有祖先子孫關係。如果我們在樹的每一組兄弟結點之間定義一個從左到右的次序，則得到一棵有序樹；否則稱為無序樹。設結點n的所有兒子按其從左到右的次序排列為n1,n2,..,nk，則我們稱n1是n的最左兒子，或簡稱左兒子，並稱ni是ni-1的右鄰兄弟，或簡稱右兄弟(i=2,3,..k)。圖2中的兩棵樹作為無序樹是相同的，但作為有序樹是不同的，因為結點a的兩個兒子在兩棵樹中的左右次序是不同的。後面，我們只關心有序樹，因為無序樹總可能轉化為有序樹加以研究。圖2 兩棵不同的有序樹我們還可以將兄弟結點之間的左右次序關係加以延拓：如果a與b是兄弟，並且a在b的左邊，則認為a的任一子孫都在b的任一子孫的左邊。 森林是m(m>0)棵互不相交的樹的集合。如果我們刪去一棵樹的樹根，留下的子樹就構成了一個森林。當我們刪去的是一棵有序樹的樹根時，留下的子樹也是有序的，這些樹組成一個樹表。在這種情況下，稱這些樹組成的森林為有序森林或果園。 在討論表的時候，我們對錶的每一位置的元素賦予一個元素值。這裡，我們也用樹的結點來儲存元素，即對於樹中的每一個結點賦予一個標號，這個標號並不是該結點的名稱，而是儲存於該結點的一個值。結點的名稱總是不變的，而它的標號是可以改變的。我們可以做這樣的類比：樹：表 = 標號：元素 = 結點：位置
是資料結構中，用來描述“樹”型結構的名詞。這種結構像一根倒著的樹。每片樹葉都長在一個結點上，這個結點就叫做這個葉子的父結點，這個葉子叫做你結點的子結點，也叫這棵樹的葉結點，它再沒有子結點了。而葉子的父結點一定還會有上面的父結點，這樣一級一級上去就到了根結點，它就像是樹的根，它上面再沒有“叉兒”了樹的相關術語一個結點的兒子結點的個數稱為該結點的度。一棵樹的度是指該樹中結點的最大度數。 樹中度為零的結點稱為葉結點或終端結點。 樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。例如在圖1中，結點A，B和E的度分別為3，2，0。其中A為根結點,B為內部結點，E為葉結點，樹的度為3。 如果存在樹中的一個結點序列K1,K2,..,Kj，使得結點Ki是結點Ki+1的父結點(1≤i≤j)，則稱該結點序列是樹中從結點K1到結點Kj的一條路徑或道路。我們稱這條路徑的長度為j-1，它是該路徑所經過的邊(即連線兩個結點的線段)的數目。樹中任一結點有一條到其自身的長度為零的路徑。例如，在圖1中，結點A到結點I有一條路徑ABFI，它的長度為3。 如果在樹中存在一條從結點K到結點M的路徑，則稱結點K是結點M的祖先，也稱結點M是結點K的子孫或後裔。例如在圖1中，結點F的祖先有A，B和F自己，而它的子孫包括它自己和I,J。注意，任一結點既是它自己的祖先也是它自己的子孫。 我們將樹中一個結點的非自身祖先和子孫分別稱為該結點的真祖先和真子孫。在一棵樹中，樹根是唯一沒有真祖先的結點。葉結點是那些沒有真子孫的結點。子樹是樹中某一結點及其所有真子孫組成的一棵樹。 樹中一個結點的高度是指從該結點到作為它的子孫的各葉結點的最長路徑的長度。樹的高度是指根結點的高度。例如圖1中的結點B，C和D的高度分別為2，0和1，而樹的高度與結點A的高度相同為3。 從樹根到任一結點n有唯一的一條路徑，我們稱這條路徑的長度為結點n的深度或層數。根結點的深度為0，其餘結點的深度為其父結點的深度加1。深度相同的結點屬於同一層。例如，在圖1中，結點A的深度為0；結點B，C和D的深度為1；結點E，F，G，H的深度為2；結點I和J的深度為3。在樹的第二層的結點有E，F，J和H，樹的第0層只有一個根結點A。 樹的定義在某些結點之間確定了父子關係，我們又將這種關係延拓為祖先子孫關係。但是樹中的許多結點之間仍然沒有這種關係。例如兄弟結點之間就沒有祖先子孫關係。如果我們在樹的每一組兄弟結點之間定義一個從左到右的次序，則得到一棵有序樹；否則稱為無序樹。設結點n的所有兒子按其從左到右的次序排列為n1,n2,..,nk，則我們稱n1是n的最左兒子，或簡稱左兒子，並稱ni是ni-1的右鄰兄弟，或簡稱右兄弟(i=2,3,..k)。圖2中的兩棵樹作為無序樹是相同的，但作為有序樹是不同的，因為結點a的兩個兒子在兩棵樹中的左右次序是不同的。後面，我們只關心有序樹，因為無序樹總可能轉化為有序樹加以研究。圖2 兩棵不同的有序樹我們還可以將兄弟結點之間的左右次序關係加以延拓：如果a與b是兄弟，並且a在b的左邊，則認為a的任一子孫都在b的任一子孫的左邊。 森林是m(m>0)棵互不相交的樹的集合。如果我們刪去一棵樹的樹根，留下的子樹就構成了一個森林。當我們刪去的是一棵有序樹的樹根時，留下的子樹也是有序的，這些樹組成一個樹表。在這種情況下，稱這些樹組成的森林為有序森林或果園。 在討論表的時候，我們對錶的每一位置的元素賦予一個元素值。這裡，我們也用樹的結點來儲存元素，即對於樹中的每一個結點賦予一個標號，這個標號並不是該結點的名稱，而是儲存於該結點的一個值。結點的名稱總是不變的，而它的標號是可以改變的。我們可以做這樣的類比：樹：表 = 標號：元素 = 結點：位置