定義
二叉樹是一個連通的無環(huán)圖，并且每一個頂點(diǎn)的度不大于3。有根二叉樹還要滿足根結(jié)點(diǎn)的度不大于2。有了根結(jié)點(diǎn)之后，每個頂點(diǎn)定義了唯一的父結(jié)點(diǎn)，和最多2個子結(jié)點(diǎn)。然而，沒有足夠的信息來區(qū)分左結(jié)點(diǎn)和右結(jié)點(diǎn)。如果不考慮連通性，允許圖中有多個連通分量，這樣的結(jié)構(gòu)叫做森林。
基本概念
二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：
(1)空二叉樹——如圖(a)；
(2)只有一個根結(jié)點(diǎn)的二叉樹——如圖(b)；
(3)只有左子樹——如圖(c)；
(4)只有右子樹——如圖(d)；
(5)完全二叉樹——如圖(e)。
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形
類型
(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結(jié)點(diǎn)外每一個結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。
(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
辨析
二叉樹不是樹的一種特殊情形，盡管其與樹有許多相似之處，但樹和二叉樹有兩個主要差別：
- 樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；
- 樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分。
術(shù)語：
樹的結(jié)點(diǎn)（node）：包含一個數(shù)據(jù)元素及若干指向子樹的分支；
孩子結(jié)點(diǎn)（child node）：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；
雙親結(jié)點(diǎn)：B 結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親；
兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)； 堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；
祖先結(jié)點(diǎn): 從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn)子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫
結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推；
樹的深度：樹中最大的結(jié)點(diǎn)層
結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個數(shù)
樹的度： 樹中最大的結(jié)點(diǎn)度。
葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)；
分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；
有序樹：子樹有序的樹，如：家族樹；
無序樹：不考慮子樹的順序；
