0. 前言
本文不是從入門到精通式的文章。寫該文的目的是理清樹結(jié)構(gòu)及其解題思路，所以講解不多而概念性的東西比較多，請(qǐng)見諒。
本文結(jié)構(gòu)：
- 概念鋪墊
- 二叉樹
- 各種相關(guān)算法
- 例題相關(guān)
1. 概念鋪墊
- 樹等價(jià)于連通無環(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)過的每一個(gè)節(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即為一對(duì)父子關(guān)系。
節(jié)點(diǎn)u所有的后代及其之間的連接邊稱為子樹，記作subtree(v)。例如圖中的B D F就構(gòu)成一棵子樹。當(dāng)一個(gè)節(jié)點(diǎn)沒有后代（沒有孩子）時(shí)，我們稱之為葉子節(jié)點(diǎn)。例如，圖中的D E F G都是葉子節(jié)點(diǎn)。
節(jié)點(diǎn)u的孩子總數(shù)稱為u的度。例如，節(jié)點(diǎn)c的度為2，因?yàn)?c有兩個(gè)孩子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)。通常約定，僅有一個(gè)節(jié)點(diǎn)的樹高度為0，空樹高度為-1。例如，圖中所未二叉樹高度為2。有些博客文章、教材、講義中認(rèn)為該樹高度為3，也正確。因?yàn)閺闹庇^角度來說是3層樹，而本文約定高度為2是為方便編程。
2. 二叉樹(binary tree)
定義：如上圖所示，二叉樹是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支（即不存在分支度大于2的節(jié)點(diǎn)）的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”。二叉樹的分支具有左右次序，不能隨意顛倒。
性質(zhì)：
- 在二叉樹中，每個(gè)節(jié)點(diǎn)的度
；
- 同一節(jié)點(diǎn)的孩子可以左右區(qū)分，即具有左右次序（有序），故二叉樹又可稱為二叉有序樹(ordered binary tree)。
2.1 二叉搜索樹（Binary Search Tree, BST）
首先要明確一點(diǎn)的是，二叉搜索樹滿足所有普通二叉樹的特征。但相比普通二叉樹而言，二叉搜索樹又有如下特征：
假定節(jié)點(diǎn)為k:
- 左子樹存儲(chǔ)著值小于k的節(jié)點(diǎn)
- 右子樹存儲(chǔ)著值大于k的節(jié)點(diǎn)
- 每棵子樹都滿足如上兩條特征
References
- 鄧俊輝. 數(shù)據(jù)結(jié)構(gòu): C++ 語言版[M]. 清華大學(xué)出版社, 2012.
- 二叉樹--維基百科
- GeeksforGeeks二叉搜索樹專題（英文版）
