一、二叉樹(shù)的非終端結(jié)點(diǎn)

二叉樹(shù)的非終端結(jié)點(diǎn)是度不為0的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。終端結(jié)點(diǎn)是?? 度為0的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)或葉子。二叉樹(shù)是一種樹(shù)形結(jié)構(gòu)，其中每個(gè)結(jié)點(diǎn)非常多只有兩個(gè)子結(jié)點(diǎn)。在二叉樹(shù)中，有兩種類(lèi)型的結(jié)點(diǎn)：終端結(jié)點(diǎn)和非終端結(jié)點(diǎn)。

葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)。

在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)結(jié)點(diǎn)非常多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱(chēng)作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）。二叉樹(shù)常被用于實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。

一棵深度為k，且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，稱(chēng)為滿二叉樹(shù)。這種樹(shù)的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。

而在一棵二叉樹(shù)中，除最后一層外，若其余層都是滿的，并且或者最后一層是滿的，或者是在右邊缺少連續(xù)若干結(jié)點(diǎn)，則此二叉樹(shù)為完全二叉樹(shù)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為floor(log2n)+1。深度為k的完全二叉樹(shù)，至少有2k-1個(gè)葉子結(jié)點(diǎn)，至多有2k-1個(gè)結(jié)點(diǎn)。

延伸閱讀：

二、二叉樹(shù)的類(lèi)型

1、完全二叉樹(shù)——若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹(shù)。

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

3、平衡二叉樹(shù)——平衡二叉樹(shù)又被稱(chēng)為AVL樹(shù)（區(qū)別于AVL算法），它是一棵二叉排序樹(shù)，且具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。