【模板】【BST树】BST删除操作
2021/10/4 23:41:49
本文主要是介绍【模板】【BST树】BST删除操作,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉搜索树(Binary Search Tree):左子树上的值都小于根结点,右子树上的值都大于根结点,其层序遍历即为有序序列。
#include<iostream> #include<algorithm> #include<vector> #include<cstdlib> using namespace std; typedef struct BST { int data; BST* lchild, * rchild; }BSTNode,*BSTree; bool BST_Insert(BSTree& T, int data) { if (T == NULL) { T = new BSTNode; T->data = data; T->lchild = T->rchild = NULL; return true; } else if (data < T->data) { return BST_Insert(T->lchild, data); } else if (data > T->data) { return BST_Insert(T->rchild, data); } else // 已存在值不插入 return false; } bool BST_Dele(BSTree& T, int data) { if (T == NULL) return false; if (T->data == data) { BSTree p, q; // 前驱 后继 //如果左右儿子都有比较难删除 if (T->lchild && T->rchild) { p = T; q = p->lchild; while (q->rchild) // 寻找左子树最大 { p = q; q = q->rchild; } if (p != T) { p->rchild = q->lchild; } else { p->lchild = q->lchild; } free(q); } else if (T->lchild) { //只有左儿子 p = T; T = T->lchild; free(p); } else //只有右儿子或左右儿子都没有(叶子) { p = T; T = T->rchild; free(p); } return true; } else if (data < T->data) { return BST_Dele(T->lchild, data); } else if (data > T->data) { return BST_Dele(T->rchild, data); } } //BST 前序遍历 void Prior_Order(BSTree& T) { if (T != NULL) { cout << T->data; Prior_Order(T->lchild); Prior_Order(T->rchild); } } //BST 中序遍历 void Mid_Order(BSTree& T) { if (T != NULL) { Mid_Order(T->lchild); cout << T->data; Mid_Order(T->rchild); } } //BST 后序遍历 void Post_Order(BSTree& T) { if (T != NULL) { Post_Order(T->lchild); Post_Order(T->rchild); cout << T->data; } } int main() { ios::sync_with_stdio(false); BSTree T = NULL; for (int i = 0; i < 10; i++) { BST_Insert(T, i); } Prior_Order(T); return 0; }
这篇关于【模板】【BST树】BST删除操作的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南