1. Toy模板网首页
  2. > Toy博客

数据结构10 -查找_树表查找

9月前 作者：I'mFAN 分类：Toy博客 阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构10 -查找_树表查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

  1. 创建二叉搜索树

二叉搜索树

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

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

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

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

下面这两棵树都是搜索树

数据结构10 -查找_树表查找,数据结构,数据结构

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：

数据结构10 -查找_树表查找,数据结构,数据结构 

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

示例 2：

数据结构10 -查找_树表查找,数据结构,数据结构 

输入：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);
       else
                printf("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;
            else
                  p = p->rtree;   
      }
      return 0;
}

力扣题目

700. 二叉搜索树中的搜索

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

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

示例 1:

数据结构10 -查找_树表查找,数据结构,数据结构 

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

示例 2:

数据结构10 -查找_树表查找,数据结构,数据结构 

输入：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：

数据结构10 -查找_树表查找,数据结构,数据结构 

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
数据结构10 -查找_树表查找,数据结构,数据结构

示例 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);
       else
                printf("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;
            else
                  p = 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);
       else
            T->rtree = delete_bstree(T->rtree, elem);
       
       return T;
}

力扣题目

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

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

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


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

示例 1:

数据结构10 -查找_树表查找,数据结构,数据结构 

输入：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]。
数据结构10 -查找_树表查找,数据结构,数据结构

示例 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的右孩子作为新root
                delete 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的父节点，用来删除cur
        while (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：

数据结构10 -查找_树表查找,数据结构,数据结构 

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

示例 2：

数据结构10 -查找_树表查找,数据结构,数据结构 

输入：root = [1,0,48,null,null,12,49]
输出：1
501. 二叉搜索树中的众数

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

假定 BST 满足如下定义：


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

示例 1：

数据结构10 -查找_树表查找,数据结构,数据结构 

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

示例 2：


输入：root = [0]
输出：[0]
236. 二叉树的最近公共祖先

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

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

示例 1：

数据结构10 -查找_树表查找,数据结构,数据结构 

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

示例 2：

数据结构10 -查找_树表查找,数据结构,数据结构 

输入：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]

数据结构10 -查找_树表查找,数据结构,数据结构

示例 1:


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

示例 2:文章来源地址https://www.toymoban.com/news/detail-633938.html


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

到了这里，关于数据结构10 -查找_树表查找的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-查找（顺序查找与二分查找的讲解与代码实现）

    数据结构-查找（顺序查找与二分查找的讲解与代码实现）

    顺序查找概念：从表的另一端开始，一次将记录的和给定值进行比较，若某个记录的和给定的值相等，则查找成功，反之则查找失败。 ASL:平均查找长度 pi查找概率，ci查找次数 eg：序列1，2，3 查找1的次数为1概率为1/3，2为两次概率1/3，3的次数为3概率1/3  将12

    2024年02月06日
    浏览(68)
  • 折半查找实验 （数据结构）

    折半查找实验 （数据结构）

    一、实验目的 掌握折半查找算法的基本思想 掌握折半查找算法的实现方法 掌握折半查找的时间性能 掌握折半查找类的定义和使用 二、实验要求 熟悉C++语言编程 了解折半查找的原理 了解折半查找类的定义、应用 三、实验内容 1、问题描述 在一个有序序列中，折半查找一个

    2024年02月08日
    浏览(85)
  • 【数据结构】查找（一）

    【数据结构】查找（一）

    因为时间关系（现阶段来不及），先不学红黑树和B树，所以这是查找（一）。 先写一下二分查找，数据结构数上叫的“折半查找”。 下面依旧是对王道书上选择题的一个简单纠错（摸鱼），希望6.10能写完查找部分，6.11写完排序部分 1.（B） 对于顺序查找，每个元素查找成功

    2024年02月09日
    浏览(12)
  • 数据结构【查找】

    数据结构【查找】

    提前了解： 1、： 若能唯一标识一个数据元素，则称为主；若能标识若干个数据元素的称为次； 2、查找（检索）：顾名思义，给定一个值，进行查找；若存在值则查找成功，反之查找失败； 3、查找方法评价指标：其中pᵢ为查找第i个

    2024年02月15日
    浏览(27)
  • 数据结构-查找1

    数据结构-查找1

    1.对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（   ）。 A．(n-1)/2       B． n/2        C．(n+1)/2        D．n  答案：C 解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。 2.适用于折半查找的表的存储方式及元素排列要求为（

    2024年02月03日
    浏览(37)
  • 数据结构-查找2(详解)

    数据结构-查找2(详解)

    1 .在一棵由包含 4、5、6 等等一系列整数结点构成的二叉搜索树中，如果结点 4 和 6 在树的同一层，那么可以断定结点 5 一定是结点 4 和 6 的父亲结点。  错    解析：         反例  2.二叉搜索树的查找和折半查找的时间复杂度相同。 错   解析：不一定相同。二叉排序树

    2024年02月02日
    浏览(36)

  • 数据结构——查找

    目录 1.查找的基本概念 1.1基本概念 ​编辑1.2对查找表的常见操作 以此分为静态查找表和动态查找表：​编辑1.3查找算法的评价指标 2.顺序查找 2.1算法思想 2.2算法实现 2.2.1顺序表查找的实现 2.2.2顺序表查找的实现（哨兵） 2.3顺序查找效率及算法优化 3.折半查找⭐ 3.1算法思想

    2024年02月06日
    浏览(17)
  • 数据结构之查找详解

    数据结构之查找详解

    1.1 定义 查找表是由同一类型的数据元素构成的集合。 例如电话号码簿和字典都可以看作是一张查找表。 1.2 查找表的几种操作： 1）在查找表中查找某个具体的数据元素； 2）在查找表中插入数据元素； 3）从查找表中删除数据元素； 1.3 静态查找表和动态查找表 在查找表中

    2024年01月16日
    浏览(32)
  • 数据结构_查找

    数据结构_查找

    目录 1. 查找的基本概念 2. 顺序查找和折半查找 2.1 顺序查找 2.1.1 一般线性表的顺序查找 2.1.2 有序表的顺序查找 2.2 折半查找 2.3 分块查找 2.4 相关练习 3. 树型查找         3.1 二叉排序树 3.1.1 二叉排序树的定义 3.1.2 二叉排序树的查找 3.1.3 二叉排序树的插入 3.1.4 二叉排序

    2024年02月04日
    浏览(25)
  • 数据结构习题9---查找

    数据结构习题9---查找

    一、填空题 1 .   在数据的存放无规律而言的线性表中进行检索的最佳方法是    顺序查找（线性查找）    。 2 . 线性有序表（ a 1 ， a 2 ， a 3 ，…， a 256 ) 是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索   

    2024年02月09日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包