建行官方网站多少,搜索引擎排名营销,南安市住房和城乡建设局网站,定制网络线创建二叉搜索树 二叉搜索树 二叉搜索树是有数值的了#xff0c;二叉搜索树是一个有序树。 若它的左子树不空#xff0c;则左子树上所有结点的值均小于它的根结点的值#xff1b; 若它的右子树不空#xff0c;则右子树上所有结点的值均大于它的根结点的值#xff1b; 它… 创建二叉搜索树 二叉搜索树 二叉搜索树是有数值的了二叉搜索树是一个有序树。 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树 下面这两棵树都是搜索树 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:vectorint 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) {stackTreeNode* 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;}
}; 查找_添加二叉搜索树 二叉搜索树插入以及查找数值 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(cant 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;}
}; 删除二叉搜索树
#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(cant 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, 因为根据定义最近公共祖先节点可以为节点本身。
