城阳网站制作,html静态网页作业,制作网站需要什么知识,摄影网站cnu视觉联盟目录#x1f60b;
任务描述
相关知识
测试说明
我的通关代码:
测试结果#xff1a;
任务描述 本关任务#xff1a;实现二叉排序树的基本算法。 相关知识 为了完成本关任务#xff0c;你需要掌握#xff1a;二叉树的创建、查找和删除算法。具体如下#xff1a; (1)由…目录
任务描述
相关知识
测试说明
我的通关代码:
测试结果
任务描述 本关任务实现二叉排序树的基本算法。 相关知识 为了完成本关任务你需要掌握二叉树的创建、查找和删除算法。具体如下 (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键字为4和5的结点,并输出删除后的二叉排序树。 测试说明 平台会对你编写的代码进行测试 预期输出 (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;elsecout (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;
}测试结果
