xerolyskinner/MicrochipFor32
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
MicrochipFor32/STL_Device/STL_BST.cpp

291 lines
8.0 KiB
C++
Raw Permalink Normal View History

换血大更新
2023-03-06 12:44:58 +08:00
/*----------------------------------------------------------------------------------------------------
#
# Copyright (c) 2022 Yuankang Liang(XerolySkinner)
#
# <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԭ<EFBFBD><D4AD><EFBFBD>ṩ,<2C><><EFBFBD>κ<EFBFBD><CEBA><EFBFBD>ʾ<EFBFBD><CABE><EFBFBD><EFBFBD>ʾ
# <09><><EFBFBD>κ<EFBFBD><CEBA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>,<2C><><EFBFBD>߶<EFBFBD><DFB6><EFBFBD><EFBFBD>е<EFBFBD><D0B5>κ<EFBFBD><CEBA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>⳥<EFBFBD><E2B3A5><EFBFBD><EFBFBD>
#
# ʹ<>õ<EFBFBD><C3B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>:
# 1. <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Դ,<2C>㲻<EFBFBD><E3B2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>д<EFBFBD><D0B4>ԭʼ<D4AD><CABC><EFBFBD><EFBFBD>.
# 2. <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>κ<EFBFBD>Ŀ<EFBFBD><C4BF>,ǰ<><C7B0><EFBFBD>ǰ<EFBFBD>Ȩ<EFBFBD><C8A8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>и<EFBFBD><D0B8><EFBFBD><EFBFBD><EFBFBD>.
# <09><><EFBFBD>Ұ<EFBFBD>Ȩ<EFBFBD><C8A8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͬʱ<CDAC><CAB1><EFBFBD><EFBFBD>.
# 3. <09><><EFBFBD><EFBFBD>ʹ<EFBFBD><CAB9>,<2C><><EFBFBD><EFBFBD>,<2C>޸<EFBFBD>,<2C>ַ<EFBFBD>,<2C><><EFBFBD><EFBFBD><EFBFBD>۱<EFBFBD><DBB1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>.
# 4. <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڲ<EFBFBD>Ʒ<EFBFBD><C6B7>ʹ<EFBFBD><CAB9>,<2C><>Ʒ<EFBFBD>ĵ<EFBFBD><C4B5>е<EFBFBD><D0B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>͵ĵ<CDB5><C4B5><EFBFBD><EFBFBD>DZ<EFBFBD><C7B1><EFBFBD><EFBFBD><EFBFBD>.
# 5. <09><>֪ͨ<CDA8><D6AA><EFBFBD>ô<EFBFBD><C3B4>κ<EFBFBD><CEBA><EFBFBD>Դɾ<D4B4><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>.
#
# Yuankang Liang(XerolySkinner)
# E-mail:zabbcccbbaz@163.com
# QQ:2715099320
# Mobile Phone:13005636215
#
# All rights reserved.
*/
/**
* @file STL_BST.h
* @brief ʵ<EFBFBD>ֶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
* @mainpage <EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD>Ϣ
* @author Yuankang Liang(XerolySkinner)
* @email zabbcccbbaz@163.com
* @version V1.0.0
* @date 2022-12-09 20:30
*/
#include "STL_BST.h"
//////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------
// <09>ຯ<EFBFBD><E0BAAF>
/**
* @brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ա
* @param num <EFBFBD><EFBFBD>Աֵ
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::Insert(u32 num) {
STL_BST_Node* now=root;
STL_BST_Node* new_Node= make(num);
u32 count = 1;
if (new_Node == NULL)return BST_NULL;
// <09><><EFBFBD><EFBFBD>
if (root == NULL) {
depth = 0;
root = new_Node;
return BST_OK;}
// <09>ǿ<EFBFBD><C7BF><EFBFBD>
while (1) {
// <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>֫
if (now->val > num) {
if (now->Lkid == NULL) { // <09><>֫Ϊ<D6AB><CEAA>,ֱ<><D6B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
Llink(now, new_Node);
break;}
else { // <09><>֫<EFBFBD>ǿ<EFBFBD>,<2C><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
++count; // <09>߶<EFBFBD><DFB6><EFBFBD><EFBFBD><EFBFBD>
now = now->Lkid;} // <09><>һ<EFBFBD><D2BB>
}
// <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>֫
else {
if (now->Rkid == NULL) { // <09><>֫Ϊ<D6AB><CEAA>,ֱ<><D6B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
Rlink(now, new_Node);
break;}
else{ // <09><>֫<EFBFBD>ǿ<EFBFBD>,<2C><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
++count; // <09>߶<EFBFBD><DFB6><EFBFBD><EFBFBD><EFBFBD>
now = now->Rkid;} // <09><>һ<EFBFBD><D2BB>
}
}
new_Node->heigh = count; // <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
if (depth < count)depth = count; // <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
return BST_OK;}
//----------------------------------------------------------------------------------------------------
/**
* @brief Ѱ<EFBFBD>ҳ<EFBFBD>Ա
* @param num Ѱ<EFBFBD>ҳ<EFBFBD>Աֵ
* @return <EFBFBD>ҵ<EFBFBD><EFBFBD>Ľڵ<EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD>
*/
STL_BST_Node* STL_BST::Find(u32 num) {
STL_BST_Node* now = root;
// <09><><EFBFBD><EFBFBD>
if (root == NULL)return NULL; // <09>Ҳ<EFBFBD><D2B2><EFBFBD>Ԫ<EFBFBD><D4AA>
// <09>ǿ<EFBFBD><C7BF><EFBFBD>
while (1) {
if (now->val == num)
return now;
else if (now->val > num) {
if (now->Lkid == NULL) // <09><>֫Ϊ<D6AB><CEAA>,<2C><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD>
return NULL;
else
now = now->Lkid;}
else {
if (now->Rkid == NULL) // <09><>֫Ϊ<D6AB><CEAA>,<2C><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD>
return NULL;
else
now = now->Rkid;}
}
return now;}
//----------------------------------------------------------------------------------------------------
/**
* @brief ɾ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ա
* @param num ɾ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Աֵ
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::Remove(u32 num) {
STL_BST_Node* now = Find(num);
STL_BST_Node* Lmax = NULL;
if (now == NULL)return BST_NULL;
// <09><><EFBFBD>Ӵ<EFBFBD>
if (now->Lkid == NULL && now->Rkid == NULL) {
if (tsRL(now)==BST_NULL) {
// <09><><EFBFBD>ڵ<EFBFBD>
root = NULL;
depth = 0;
free(now);}
else if (tsRL(now) == BST_L) {
// <09><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
Llink(now->Father, NULL);
free(now);
}
else if (tsRL(now) == BST_R) {
// <09><><EFBFBD>ҽڵ<D2BD>
Rlink(now->Father, NULL);
free(now);}
}
// <09><><EFBFBD><EFBFBD>
else if (now->Lkid != NULL && now->Rkid == NULL) {
if (tsRL(now) == BST_NULL) {
// <09><><EFBFBD>ڵ<EFBFBD>
root = root->Lkid;
--depth;
free(now);}
else if (tsRL(now) == BST_L) {
// <09><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
Llink(now->Father, now->Lkid);
free(now);}
else if (tsRL(now) == BST_R) {
// <09><><EFBFBD>ҽڵ<D2BD>
Rlink(now->Father, now->Lkid);
free(now);}
}
// <09>ҵ<EFBFBD>
else if (now->Lkid == NULL && now->Rkid != NULL) {
if (tsRL(now) == BST_NULL) {
// <09><><EFBFBD>ڵ<EFBFBD>
root = root->Rkid;
--depth;
free(now);}
else if (tsRL(now) == BST_L) {
// <09><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
Llink(now->Father, now->Rkid);
free(now);}
else if (tsRL(now) == BST_R) {
// <09><><EFBFBD>ҽڵ<D2BD>
Rlink(now->Father, now->Rkid);
free(now);}
}
// ˫ϵ
else {
Lmax = Max(now->Lkid);
now->val = Lmax->val;
// <09>ƺ<EFBFBD>
if (tsRL(Lmax) == BST_L)
Llink(Lmax->Father, Lmax->Lkid == NULL ? NULL : Lmax->Lkid);
if (tsRL(Lmax) == BST_R)
Rlink(Lmax->Father, Lmax->Lkid == NULL ? NULL : Lmax->Lkid);
free(Lmax);
}
// <09><>β
return BST_OK;
}
//----------------------------------------------------------------------------------------------------
/**
* @brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ա
* @param num_save <EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ñ<EFBFBD><EFBFBD><EFBFBD>
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::Max(u32& num_save) {
num_save = Max(root)->val;
return BST_OK;}
//----------------------------------------------------------------------------------------------------
/**
* @brief <EFBFBD><EFBFBD>С<EFBFBD><EFBFBD>Ա
* @param num_save <EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ñ<EFBFBD><EFBFBD><EFBFBD>
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::Min(u32& num_save) {
num_save = Min(root)->val;
return BST_OK;}
//----------------------------------------------------------------------------------------------------
/**
* @brief <EFBFBD><EFBFBD>С<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
* @param p <EFBFBD>Ӹýڵ㼰<EFBFBD><EFBFBD><EFBFBD>µı<EFBFBD><EFBFBD><EFBFBD>
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::ergodic(STL_BST_Node* p) {
if (p == NULL)return BST_NULL;
// <09><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
if (p == NULL)return BST_NULL;
else(ergodic(p->Lkid));
// <09>е<EFBFBD><D0B5><EFBFBD>
printf("%3d ", p->val);
// <09>ҵ<EFBFBD><D2B5><EFBFBD>
if (p->Rkid == NULL)return BST_NULL;
else(ergodic(p->Rkid));
return BST_NULL;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------
// ˽<>к<EFBFBD><D0BA><EFBFBD>
/**
* @brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD>յĽڵ<EFBFBD>
* @param num <EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD>ʼ<EFBFBD><EFBFBD>ֵ
* @return <EFBFBD><EFBFBD>BST_RES
*/
STL_BST_Node* STL_BST::make(u32 num) {
STL_BST_Node* res=(STL_BST_Node*)malloc(sizeof(STL_BST_Node));
if (res == NULL)return NULL;
res->Father = NULL;
res->Lkid = NULL;
res->Rkid = NULL;
res->val = num;
res->heigh = 0;
return res;}
//----------------------------------------------------------------------------------------------------
/**
* @brief <EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӵ<EFBFBD><EFBFBD>ڵ<EFBFBD>
* @param F <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĸ<EFBFBD><EFBFBD>ڵ<EFBFBD>
* @param L <EFBFBD><EFBFBD><EFBFBD>ӵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::Llink(STL_BST_Node* F, STL_BST_Node* L) {
if (F == NULL || L == NULL)return BST_NULL;
F->Lkid = L;
L->Father = F;
return BST_OK;}
//----------------------------------------------------------------------------------------------------
/**
* @brief <EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӵ<EFBFBD><EFBFBD>ڵ<EFBFBD>
* @param F <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĸ<EFBFBD><EFBFBD>ڵ<EFBFBD>
* @param R <EFBFBD><EFBFBD><EFBFBD>ӵ<EFBFBD><EFBFBD>ҽڵ<EFBFBD>
* @return <EFBFBD><EFBFBD>BST_RES
*/
u32 STL_BST::Rlink(STL_BST_Node* F, STL_BST_Node* R) {
if (F == NULL || R == NULL)return BST_NULL;
F->Rkid = R;
R->Father = F;
return BST_OK;}
//----------------------------------------------------------------------------------------------------
/**
* @brief Ѱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľڵ<EFBFBD>
* @param p <EFBFBD>Ӵ˽ڵ㼰<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
* @return <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD>
*/
STL_BST_Node* STL_BST::Max(STL_BST_Node* p) {
if (p->Rkid == NULL)return p;
else return Max(p->Rkid);}
//----------------------------------------------------------------------------------------------------
/**
* @brief Ѱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>С<EFBFBD>Ľڵ<EFBFBD>
* @param p <EFBFBD>Ӵ˽ڵ㼰<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
* @return <EFBFBD><EFBFBD>С<EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD>
*/
STL_BST_Node* STL_BST::Min(STL_BST_Node* p) {
if (p->Lkid == NULL)return p;
else return Min(p->Lkid);}
//----------------------------------------------------------------------------------------------------
/**
* @brief <EFBFBD><EFBFBD><EFBFBD>Ըýڵ<EFBFBD>Ϊ<EFBFBD>丸<EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ㻹<EFBFBD><EFBFBD><EFBFBD>ҽڵ<EFBFBD>
* @param p <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Խڵ<EFBFBD>
* @return <EFBFBD><EFBFBD><EFBFBD><EFBFBD>ΪBST_L<EFBFBD><EFBFBD>BST_R,<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>޸<EFBFBD><EFBFBD>ڵ<EFBFBD>BST_NULL
*/
u32 STL_BST::tsRL(STL_BST_Node* p) {
if (p->Father == NULL)return BST_NULL;
else if (p->Father->Lkid == p)return BST_L;
else if (p->Father->Rkid == p)return BST_R;
else return BST_NULL;}
//////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------
// <09>ṹ<EFBFBD><E1B9B9><EFBFBD><EFBFBD>
STL_BST::STL_BST(void) {
root = NULL;
depth = 0;}
//----------------------------------------------------------------------------------------------------
STL_BST::~STL_BST(void) {
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
Reference in New Issue Copy Permalink