网站建设方案解救苏州久远网络,开发一套微商城多少钱,ui导航设计,企业网站备案申请文章目录 1. 二叉搜索树的概念2. 二叉搜索树的操作1.1 二叉搜索树的查找1.2 二叉搜索树的插入1.3 二叉搜索树的删除 1. 二叉搜索树的概念
二叉搜索树又称二叉排序树#xff0c;它可能是一棵空树#xff0c;也可能是具有以下性质的二叉树#xff1a;
若它的左子树不为空它可能是一棵空树也可能是具有以下性质的二叉树
若它的左子树不为空则左子树上所有节点的值都小于根节点的值。若它的右子树不为空则右子树上所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树。 2. 二叉搜索树的操作 int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };1.1 二叉搜索树的查找
从根开始比较、查找比根大则往右边走查找比根小则往左边走查找。最多查找高度次若走到空还没找到则这个值不存在。
1.2 二叉搜索树的插入
树为空则直接新增节点赋值给 root 指针。树不空按二叉搜索树性质查找插入位置插入新节点。 1.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在就返回否则要删除的节点可能分下面四种情况
要删除的节点无孩子节点要删除的节点只有左孩子节点要删除的节点只有右孩子节点要删除的节点有左、右孩子节点。
看起来待删除节点有 4 种情况实际情况 a 可以与情况 b 或者情况 c 合并起来因此真正的删除过程如下
情况 b 删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点 - 直接删除情况 c 删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点 - 直接删除情况 d 在它的右子树中寻找中序下的第一个节点关键码最小用它的值填补到被删除节点中再来处理该节点的删除问题 - 替换法删除。 本文完
