0. 前言
本文不是從入門到精通式的文章寞缝。寫該文的目的是理清樹結(jié)構(gòu)及其解題思路，所以講解不多而概念性的東西比較多仰泻，請見諒荆陆。
本文結(jié)構(gòu)：
- 概念鋪墊
- 二叉樹
- 各種相關(guān)算法
- 例題相關(guān)
1. 概念鋪墊
- 樹等價于連通無環(huán)圖，由一組頂點(diǎn)(vertex)和邊(edge)構(gòu)成集侯。其中被啼，如圖所示，A點(diǎn)為根頂點(diǎn)(root)棠枉。一般情況下浓体，我們多稱頂點(diǎn)為節(jié)點(diǎn)(node)。
祖先(ancestor)、后代(descendant)月幌、父親(parent)碍讯、孩子(child)、子樹(subtree)扯躺、葉子節(jié)點(diǎn)(leaf)捉兴、度(degree)：在節(jié)點(diǎn)
v尋根過程中經(jīng)過的每一個節(jié)點(diǎn)都是其祖先蝎困，節(jié)點(diǎn)v是其后代。依舊以上圖為例倍啥，節(jié)點(diǎn)E的祖先是B和A禾乘，E是B和A的后代，而B又是A的后代逗栽。
父親<-->孩子是特殊的祖先<-->后代關(guān)系盖袭。若節(jié)點(diǎn)u是v的祖先且恰好比v高一層，則稱u是v的父親彼宠，v是u的孩子鳄虱。例如：B與E即為一對父子關(guān)系。
節(jié)點(diǎn)u所有的后代及其之間的連接邊稱為子樹凭峡，記作subtree(v)拙已。例如圖中的B D F就構(gòu)成一棵子樹。當(dāng)一個節(jié)點(diǎn)沒有后代（沒有孩子）時摧冀，我們稱之為葉子節(jié)點(diǎn)倍踪。例如，圖中的D E F G都是葉子節(jié)點(diǎn)索昂。
節(jié)點(diǎn)u的孩子總數(shù)稱為u的度建车。例如，節(jié)點(diǎn)c的度為2椒惨，因?yàn)?c有兩個孩子F G缤至。葉子節(jié)點(diǎn)的度為0。深度(depth)康谆、高度(height)：沿節(jié)點(diǎn)
v到r唯一通路所經(jīng)過邊的數(shù)目领斥，稱為節(jié)點(diǎn)v的深度，記作depth(v)沃暗。例如上圖中月洛，從節(jié)點(diǎn)E走到根節(jié)點(diǎn)A的邊數(shù)是2，所以depth(E) = 2孽锥。設(shè)節(jié)點(diǎn)v深度為v_d嚼黔，那么我們可以認(rèn)為節(jié)點(diǎn)v處于在第v_d層。特別地忱叭，約定根頂點(diǎn)root的深度為0隔崎，即depth(root) = 0。
樹T中所有節(jié)點(diǎn)深度最大值稱作該樹的高度韵丑，記作height(T)。通常約定虚缎，僅有一個節(jié)點(diǎn)的樹高度為0撵彻，空樹高度為-1钓株。例如，圖中所未二叉樹高度為2陌僵。有些博客文章轴合、教材、講義中認(rèn)為該樹高度為3碗短，也正確受葛。因?yàn)閺闹庇^角度來說是3層樹，而本文約定高度為2是為方便編程偎谁。
2. 二叉樹(binary tree)
定義：如上圖所示总滩，二叉樹是每個節(jié)點(diǎn)最多只有兩個分支（即不存在分支度大于2的節(jié)點(diǎn)）的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”巡雨。二叉樹的分支具有左右次序闰渔，不能隨意顛倒。
性質(zhì)：
- 在二叉樹中铐望，每個節(jié)點(diǎn)的度
冈涧；
- 同一節(jié)點(diǎn)的孩子可以左右區(qū)分，即具有左右次序（有序）正蛙，故二叉樹又可稱為二叉有序樹(ordered binary tree)督弓。
2.1 二叉搜索樹（Binary Search Tree, BST）
首先要明確一點(diǎn)的是，二叉搜索樹滿足所有普通二叉樹的特征乒验。但相比普通二叉樹而言愚隧，二叉搜索樹又有如下特征：
假定節(jié)點(diǎn)為k:
- 左子樹存儲著值小于k的節(jié)點(diǎn)
- 右子樹存儲著值大于k的節(jié)點(diǎn)
- 每棵子樹都滿足如上兩條特征
References
- 鄧俊輝. 數(shù)據(jù)結(jié)構(gòu): C++ 語言版[M]. 清華大學(xué)出版社, 2012.
- 二叉樹--維基百科
- GeeksforGeeks二叉搜索樹專題（英文版）
