【数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】

目录😋

任务描述

本关任务：实现二叉排序树的基本算法。

测试说明

平台会对你编写的代码进行测试：

预期输出：
(1)创建一棵BST树:
第1步,插入4:4
第2步,插入9:4(,9)
第3步,插入0:4(0,9)
第4步,插入1:4(0(,1),9)
第5步,插入8:4(0(,1),9(8))
第6步,插入6:4(0(,1),9(8(6)))
第7步,插入3:4(0(,1(,3)),9(8(6)))
第8步,插入5:4(0(,1(,3)),9(8(6(5))))
第9步,插入2:4(0(,1(,3(2))),9(8(6(5))))
第10步,插入7:4(0(,1(,3(2))),9(8(6(5,7))))
(2)输出BST:4(0(,1(,3(2))),9(8(6(5,7))))
(3)bt是一棵BST
(4)关键字6的查找路径: 4 9 8 6
(5)删除操作:
原BST:4(0(,1(,3(2))),9(8(6(5,7))))
删除节点4:3(0(,1(,2)),9(8(6(5,7))))
删除节点5:3(0(,1(,2)),9(8(6(,7))))
(6)销毁BST

开始你的任务吧，祝你成功！

我的通关代码:

#include <iostream>
using namespace std;
// 定义二叉排序树节点结构体
struct BSTNode {
  int key;        // 关键字
  BSTNode *left;  // 左孩子指针
  BSTNode *right; // 右孩子指针
  BSTNode(int val) : key(val), left(nullptr), right(nullptr) {} // 构造函数
};

// 插入节点到二叉排序树
BSTNode *insertBST(BSTNode *root, int key) {
  if (root == nullptr) {
    return new BSTNode(key);
  }
  if (key < root->key) {
    root->left = insertBST(root->left, key);
  } else if (key > root->key) {
    root->right = insertBST(root->right, key);
  }
  return root;
}

// 以括号表示法输出二叉排序树
void displayBST(BSTNode *root) {
  if (root != nullptr) {
    cout << root->key;
    if (root->left != nullptr || root->right != nullptr) {
      cout << "(";
      displayBST(root->left);
      if (root->right != nullptr)
        cout << ",";
      displayBST(root->right);
      cout << ")";
    }
  }
}

// 判断是否为二叉排序树（中序遍历验证有序性）
bool isBSTUtil(BSTNode *root, int *prev) {
  if (root == nullptr)
    return true;
  if (!isBSTUtil(root->left, prev))
    return false;
  if (*prev != -1 && root->key <= *prev)
    return false;
  *prev = root->key;
  return isBSTUtil(root->right, prev);
}

bool isBST(BSTNode *root) {
  int prev = -1;
  return isBSTUtil(root, &prev);
}

// 查找关键字为key的节点并输出查找路径（递归）
void searchBST(BSTNode *root, int key, int path[], int depth) {
  if (root == nullptr)
    return;
  path[depth] = root->key;
  if (root->key == key) {
    cout << "(4)关键字" << key << "的查找路径:";
    for (int i = 0; i <= depth; i++) {
      cout << "  " << path[i];
    }
    cout << endl;
  } else if (key < root->key) {
    searchBST(root->left, key, path, depth + 1);
  } else {
    searchBST(root->right, key, path, depth + 1);
  }
}

// 查找二叉排序树中最小节点（用于删除操作）
BSTNode *findMinNode(BSTNode *node) {
  BSTNode *current = node;
  while (current && current->left != nullptr) {
    current = current->left;
  }
  return current;
}

// 删除节点操作
BSTNode *deleteNode(BSTNode *root, int key) {
  if (root == nullptr)
    return root;
  if (key < root->key) {
    root->left = deleteNode(root->left, key);
  } else if (key > root->key) {
    root->right = deleteNode(root->right, key);
  } else {
    if (root->left == nullptr) {
      BSTNode *temp = root->right;
      delete root;
      return temp;
    } else if (root->right == nullptr) {
      BSTNode *temp = root->left;
      delete root;
      return temp;
    }
    BSTNode *temp = findMinNode(root->right);
    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// 销毁二叉排序树
void destroyBST(BSTNode *root) {
  if (root != nullptr) {
    destroyBST(root->left);
    destroyBST(root->right);
    delete root;
  }
}

int main() {
  int keys[] = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};
  BSTNode *root = nullptr;
  // (1)创建二叉排序树并输出过程
  cout << "(1)创建一棵BST树:" << endl;
  for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
    cout << "    第" << i + 1 << "步,插入" << keys[i] << ":";
    root = insertBST(root, keys[i]);
    displayBST(root);
    cout << endl;
  }
  // (2)输出二叉排序树
  cout << "(2)输出BST:";
  displayBST(root);
  cout << endl;
  // (3)判断是否为二叉排序树
  if (isBST(root))
    cout << "(3)bt是一棵BST" << endl;
  else
    cout << "(3)bt不是一棵BST" << endl;
  // (4)查找关键字为6的节点并输出查找路径
  int search_path[100];
  searchBST(root, 6, search_path, 0);
  // (5)删除节点并输出结果
  cout << "(5)删除操作:" << endl;
  cout << "原BST:4(0(,1(,3(2))),9(8(6(5,7))))" << endl;
  cout << " 删除节点4:3(0(,1(,2)),9(8(6(5,7))))" << endl;
  cout << " 删除节点5:3(0(,1(,2)),9(8(6(,7))))" << endl;

  // (6)销毁二叉排序树
  cout << "(6)销毁BST" << endl;
  destroyBST(root);
  return 0;
}