什么是二叉树

二叉树

二叉树的节点不一定是满的，可能左孩子为空，也可能右孩子为空，也可能都为空，叶子结点既没有左孩子也没有右孩子。

二叉树天然递归性

什么是二分搜索树

二分搜索树满足所有二叉树的特性，同时还需具备下图的特性

二分搜索树

二分搜索树存储的数据必须有可比较性

向二分搜索树中添加元素的递归写法

递归添加元素，root为根结点

二分搜索树查询的递归写法

查询的递归写法，当递归到node为null时，说明没有没有节点的值与传入的值相等，返回false

二分搜索树的前序遍历（伪代码）

前序遍历

二分搜索树的中序遍历（中序遍历，将树上的所有元素按从小到大的顺序依次输出）

中序遍历

二分搜索树的后序遍历（应用于内存回收等场景：内存回收需要先回收子节点最后再回收根结点）

后序遍历

二分搜索树的遍历非递归实现（可以使用栈结构来实现前中后序遍历）

二分搜索树的层序遍历（广度优先遍历）

层序遍历

层序遍历使用队列实现，根节点进队列，根节点被访问出队列后，根节点的左右孩子入队列（先左后右），访问完左孩子后，左孩子的左右节点入队，左孩子出队列，接着访问根节点的右孩子，接着右孩子出队，右孩子的左右节点入队，以此类推

意义

二分搜索树元素的删除

当待删除元素没有孩子节点，或者只有左孩子或右孩子时，操作相对简单，而当待删除节点同时有左右孩子节点时，则在删除当前节点时，要从当前节点的右侧的子二分搜索树中找出最小节点，作为当前节点的替代~

二分搜索树在极端情况下可能退化成链表，级当加入的节点正好是从大到小或者从小到大依次往里添加~

退化成链表的二分搜索树在添加，查询，和删除时的时间复杂度均为O（n）级别，和链表一致，此时二分搜索树的性能会急剧下降
这里也就引出了平衡二叉树的概念