当前位置： 首页 > news >正文

编程网站scratch中国最大网站排名

news 2025/8/2 16:14:34
编程网站scratch,中国最大网站排名,.net美食网站开发源代码,长春市网站制作创建二叉搜索树 二叉搜索树 二叉搜索树是有数值的了，二叉搜索树是一个有序树。 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它…

  1. 创建二叉搜索树

二叉搜索树

二叉搜索树是有数值的了，二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

  • 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树

bstree.c（二叉搜索树）


#include <stdio.h>
#include <stdlib.h>
#define SIZE 10//二叉树节点
struct BSTree_node
{unsigned int elem;struct BSTree_node *ltree, *rtree;  // 左右子树
};struct BSTree_node *create_bstree(unsigned int *pt, int n);
struct BSTree_node *insert_bstree(struct BSTree_node *T, unsigned int elem);
void in_order(struct BSTree_node *tree);int main(void)
{unsigned int num;unsigned int arr[SIZE] = {37, 22, 11, 82, 67, 9, 45, 91, 33, 52}; // 无序数组struct BSTree_node *mytree = NULL;mytree = create_bstree(arr, SIZE);  // 创建二叉树in_order(mytree); // 中序遍历printf("\n");return 0;
}// 创建二叉搜索树
struct BSTree_node *create_bstree(unsigned int *pt, int n)
{struct BSTree_node *tree = NULL;for(int i = 0; i < n; i++){tree = insert_bstree(tree, *pt);pt++;}return tree;
}struct BSTree_node *insert_bstree(struct BSTree_node *T, unsigned int elem)
{if(!T){T = (struct BSTree_node *)malloc(sizeof(struct BSTree_node));T->elem = elem;T->ltree = T->rtree = NULL;}else if(elem < T->elem);{T->ltree = insert_bstree(T->ltree, elem);   //递归}else if(elem > T->elem);{T->rtree = insert_bstree(T->rtree, elem);   //递归}else{printf("inserting repeat node is fobidden.\n");exit(0);}return T;
}
// 遍历
void in_order(struct BSTree_node *tree)
{if(tree){in_order(tree->ltree);printf("%d", tree->elem);in_order(tree->rtree);}
}

力扣题目

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：


节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：


输入：root = [2,1,3]
输出：true

示例 2：


输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
//递归1  ---》中序遍历 左 - 中 - 右，所以中序遍历应该是有序数组（单调递增）
class Solution {
private:vector<int> vec;void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);    // 左vec.push_back(root->val); // 中 // 将二叉搜索树转换为有序数组traversal(root->right);   // 右}
public:bool isValidBST(TreeNode* root) {vec.clear(); // 不加这句在leetcode上也可以过，但最好加上traversal(root);for (int i = 1; i < vec.size(); i++) {// 注意要小于等于，搜索树里不能有相同元素if (vec[i] <= vec[i - 1]) return false;}return true;}
};//递归2  中序遍历
class Solution {
public:TreeNode* pre = NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root == NULL) return true;      // 空二叉树属于任何是各种二叉树bool left = isValidBST(root->left);   // 左if (pre != NULL && pre->val >= root->val) return false;pre = root; // 记录前一个节点bool right = isValidBST(root->right); // 右return left && right;}
};//迭代
class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL; // 记录前一个节点while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->left;                // 左} else {cur = st.top();                 // 中st.pop();if (pre != NULL && cur->val <= pre->val)return false;pre = cur; //保存前一个访问的结点cur = cur->right;               // 右}}return true;}
};

  1. 查找_添加二叉搜索树

二叉搜索树插入以及查找数值

bstree_find.c


#include <stdio.h>
#include <stdlib.h>
#define SIZE 10//二叉树节点
struct BSTree_node
{unsigned int elem;struct BSTree_node *ltree, *rtree;  // 左右子树
};struct BSTree_node *create_bstree(unsigned int *pt, int n);
struct BSTree_node *insert_bstree(struct BSTree_node *T, unsigned int elem);
void in_order(struct BSTree_node *tree);int main(void)
{unsigned int num;unsigned int arr[SIZE] = {37, 22, 11, 82, 67, 9, 45, 91, 33, 52}; // 无序数组struct BSTree_node *mytree = NULL;mytree = create_bstree(arr, SIZE);  // 创建二叉树in_order(mytree); // 中序遍历printf("\n");//查找printf("please enter a number you want to find in the BSTree:\n");scanf("%d", &num);if(search_bstree(mytree, num))printf("find %d in the mytree.\n", num);elseprintf("can't find %d in the mytree.\n", num);   //插入printf("please enter a number you want to insert in the BSTree:\n");scanf("%d", &num);mytree = insert_bstree(mytree, num);in_order(mytree);printf("\n");return 0;
}// 创建二叉搜索树
struct BSTree_node *create_bstree(unsigned int *pt, int n)
{struct BSTree_node *tree = NULL;for(int i = 0; i < n; i++){tree = insert_bstree(tree, *pt);pt++;}return tree;
}
// 创建二叉搜索树插入节点
struct BSTree_node *insert_bstree(struct BSTree_node *T, unsigned int elem)
{if(!T){T = (struct BSTree_node *)malloc(sizeof(struct BSTree_node));T->elem = elem;T->ltree = T->rtree = NULL;}else if(elem < T->elem);{T->ltree = insert_bstree(T->ltree, elem); //递归}else if(elem > T->elem);{T->rtree = insert_bstree(T->rtree, elem); //递归}else{printf("inserting repeat node is fobidden.\n");exit(0);}return T;
}//中序遍历
void in_order(struct BSTree_node *tree)
{if(tree){in_order(tree->ltree);     //左printf("%d", tree->elem);  //中in_order(tree->rtree);     //右}
}//二叉搜索树查找
int search_bstree(struct BSTree_node *tree, unsigned int n)
{struct BSTree_node *p = tree; // 指针while(p){if(n == p->elem)return 1;else if(n < p->elem)p = p->ltree;elsep = p->rtree;   }return 0;
}

力扣题目

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null

示例 1:


输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:


输入：root = [4,2,7,1,3], val = 5
输出：[]

//c++
//递归1
class Solution {
public:                //1.返回值参数TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root; // 2.终止条件TreeNode* result = NULL; // 变量存放返回值if (root->val > val) result = searchBST(root->left, val);  // 3.单层搜索if (root->val < val) result = searchBST(root->right, val); // result 接住目标值指针return result;  // 没有搜索到result就是NULL}
};
//递归2
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root;if (root->val > val) return searchBST(root->left, val);if (root->val < val) return searchBST(root->right, val);return NULL;}
};//迭代法
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root != NULL) { // 当节点不为空if (root->val > val) root = root->left; // > 左子树遍历else if (root->val < val) root = root->right; // < 右子树遍历else return root; // 等于时返回该节点}return NULL; // 如果搜索不到}
};

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：


输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：


输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：


输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

//递归
class Solution {
private:TreeNode* parent;void traversal(TreeNode* cur, int val) { if (cur == NULL) {  //2.终止条件，找到插入位置（叶子节点）TreeNode* node = new TreeNode(val);if (val > parent->val) parent->right = node;else parent->left = node;return;}parent = cur;if (cur->val > val) traversal(cur->left, val);if (cur->val < val) traversal(cur->right, val);return;}public:TreeNode* insertIntoBST(TreeNode* root, int val) {1.确定递归参数，返回值parent = new TreeNode(0);if (root == NULL) {root = new TreeNode(val);}traversal(root, val);return root;}
};//迭代
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == NULL) {TreeNode* node = new TreeNode(val);return node;}TreeNode* cur = root;TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点while (cur != NULL) {parent = cur;if (cur->val > val) cur = cur->left;else cur = cur->right;}TreeNode* node = new TreeNode(val);if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值else parent->right = node;return root;}
};

  1. 删除二叉搜索树


#include <stdio.h>
#include <stdlib.h>
#define SIZE 10//二叉树节点
struct BSTree_node
{unsigned int elem;struct BSTree_node *ltree, *rtree;  // 左右子树
};struct BSTree_node *create_bstree(unsigned int *pt, int n);
struct BSTree_node *insert_bstree(struct BSTree_node *T, unsigned int elem);
void in_order(struct BSTree_node *tree);
int search_bstree(struct BSTree_node *tree, unsigned int n);
struct BSTree_node *delete_bstree(struct BSTree_node *T, unsigned int elem);int main(void)
{unsigned int num;unsigned int arr[SIZE] = {37, 22, 11, 82, 67, 9, 45, 91, 33, 52}; // 无序数组struct BSTree_node *mytree = NULL;mytree = create_bstree(arr, SIZE);  // 创建二叉树in_order(mytree); // 中序遍历printf("\n");
//查找printf("please enter a number you want to find in the BSTree:\n");scanf("%d", &num);if(search_bstree(mytree, num))printf("find %d in the mytree.\n", num);elseprintf("can't find %d in the mytree.\n", num);   
//插入printf("please enter a number you want to insert in the BSTree:\n");scanf("%d", &num);mytree = insert_bstree(mytree, num);in_order(mytree);printf("\n");//删除printf("please enter a number you want to delet from the BSTree:\n");scanf("%d", &num);mytree = delete_bstree(mytree, num);in_order(mytree);printf("\n");return 0;
}// 创建二叉搜索树
struct BSTree_node *create_bstree(unsigned int *pt, int n)
{struct BSTree_node *tree = NULL;for(int i = 0; i < n; i++){tree = insert_bstree(tree, *pt);pt++;}return tree;
}
// 创建二叉搜索树插入节点
struct BSTree_node *insert_bstree(struct BSTree_node *T, unsigned int elem)
{if(!T){T = (struct BSTree_node *)malloc(sizeof(struct BSTree_node));T->elem = elem;T->ltree = T->rtree = NULL;}else if(elem < T->elem);{T->ltree = insert_bstree(T->ltree, elem); //递归}else if(elem > T->elem);{T->rtree = insert_bstree(T->rtree, elem); //递归}else{printf("inserting repeat node is fobidden.\n");exit(0);}return T;
}//中序遍历
void in_order(struct BSTree_node *tree)
{if(tree){in_order(tree->ltree);     //左printf("%d", tree->elem);  //中in_order(tree->rtree);     //右}
}//二叉搜索树查找
int search_bstree(struct BSTree_node *tree, unsigned int n)
{struct BSTree_node *p = tree; // 指针while(p){if(n == p->elem)return 1;else if(n < p->elem)p = p->ltree;elsep = p->rtree;   }return 0;
}//删除 使用后继点代替删除节点
struct BSTree_node *delete_bstree(struct BSTree_node *T, unsigned int elem)
{  //递归//1.空if(T == NULL){printf("no exist %d node.\n", elem);exit(0);}//2.等于时if(T->elem == elem){     //2.1 没有右子树，直接删除该节点，T指向左子树if(T->rtree == NULL){struct BSTree_node *temp = T; T = T->ltree;free(temp);}else //2.2 有右子树，找右子树最左点{struct BSTree_node *temp = T->rtree; while(temp->ltree)  //找最左点temp = temp->ltree; T->elem = temp->elem;T->rtree = delete_bstree(T->rtree, T->elem); // 递归删除最左节点}}//3.大于或者小于时else if(T->elem > elem)T->ltree = delete_bstree(T->ltree, elem);elseT->rtree = delete_bstree(T->rtree, elem);return T;
}

力扣题目

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：


首先找到需要删除的节点；
如果找到了，删除它。

示例 1:


输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:


输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:


输入: root = [], key = 0
输出: []

确定单层递归的逻辑

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了

  • 找到删除的节点

  • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点

  • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点

  • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点

  • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。


//递归
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了if (root->val == key) {// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点if (root->left == nullptr && root->right == nullptr) {///! 内存释放delete root;return nullptr;}// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点else if (root->left == nullptr) {auto retNode = root->right;///! 内存释放delete root;return retNode;}// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点else if (root->right == nullptr) {auto retNode = root->left;///! 内存释放delete root;return retNode;}// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else {TreeNode* cur = root->right; // 找右子树最左面的节点while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置TreeNode* tmp = root;   // 把root节点保存一下，下面来删除root = root->right;     // 返回旧root的右孩子作为新rootdelete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};//迭代
class Solution {
private:// 将目标节点（删除节点）的左子树放到 目标节点的右子树的最左面节点的左孩子位置上// 并返回目标节点右孩子为新的根节点// 是动画里模拟的过程TreeNode* deleteOneNode(TreeNode* target) {if (target == nullptr) return target;if (target->right == nullptr) return target->left;TreeNode* cur = target->right;while (cur->left) {cur = cur->left;}cur->left = target->left;return target->right;}
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;TreeNode* cur = root;TreeNode* pre = nullptr; // 记录cur的父节点，用来删除curwhile (cur) {if (cur->val == key) break;pre = cur;if (cur->val > key) cur = cur->left;else cur = cur->right;}if (pre == nullptr) { // 如果搜索树只有头结点return deleteOneNode(cur);}// pre 要知道是删左孩子还是右孩子if (pre->left && pre->left->val == key) {pre->left = deleteOneNode(cur);}if (pre->right && pre->right->val == key) {pre->right = deleteOneNode(cur);}return root;}
};

530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：


输入：root = [4,2,6,1,3]
输出：1

示例 2：


输入：root = [1,0,48,null,null,12,49]
输出：1

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：


结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：


输入：root = [1,null,2,2]
输出：[2]

示例 2：


输入：root = [0]
输出：[0]

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：


输入：root = [1,2], p = 1, q = 2
输出：1

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:


输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:


输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点1 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
http://www.mmbaike.com/news/72212.html

相关文章：

  • 最专业的网站制作公司网站策划书
  • 图书馆评估定级关于网站建设标准知识搜索引擎
  • 扁平化网站后台产品网络营销策划
  • wordpress如何通过后台增加主菜单快速整站排名seo教程
  • 东莞建网站的公司推广神器
  • 精品课网站怎么做seo从0到1怎么做
  • 做logo用什么网站seo排名哪家有名
  • 鸿鹄网站建设福州seo代理计费
  • 网站广告赚钱怎么做网站发布
  • 礼品公司网站制作网络推广整合平台
  • 陕西城乡建设学校网站是真吗2022年列入传销组织最新骗法
  • 怎么做健康咨询网站seo谷歌外贸推广
  • 网站建设案例收费情况小程序商城
  • 旅游网站建设色彩搭配表写软文能赚钱吗
  • 在百度上做公司做网站2024年瘟疫大爆发
  • 天津网站建设技术网络营销 长沙
  • 微信小程序是免费的吗seo外链推广
  • 给赌博人做网站厦门关键词排名提升
  • 怎么查看网站啥系统做的上海seo推广整站
  • 建立网站目录的时候万网域名管理平台
  • 桂林漓江旅游攻略长沙官网网站推广优化
  • 网站被攻击打不开怎么办武汉seo公司出 名
  • 河南郑州做网站东莞关键词优化软件
  • 服装商店的网站建设要求小程序推广运营的公司
  • 网站分类代码网站建设 网站制作
  • 网站建设南京学seo需要多久
  • 慈溪网站开发seo外包公司
  • 区块链开发前景seo报价单
  • 宁德做网站网络营销推广
  • 网站by wordpress自动点击器安卓