一、什么是二叉樹
1. 什么是樹。
計(jì)算機(jī)科學(xué)里面的樹本質(zhì)是一個(gè)樹狀圖。樹首先是一個(gè)有向無(wú)環(huán)圖，由根節(jié)點(diǎn)指向子結(jié)點(diǎn)。但是不嚴(yán)格的說(shuō)，我們也研究無(wú)向樹。所謂無(wú)向樹就是將有向樹的所有邊看成無(wú)向邊形成的樹狀圖。樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，所以我們研究樹也是按照遞歸的方式去研究的。
2.什么是二叉樹。
我們給出二叉樹的遞歸定義如下：
（1）空樹是一個(gè)二叉樹。
（2）單個(gè)節(jié)點(diǎn)是一個(gè)二叉樹。
（3）如果一棵樹中，以它的左右子節(jié)點(diǎn)為根形成的子樹都是二叉樹，那么這棵樹本身也是二叉樹。
二、BST
1.什么是二叉排序樹。
二叉排序樹是一種二叉樹，它滿足樹的中序遍歷是有序的。
2.BST（Binary Search Tree）。
二叉查找樹是一種最普通的二叉排序樹，一般稱作BST，也稱為B-樹。在這棵樹中，滿足在任意一個(gè)子樹中，都滿足左子樹 < 根節(jié)點(diǎn) < 右子樹，即該樹的中序遍歷滿足從小到大排序的結(jié)果。
3.如何構(gòu)造一個(gè)二叉排序樹？
很顯然，要想構(gòu)造一個(gè)BST，就必須在插入節(jié)點(diǎn)時(shí)，滿足下面的原則：
（1）如果節(jié)點(diǎn)為空，則直接插入到該節(jié)點(diǎn)。
（2）如果節(jié)點(diǎn)不為空，且要插入的值小于等于當(dāng)前節(jié)點(diǎn)的值，那么則將該節(jié)點(diǎn)插入到左子樹當(dāng)中。
（3）如果節(jié)點(diǎn)不為空，且要插入的值大于當(dāng)前節(jié)點(diǎn)的值，那么則將該節(jié)點(diǎn)插入到右子樹當(dāng)中。
4.利用BST的性質(zhì)對(duì)一個(gè)數(shù)組進(jìn)行剃重。
由于BST有二叉排序樹的性質(zhì)，我們可以利用這樣的性質(zhì)對(duì)一個(gè)待定數(shù)組進(jìn)行剃重。原理很簡(jiǎn)單，只需要在插入的時(shí)候如果已經(jīng)發(fā)現(xiàn)了相等的節(jié)點(diǎn)的話，那么則不進(jìn)行插入即可。也就是說(shuō)，只有該樹沒有的節(jié)點(diǎn)，我們才進(jìn)行相應(yīng)的插入操作。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式