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