seo网站建设时文章频率,苏州高端企业网站建设,成都app推广公司,长春网站建设q.479185700惠二叉搜索树 满足条件#xff1a; 1.对于根节点#xff1a;左子树中所有节点的值小于右子树中所有节点的值 2.任意节点的左右子树也是二叉搜索树#xff0c;同样满足条件1 二叉搜索树的常用操作 我们将二叉搜索树封装为一个类 BinarySearchTree #xff0c;并声明一个成员变…二叉搜索树 满足条件 1.对于根节点左子树中所有节点的值小于右子树中所有节点的值 2.任意节点的左右子树也是二叉搜索树同样满足条件1 二叉搜索树的常用操作 我们将二叉搜索树封装为一个类 BinarySearchTree 并声明一个成员变量 root 指向树的根节点 查找节点
给定目标值target,我们可以根据二叉搜索树的性质来查找声明一个节点cur从根节点开始遍历
若cur.valtarget说明target在cur的右子树执行curcur.right若cur.valtarget说明target在cur的左子树执行curcur.left若cur.valtarget,返回该节点跳出循环
/* 查找节点 */
TreeNode *search(int num) {TreeNode *cur root;// 循环查找越过叶节点后跳出while (cur ! nullptr) {// 目标节点在 cur 的右子树中if (cur-val num)cur cur-right;// 目标节点在 cur 的左子树中else if (cur-val num)cur cur-left;// 找到目标节点跳出循环elsebreak;}// 返回目标节点return cur;
}插入节点 查找插入位置从根节点出发根据当前节点值和 num 的大小关系循环向下搜索直到越过叶节点遍历至 None 时跳出循环 在该位置插入节点初始化节点 num 将该节点置于 None 的位置。 注意 二叉搜索树中不允许有重复的元素否则就违反了二叉搜索树的定义若待插入的节点在二叉搜索树中则不执行任何操作直接返回 为了实现插入节点我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时我们可以获取到其父节点从而完成节点插入操作 /* 插入节点 */
void insert(int num) {// 若树为空则初始化根节点if (root nullptr) {root new TreeNode(num);return;}TreeNode *cur root, *pre nullptr;// 循环查找越过叶节点后跳出while (cur ! nullptr) {// 找到重复节点直接返回if (cur-val num)return;pre cur;// 插入位置在 cur 的右子树中if (cur-val num)cur cur-right;// 插入位置在 cur 的左子树中elsecur cur-left;}// 插入节点TreeNode *node new TreeNode(num);if (pre-val num)pre-right node;elsepre-left node;
}删除节点 二叉搜索树的删除分为三种情况 当待删除节点的度为0时可以直接删除这个节点。当待删除节点的度为1时我们将子节点替换待删除的节点即可当待删除节点的度为2时我们无法删除这个节点而是需要一个节点替换这个节点因为要维持搜索二叉树的性质所以这个待删除节点的值可以是右子树的最小节点或者左子树的最大节点 /* 删除节点 */
void remove(int num) {// 若树为空直接提前返回if (root nullptr)return;TreeNode *cur root, *pre nullptr;// 循环查找越过叶节点后跳出while (cur ! nullptr) {// 找到待删除节点跳出循环if (cur-val num)break;pre cur;// 待删除节点在 cur 的右子树中if (cur-val num)cur cur-right;// 待删除节点在 cur 的左子树中elsecur cur-left;}// 若无待删除节点则直接返回if (cur nullptr)return;// 子节点数量 0 or 1if (cur-left nullptr || cur-right nullptr) {// 当子节点数量 0 / 1 时 child nullptr / 该子节点TreeNode *child cur-left ! nullptr ? cur-left : cur-right;// 删除节点 curif (cur ! root) {if (pre-left cur)pre-left child;elsepre-right child;} else {// 若删除节点为根节点则重新指定根节点root child;}// 释放内存delete cur;}// 子节点数量 2else {// 获取中序遍历中 cur 的下一个节点TreeNode *tmp cur-right;while (tmp-left ! nullptr) {tmp tmp-left;}int tmpVal tmp-val;// 递归删除节点 tmpremove(tmp-val);// 用 tmp 覆盖 curcur-val tmpVal;}
}
