数据结构(2)——排序二叉树
因因排序二叉树
因因首先如果普通二叉树每个节点满足:因因左子树所有节点值小于它的根节点值,且右子树所有节点值大于它的根节点值,因则这样的二叉树就是排序二叉树。 因因
因因插入操作
因因首先要从根节点开始往下找到自己要插入的位置(因即新节点的父节点因);具体流程是:因新节点与当前节点比较,如果相同则表示已经存在且不能再重复插入;因如果小于当前节点,则到左子树中寻找,如果左子树为空则当前节点为要找的父节点,新节点插入到当前节点的左子树即可;因如果大于当前节点,则到右子树中寻找,如果右子树为空则当前节点为要找的父节点,新节点插入到当前节点的右子树即可。因因
因因删除操作
因因删除操作主要分为三种情况,因即要删除的节点无子节点,因要删除的节点只有一个子节点,因要删除的节点有两个子节点。
因因1. 对于要删除的节点无子节点可以直接删除,因即让其父节点将该子节点置空即可。因因
因因2. 对于要删除的节点只有一个子节点,因则替换要删除的节点为其子节点。因因
因因3. 对于要删除的节点有两个子节点,则首先找该节点的替换节点(因即右子树中最小的节点因),接着替换要删除的节点为替换节点,然后删除替换节点。因因
查询操作
因因查找操作的主要流程为:因先和根节点比较,如果相同就返回,如果小于根节点则到左子树中递归查找,如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大(因最右最深子节点因)和最小(因最左最深子节点因)值。因因