一、二叉樹的非終端結點
二叉樹的非終端結點是度不為0的結點稱為非終端結點或分支結點。終端結點是?? 度為0的結點稱為終端結點或葉子。二叉樹是一種樹形結構,其中每個結點非常多只有兩個子結點。在二叉樹中,有兩種類型的結點:終端結點和非終端結點。
葉子結點:也叫終端結點,是度為 0 的結點。
在計算機科學中,二叉樹是每個結點非常多有兩個子樹的樹結構。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。二叉樹常被用于實現二叉查找樹和二叉堆。
一棵深度為k,且有2^k-1個結點的二叉樹,稱為滿二叉樹。這種樹的特點是每一層上的結點數都是最大結點數。
而在一棵二叉樹中,除最后一層外,若其余層都是滿的,并且或者最后一層是滿的,或者是在右邊缺少連續若干結點,則此二叉樹為完全二叉樹。具有n個結點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹,至少有2k-1個葉子結點,至多有2k-1個結點。
延伸閱讀:
二、二叉樹的類型
1、完全二叉樹——若設二叉樹的高度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第h層有葉子結點,并且葉子結點都是從左到右依次排布,這就是完全二叉樹。
2、滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
3、平衡二叉樹——平衡二叉樹又被稱為AVL樹(區別于AVL算法),它是一棵二叉排序樹,且具有以下性質:它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,并且左右兩個子樹都是一棵平衡二叉樹。