从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题(上)

简介: 从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题

此篇算是用C++讲高阶数据结构第一篇,在C++完结之前高阶数据结构内容都放在④⑤两个专栏,等后面C++完结还会学图和算法的内容。

先讲二叉搜索树是因为讲解 map 和 set 的特性需要二叉搜索树做铺垫,理解搜索二叉树有助于更好地理解 map 和 set 的特性。第二个原因是为了后期讲解查找效率极高的平衡搜索二叉树,随后再讲完红黑树,我们就可以模拟实现 map 和 set 了。

1. 二叉搜索树(BinarySearchTree)

概念:搜索二叉树(二叉搜索树)又称为二叉排序树,它或者是一颗空树,

或者是具有以下性质的二叉树:

  • 若其左子树不是空,则左子树上所有节点的值都小于根结点的值
  • 若其右子树不是空,则右子树上所有结点的值都大于根结点的值
  • 其左右子树必须都是二叉搜索树

至于叫它 "搜索二叉树",还是 "二叉搜索树",都是可以的,就是叫搜索二叉树的英文缩写不太好。

结论:任意一个子树都需要满足,左子树的值 < 根 < 右子树的值,才能构成二叉搜索树。


1.1 二叉搜索树的优势和劣势

既然叫搜索二叉树,它肯定是用来搜索的,当满足搜索二叉树时你将可以快速地查找任意的值。

举个例子: 查找7

放到以前我们如果不用二分查找,可能会选择用暴力的方式去从头到尾遍历一遍。


但现在学了搜索二叉树,我们就可以轻松找到这个7了,7 比 8(根节点) 小,

根据搜索二叉树的性质,它必然不会出现在右子树 (右边大) ...

搜索二叉树查找一个值的最坏情况,也只是查找高度次。

二叉搜索树的时间复杂度:O(N)

上面的例子会让人误以为搜索二叉树的增删查改的时间复杂度是O(logN),

但实际上是O(N),因为这棵树是有可能会 蜕化 的,极端情况下会蜕化成一个 "单边树"

比如按有序插入:


最差情况:二叉搜索树退化为单边树(或类似单边),其平均比较次数为:O(N)

最优情况:二叉搜索树为完全二叉树(或接近完全二叉树),其平均比较次数为:O(logN)

对于时间复杂度的分析我们要做一个悲观主义者,根据最差情况去定时间复杂度:O(N)


1.2 二叉搜索树的改良

如果搜索二叉树退化成了单边树,其性能也就失去了,能否进行改进让它保持性能?

如何做到不论按照上面次序插入关键码,二叉搜索树的性能均能达到最优?

搜索二叉树由于控制不了极端情况,与 O(logN)失之交臂,但平衡二叉搜索树做到了。

严格意义上来说满二叉树才是O(logN),完全二叉树是接近O(logN)。

而平衡搜索二叉树维持左右两边均匀程度,让它接近完全二叉树,从而让效率趋近O(logN)。

后面我们学的各种树(AV树,红黑树)可以说都是二叉搜索树的改良。


2. 二叉搜索树的实现

2.1 二叉搜索树的定义

此时我们的BinarySearchTree就缩写成BSTree了。

这里我们用模板,模板参数我们给了一个K,表示 key 的意思(模板参数并非一定要用 T)。

template<class K>
class BSTreeNode
{
public:
  BSTreeNode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {}
 
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};

下面我们来定义整个树,BSTreeNode 有些长了,这里将其 typedef 成 Node 。

构造函数都没必要写,它自己生成的就够用了:

template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
 
protected:
  Node* _root = nullptr;
};

2.2 二叉搜索树的插入

二叉搜索树的插入是会“去重”的。

我们先来实现最简单的插入操作:

  • 如果树为空,则直接新增结点,赋值给 root 指针。
  • 如果树不为空,按二叉搜索树性质查找插入位置,插入新节点。

Insert 的实现我们可以用递归,也可以用非递归,这一块递归比非递归更难理解。

秉着先难后易的态度,我们先讲比较难理解的非递归版本

Step1:首先检查是否有根结点 _root,如果没有我们就 new 一个结点出来作为根结点。此时插入成功,返回 true。

Step2:插入就需要找到插入位置,我们定义一个 cur 变量,从根节点开始,
根据搜索二叉树 性质,将 cur 结点的值与插入的值  进行大小比较。

如果插入的值大于当前结点值,则将 cur 结点向右移动 cur=cur->_right ;

如果插入的值小于当前节点值,就将 cur 结点向左移动 cur=cur->_left。

值得注意的是,还需要额外记录一下 cur 的父结点,

因为你不知道什么时候会碰到nullptr结束。

并且当我们找到插入位置后,仅仅 new 上一个新结点给 cur 是完成不了插入操作的。

因为直接这么做 cur 也只是一个局部变量而已,需要 cur 跟上一层(cur 的父亲)相链接才行。

为了能找到上一层,所以我们还需要额外定义一个 prev 变量来记录 cur 的父结点,

在我们更换 cur 结点时记录父结点的位置 prev=cur 即可。

当然了,还有一种插入失败的情况,就是判断大小时出现等于的情况,返回 false 即可。

(重复的值是不允许插入的,默认情况是不允许冗余的!但是也有针对这个的变形,后续再说)

Step3:插入。new 一个新结点给 cur,此时 cur 只是一个局部变量,必须要和父亲链接,

此时应该链接父亲的左边,还是链接父亲的右边?我们不知道,所以我们需要再做一个比较:

如果父节点的值大于插入的值,则将 cur 链接到父亲左边 prev->_left=cur;

反之将 cur 链接到父亲右边  prev->_right=cur。

最后,插入成功返回 true。

insert 代码:

  bool Insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
 
    Node* prev = nullptr;
    Node* cur = _root;
    while (cur != nullptr) // 找到要插入的位置
    {
      if (key < cur->_key) // 要插入的值比当前值小
      {
        prev = cur; // 记录cur,等下cur更新就是cur的父亲
        cur = cur->_left; // 到左边插入
      }
      else if (key > cur->_key)
      {
        prev = cur;
        cur = cur->_right;
      }
      else
      {
        return false; // 相等,插入失败
      }
    }
 
    cur = new Node(key); // 走到这,cur就是要插入的位置
    if (key < prev->_key) // 如果key比cur的父亲小
    {
      prev->_left = cur; // 插入到父亲的左孩子
    }
    else
    {
      prev->_right = cur;
    }
    return true;
  }

再写一个中序遍历来测试一下插入的效果:

  void InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    InOrder(root->_left);
    cout << root->_key << " ";
    InOrder(root->_right);
  }

模拟出一个测试用例:

void TestBSTree1() 
{
  BSTree<int> t;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  for (const auto& e : a) 
  {
    t.Insert(e);
  }
  t.InOrder();  // 没法传根
}

此时会出现一个问题,因为根是私有的,我们没办法把根传过去。

此时我们可以选择在类内部写一个成员函数 GetRoot 去取根,但是这里我们可以选择这么做:

干脆将刚才我们实现的中序设为 protected 保护,然后再写一个 InOrder 放在公有的区域。

这就是在类内访问 _root 了,没有什么问题。

如此一来我们在类外就可以直接调用 InOrder,并且也不需要传递参数了。

BinarySearchTree.h:

#pragma once
 
#include <iostream>
using namespace std;
 
template<class K>
class BSTreeNode
{
public:
  BSTreeNode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {}
 
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};
 
template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
 
public:
  bool Insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
 
    Node* prev = nullptr;
    Node* cur = _root;
    while (cur != nullptr) // 找到要插入的位置
    {
      if (key < cur->_key) // 要插入的值比当前值小
      {
        prev = cur; // 记录cur,等下cur更新就是cur的父亲
        cur = cur->_left; // 到左边插入
      }
      else if (key > cur->_key)
      {
        prev = cur;
        cur = cur->_right;
      }
      else
      {
        return false; // 相等,插入失败
      }
    }
 
    cur = new Node(key); // 走到这,cur就是要插入的位置
    if (key < prev->_key) // 如果key比cur的父亲小
    {
      prev->_left = cur; // 插入到父亲的左孩子
    }
    else
    {
      prev->_right = cur;
    }
    return true;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
protected:
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
 
  Node* _root = nullptr;
};

Test.c:

#include "BinarySearchTree.h"
 
void TestBSTree1() 
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.Insert(e);
  }
  t.InOrder();
}
 
int main()
{
  TestBSTree1();
 
  return 0;
}


2.3 二叉搜索树的查找

二叉搜索树的查找 Find 实现很容易,用和刚才一样的思路,从根结点开始查找。

从根开始,如果要查找的值大于 cur 目前的值,则让 cur 往右走,反之往左走。

当查找得值与 cur 的值相等时则说明找到了,返回 true。

当 cur 触及到空(while 循环结束)则说明找不到,返回 false。

代码:

  bool Find(const K& key)
  {
    Node* cur = _root;
    while (cur != nullptr)
    {
      if (key < cur->_key)
      {
        cur = cur->_left;
      }
      else if (key > cur->_key)
      {
        cur = cur->_right;
      }
      else
      {
        return true;
      }
    }
    return false;
  }

从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题(中):https://developer.aliyun.com/article/1521942?spm=a2c6h.13148508.setting.21.50c04f0eHmAr4x

目录
相关文章
|
1月前
|
安全 编译器 C语言
C++入门1——从C语言到C++的过渡
C++入门1——从C语言到C++的过渡
52 2
|
1月前
|
存储 搜索推荐 C语言
深入C语言指针,使代码更加灵活(二)
深入C语言指针,使代码更加灵活(二)
|
1月前
|
存储 程序员 编译器
深入C语言指针,使代码更加灵活(一)
深入C语言指针,使代码更加灵活(一)
|
1月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中,`static`关键字主要用于变量声明,使得该变量的作用域被限制在其被声明的函数内部,且在整个程序运行期间保留其值。而在C++中,除了继承了C的特性外,`static`还可以用于类成员,使该成员被所有类实例共享,同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景,不仅限于控制变量的作用域和生存期。
53 10
|
1月前
|
C语言
深入C语言指针,使代码更加灵活(三)
深入C语言指针,使代码更加灵活(三)
深入C语言指针,使代码更加灵活(三)
|
2月前
|
安全 C语言
在C语言中,正确使用运算符能提升代码的可读性和效率
在C语言中,运算符的使用需要注意优先级、结合性、自增自减的形式、逻辑运算的短路特性、位运算的类型、条件运算的可读性、类型转换以及使用括号来明确运算顺序。掌握这些注意事项可以帮助编写出更安全和高效的代码。
49 4
|
2月前
|
算法 机器人 C语言
ROS仿真支持C++和C语言
ROS仿真支持C++和C语言
68 1
|
1月前
|
C语言
C语言练习题代码
C语言练习题代码
|
1月前
|
C语言 C++
实现两个变量值的互换[C语言和C++的区别]
实现两个变量值的互换[C语言和C++的区别]
19 0
|
1月前
|
程序员 C++ 开发者
C++入门教程:掌握函数重载、引用与内联函数的概念
通过上述介绍和实例,我们可以看到,函数重载提供了多态性;引用提高了函数调用的效率和便捷性;内联函数则在保证代码清晰的同时,提高了程序的运行效率。掌握这些概念,对于初学者来说是非常重要的,它们是提升C++编程技能的基石。
21 0