一、什么是二叉树
1. 什么是树。
计算机科学里面的树本质是一个树状图。树首先是一个有向无环图，由根节点指向子结点。但是不严格的说，我们也研究无向树。所谓无向树就是将有向树的所有边看成无向边形成的树状图。树是一种递归的数据结构，所以我们研究树也是按照递归的方式去研究的。
2.什么是二叉树。
我们给出二叉树的递归定义如下：
（1）空树是一个二叉树。
（2）单个节点是一个二叉树。
（3）如果一棵树中，以它的左右子节点为根形成的子树都是二叉树，那么这棵树本身也是二叉树。
二、BST
1.什么是二叉排序树。
二叉排序树是一种二叉树，它满足树的中序遍历是有序的。
2.BST（Binary Search Tree）。
二叉查找树是一种最普通的二叉排序树，一般称作BST，也称为B-树。在这棵树中，满足在任意一个子树中，都满足左子树 < 根节点 < 右子树，即该树的中序遍历满足从小到大排序的结果。
3.如何构造一个二叉排序树？
很显然，要想构造一个BST，就必须在插入节点时，满足下面的原则：
（1）如果节点为空，则直接插入到该节点。
（2）如果节点不为空，且要插入的值小于等于当前节点的值，那么则将该节点插入到左子树当中。
（3）如果节点不为空，且要插入的值大于当前节点的值，那么则将该节点插入到右子树当中。
4.利用BST的性质对一个数组进行剃重。
由于BST有二叉排序树的性质，我们可以利用这样的性质对一个待定数组进行剃重。原理很简单，只需要在插入的时候如果已经发现了相等的节点的话，那么则不进行插入即可。也就是说，只有该树没有的节点，我们才进行相应的插入操作。
延伸阅读
- ssh框架 2016-09-30
- 阿里移动安全 [无线安全]玩转无线电——不安全的蓝牙锁 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实现JSON转Model - HandyJSON使用讲解 2017-07-26
- 阿里移动安全 Android端恶意锁屏勒索应用分析 2017-07-26
- 集合结合数据结构来看看(二) 2017-07-26
学习是年轻人改变自己的最好方式