樹，這是一棵樹哼凯，這是一種非線性結(jié)構(gòu)欲间。在前面我們所學(xué)習(xí)的都是線性結(jié)構(gòu)，而他們的特點是表中的元素相互之間都是線性關(guān)系断部，邏輯較為清晰猎贴，容易進行查找、插入和刪除操作蝴光，這種數(shù)據(jù)結(jié)構(gòu)描述的是一種元素只唯一前驅(qū)元素和唯一后繼元素的模型她渴。
而樹這種非線性結(jié)構(gòu)是相對于線性結(jié)構(gòu)而言的，相比起線性結(jié)構(gòu)中元素之間一對一的關(guān)系蔑祟，樹型結(jié)構(gòu)中元素之間是一對多的關(guān)系趁耗。樹是一種十分重要的非線性結(jié)構(gòu)。
樹的基本概念
樹的定義
樹是n（n>=0）個元素的的有限集合疆虚，既然被叫做樹对粪，那么自然有根有葉子。在任何一顆非空樹中：
- 有且僅有一個節(jié)點被稱為根節(jié)點装蓬，而且我們一般把根節(jié)點提到整棵數(shù)的最上面
- 當n>1時著拭，除根以外的其余節(jié)點可一被分為m（m>0）個互不相交的有限集合T1，……,Tn,其中每一個集合本身又是一顆樹牍帚，并且稱為根的子樹
這真的是個很繞的東西儡遮，不過由此可以看出，樹的定義是具有遞歸性的暗赶，即樹中有樹鄙币，當一顆樹只有一個節(jié)點時肃叶，該節(jié)點被稱為根節(jié)點。當有多個節(jié)點時十嘿，除了根節(jié)點外因惭，它還有多棵子樹，每棵子樹都互不相交绩衷。
樹的相關(guān)術(shù)語
一般而言蹦魔，就像圖片描述的，圖中的圓圈代表節(jié)點咳燕，線代表邊勿决，圈內(nèi)的東東就是這個節(jié)點的信息。
- 節(jié)點：樹中的數(shù)據(jù)元素稱為節(jié)點招盲，每個節(jié)點都保存了該節(jié)點的信息低缩，即數(shù)據(jù)元素和數(shù)據(jù)項與數(shù)據(jù)元素之間的關(guān)系
- 節(jié)點的度：節(jié)點擁有子樹的個數(shù)
- 樹的度：樹中各節(jié)點的度的最大值
- 葉子節(jié)點： 樹中度為0的節(jié)點，也叫做終端節(jié)點
- 分支節(jié)點： 樹中度不為0的節(jié)點曹货，稱為分支節(jié)點或非終端節(jié)點
- 兒子：節(jié)點子樹的根咆繁，兒子節(jié)點簡稱為子節(jié)點
- 父親：有兒子的就是父親，父親節(jié)點簡稱為父節(jié)點
- 兄弟：有同一父親的節(jié)點被稱為兄弟節(jié)點
- 堂兄弟：位于同一層顶籽，但是沒有同一父親的子節(jié)點稱為堂兄弟
- 樹的深度：樹中節(jié)點節(jié)點的最大層數(shù)玩般，圖中的樹深度為3
- 節(jié)點的層次：從根節(jié)點開始，根為第一層蜕衡，根的孩子為第二層壤短，以此類推，如果某節(jié)點在第k層慨仿，那么其子樹的根就在k+1層久脯。
- 根：唯一一個沒有前驅(qū)的節(jié)點（無父節(jié)點），此節(jié)點為根節(jié)點
- 森林： 指m棵互不相交的樹的集合镰吆，一棵樹的子樹就構(gòu)成一個森林
- 有序樹： 如果樹中節(jié)點的各棵子樹規(guī)定從左至右是有序的（不能互換）帘撰，則稱為有序樹，否則稱為無序樹万皿。二叉樹就是一種有序樹摧找。
- 無序樹：不是有序樹就是無序樹了（= =||），就是節(jié)點的各個子樹可以互換位置
二叉樹
樹型結(jié)構(gòu)中有一種特殊的樹叫做二叉樹牢硅，二叉樹的結(jié)構(gòu)也比較簡單蹬耘，規(guī)律性較強，并且可以證明减余，即使一般的樹也能轉(zhuǎn)化成二叉樹综苔。而且許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往就是二叉樹的形式。
二叉樹的定義
二叉樹是個有限元素的集合，該集合為空或者由一個根和兩個互不相交的左子樹和右子樹組成如筛。在二叉樹中堡牡，一個元素也稱為一個節(jié)點。
二叉樹的基本特征：
- 每個節(jié)點最多只有兩棵子樹杨刨，即不存在度大于2的節(jié)點
- 左子樹和右子樹次序不能顛倒晤柄，即二叉樹是有序樹，而且哪怕只有
一顆子樹妖胀，也要區(qū)分是左子樹還是右子樹芥颈。
二叉樹有五中基本形態(tài)：
- 空集
- 根有兩顆子樹
- 根只有一顆子樹（左子樹或右子樹）
- 根沒有子樹
在二叉樹中有兩種特殊的二叉樹：滿二叉樹和完全二叉樹
滿二叉樹
在一棵樹中所有的分支節(jié)點都存在左子樹和右子樹，并且所有的葉子節(jié)點都在同一層上做粤，這樣的二叉樹稱為滿二叉樹浇借。
完全二叉樹
一棵深度為k且具有n個節(jié)點的二叉樹捉撮，對樹中節(jié)點按從上至下怕品，從左至右的順序進行編號，當且僅當節(jié)點都與深度為k的滿二叉樹中編號從1至n的節(jié)點一一對應(yīng)
時巾遭，才稱這棵二叉樹為完全二叉樹肉康。顯然滿二叉樹也是完全二叉樹的一種。
完全二叉樹的特點：
- 葉子節(jié)點只可能在層次最大的兩層上出現(xiàn)
-
對任一節(jié)點灼舍，其右分支下的兒子的最大層次為h吼和，則其左分支下的兒子最大層次為
h或h+1
完全二叉樹
