二叉排序树
1. 二叉树的基本概念
1.1 定义
略
1.2性质
由定义可以得出二叉排序树的一个重要性质：中序遍历是一个二叉排序树时可以得到一个递增有序数列。
2.二叉树的基本运算
2.1插入结点
略
2.2 建立二叉排序树
略
2.3输出二叉排序树
略
2.4删除结点
2.4.1原理
从二叉排序树中删除一个结点，必须保证删除后所得二叉树仍然满足二叉排序树的性质不变。
2.4.2思路
- 首先确定删除的结点p是否在二叉树内
- 如果在，我们假设结点f为p的双亲，结点s为p的直接前驱（即s为p左子树中权值最大的结点，右孩子的情况类似），结点q为s的双亲
2.4.3几种情况
1. 删除叶子结点
直接删除
2.删除单分支结点
将删除结点的孩子当成双亲结点f的孩子
3.双分支结点
（1）可以选择p左子树的最小值替换它（主要）
（2）也可以选择p右子树中权值最小的替换它
原理：这两个结点刚好是二叉排序树