樹

基本術(shù)語

結(jié)點(diǎn)
結(jié)點(diǎn)的度：擁有子樹的個(gè)數(shù)
葉子結(jié)點(diǎn)：度為0
分支結(jié)點(diǎn)：度不為0
孩子，雙親和兄弟
結(jié)點(diǎn)的層數(shù)
樹的深度
樹的度：表示樹中各結(jié)點(diǎn)度的最大值
有序樹和無序樹：各子樹從左到右是有次序的
森林：表示m顆互不相交的樹的集合

二叉樹

定義

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

滿二叉樹和完全二叉樹

滿二叉樹：深度為h且含有2^h-1個(gè)結(jié)點(diǎn)的二叉樹
完全二叉樹：

性質(zhì)

一顆非空二叉樹的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn)
一顆深度為h的二叉樹最多具有2^h-1個(gè)結(jié)點(diǎn)
對(duì)于一顆非空二叉樹，若其具有N0個(gè)葉子結(jié)點(diǎn)，有N2個(gè)度為2的結(jié)點(diǎn)，則有N0=N2+1
具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為【log2^n】+1