定義
二叉樹（binary tree）是指樹中節點的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節點和兩棵互不相交的，分别稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹。
基本形态
二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形态：
1、空二叉樹——如圖1（a）；
2、隻有一個根結點的二叉樹——如圖1（b）；
3、隻有左子樹——如圖1（c）；
4、隻有右子樹——如圖1（d）；
5、完全二叉樹——如圖1（e）。
特殊類型
1、滿二叉樹：如果一棵二叉樹隻有度為0的結點和度為2的結點，并且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。
2、完全二叉樹：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編号從1到n的結點一一對應時，稱為完全二叉樹。
完全二叉樹的特點是葉子結點隻可能出現在層序最大的兩層上，并且某個結點的左分支下子孫的最大層序與右分支下子孫的最大層序相等或大1。
相關術語
①結點：包含一個數據元素及若幹指向子樹分支的信息。
②結點的度：一個結點擁有子樹的數目稱為結點的度。
③葉子結點：也稱為終端結點，沒有子樹的結點或者度為零的結點。
④分支結點：也稱為非終端結點，度不為零的結點稱為非終端結構。
⑤樹的度：樹中所有結點的度的最大值。
⑥結點的層次：從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位于第L層，則其子節點位于第L+1層。
⑦樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度。
⑧有序樹：如果樹中各棵子樹的次序是有先後次序，則稱該樹為有序樹。
⑨無序樹：如果樹中各棵子樹的次序沒有先後次序，則稱該樹為無序樹。
⑩森林：由m（m≥0）棵互不相交的樹構成一片森林。如果把一棵非空的樹的根結點删除，則該樹就變成了一片森林，森林中的樹由原來根結點的各棵子樹構成。
二叉樹性質
性質1：二叉樹的第i層上至多有2i-1（i≥1）個節點。
性質2：深度為h的二叉樹中至多含有2h-1個節點。
性質3：若在任意一棵二叉樹中，有n0個葉子節點，有n2個度為2的節點，則必有n0=n2+1。
性質4：具有n個節點的完全二叉樹深為log2x+1（其中x表示不大于n的最大整數)。
性質5：若對一棵有n個節點的完全二叉樹進行順序編号（1≤i≤n），那麼，對于編号為i（i≥1）的節點；
當i=1時，該節點為根，它無雙親節點。
當i>1時，該節點的雙親節點的編号為i/2。
若2i≤n，則有編号為2i的左節點，否則沒有左節點。
若2i+1≤n，則有編号為2i+1的右節點，否則沒有右節點。
二叉樹遍曆
遍曆是對樹的一種最基本的運算，所謂遍曆二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且隻被訪問一次。由于二叉樹是非線性結構，因此，樹的遍曆實質上是将二叉樹的各個結點轉換成為一個線性序列來表示。
線索二叉樹
按照某種遍曆方式對二叉樹進行遍曆，可以把二叉樹中所有結點排列為一個線性序列。在該序列中，除第一個結點外，每個結點有且僅有一個直接前驅結點；除最後一個結點外，每個結點有且僅有一個直接後繼結點。但是，二叉樹中每個結點在這個序列中的直接前驅結點和直接後繼結點是什麼，二叉樹的存儲結構中并沒有反映出來，隻能在對二叉樹遍曆的動态過程中得到這些信息。為了保留結點在某種遍曆序列中直接前驅和直接後繼的位置信息，可以利用二叉樹的二叉鍊表存儲結構中的那些空指針域來指示。這些指向直接前驅結點和指向直接後繼結點的指針被稱為線索（thread），加了線索的叉樹稱為線索二叉樹。線索二叉樹将為二叉樹的遍曆提供許多遍曆。
