二叉樹的概念
概念
一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹
的二叉樹組成。
二叉樹的特點：
- 每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點。
- 二叉樹的子樹有左右之分，其子樹的次序不能顛倒。
特殊二叉樹
- 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是
說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。 - 完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K
的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對
應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
關于樹的名詞解釋
節點的度：一個節點含有的子樹的個數稱為該節點的度；
葉節點或終端節點：度為0的節點稱為葉節點；
非終端節點或分支節點：度不為0的節點；
雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
兄弟節點：具有相同父節點的節點互稱為兄弟節點；
樹的度：一棵樹中，最大的節點的度稱為樹的度；
節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
樹的高度或深度：樹中節點的最大層次；
堂兄弟節點：雙親在同一層的節點互為堂兄弟；
節點的祖先：從根到該節點所經分支上的所有節點；
子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
