樹

基本術語

結點

結點的度：擁有子樹的個數

葉子結點：度為0

分支結點：度不為0

孩子，雙親和兄弟

結點的層數

樹的深度

樹的度：表示樹中各結點度的最大值

有序樹和無序樹：各子樹從左到右是有次序的

森林：表示m顆互不相交的樹的集合

二叉樹

定義

度不大于2，而且是一種有序樹

滿二叉樹和完全二叉樹

滿二叉樹：深度為h且含有2^h-1個結點的二叉樹

完全二叉樹：

性質

一顆非空二叉樹的第i層上最多有2^(i-1)個結點

一顆深度為h的二叉樹最多具有2^h-1個結點

對于一顆非空二叉樹，若其具有N0個葉子結點，有N2個度為2的結點，則有N0=N2+1

具有n個結點的完全二叉樹的深度為【log2^n】+1