BST示例代碼如下:
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *lchild, *rchild, *father;
Node(int _data, Node *_father = NULL) {
data = _data;
lchild = NULL;
rchild = NULL;
father = _father;
}
~Node() {
if (lchild != NULL) {
delete lchild;
}
if (rchild != NULL) {
delete rchild;
}
}
void insert(int value) {
if (value == data) {
return;
} else if (value > data) {
if (rchild == NULL) {
rchild = new Node(value, this);
} else {
rchild->insert(value);
}
} else {
if (lchild == NULL) {
lchild = new Node(value, this);
} else {
lchild->insert(value);
}
}
}
Node* search(int value) {
if (data == value) {
return this;
} else if (value > data) {
if (rchild == NULL) {
return NULL;
} else {
return rchild->search(value);
}
} else {
if (lchild == NULL) {
return NULL;
} else {
return lchild->search(value);
}
}
}
Node* predecessor() {
Node *temp = lchild;
while (temp != NULL && temp->rchild != NULL) {
temp = temp->rchild;
}
return temp;
}
Node* successor() {
Node *temp = rchild;
while (temp != NULL && temp->lchild != NULL) {
temp = temp->lchild;
}
return temp;
}
};
class BinaryTree {
private:
Node *root;
public:
BinaryTree() {
root = NULL;
}
~BinaryTree() {
if (root != NULL) {
delete root;
}
}
void insert(int value) {
if (root == NULL) {
root = new Node(value);
} else {
root->insert(value);
}
}
bool find(int value) {
if (root->search(value) == NULL) {
return false;
} else {
return true;
}
}
};
int main() {
BinaryTree binarytree;
int arr[10] = { 8, 9, 10, 3, 2, 1, 6, 4, 7, 5 };
for (int i = 0; i < 10; i++) {
binarytree.insert(arr[i]);
}
int value;
cin >> value;
if (binarytree.find(value)) {
cout << "search success!" << endl;
} else {
cout << "search failed!" << endl;
}
return 0;
}
BST的元素刪除
BST節(jié)點(diǎn)的前驅(qū)與后繼搜索
某個BST節(jié)點(diǎn)的前驅(qū)汇陆,即為值比它小的最大的一個節(jié)點(diǎn)——進(jìn)入該節(jié)點(diǎn)的左子樹,然后不斷搜索左子樹的右孩子看尼,找到最后的節(jié)點(diǎn)即可
Node* predecessor(){
Node* temp=lchild;
while(temp!=NULL&&temp->lchild!=NULL){
temp=temp->lchild;
}
return temp;
}
后繼也是一樣兆览,完全相反即可匿醒,此處略
刪除度數(shù)為0或者1的節(jié)點(diǎn)
對于一個非空的節(jié)點(diǎn),首先檢查它是否有左孩子或者右孩子——因?yàn)樵摴?jié)點(diǎn)度數(shù)為0或者1梯码,所以最多只能有一個孩子
對于節(jié)點(diǎn)delete_node的孩子temp,首先孩子的父親設(shè)置為delete_node的父親鳄抒,然后斷開其與delete_node的聯(lián)系
接下來判斷delete_node是其父節(jié)點(diǎn)的左孩子還是右孩子,確認(rèn)之后把temp換上
最后直接刪除delete_node
代碼如下:
void remove_node(Node* delete_node){ //delete_node的度為0或者1
Node* temp=NULL;
if(delete_node->lchild!=NULL){
temp=delete_node->lchild;
temp->father=delete_node->father;
delete_node->lchild=NULL;
}
if(delete_node->rchild!=NULL){
temp=delete_node->rchild;
temp->father=delete_node->father;
delete_node->rchild=NULL;
}
if(delete_node->father->lchild==delete_node){
delete_node->father->lchild=temp;
}
else{
delete_node->father->rchild=temp;
}
delete delete_node;
}
刪除度數(shù)為2的節(jié)點(diǎn)
首先找到待刪除的節(jié)點(diǎn)
如果節(jié)點(diǎn)的左孩子存在耐朴,就把delete_node設(shè)置為節(jié)點(diǎn)的前驅(qū)
右孩子存在則設(shè)定為后繼
都不存在則設(shè)定為節(jié)點(diǎn)自身(此時待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn))
把delete_node的data值賦給原本待刪除的節(jié)點(diǎn)——相當(dāng)于將待刪除的節(jié)點(diǎn)與delete_node調(diào)換
最后直接刪除delete_node
bool delete_tree(int value){
Node *delete_node,*current_node;
current_node=search(value);
if(current_node==NULL){
return false;
}
if(current_node->lchild!=NULL){
delete_node=current_node->predecessor();
}
else if(current_node->rchild!=NULL){
delete_node=current_node->successor();
}
else{
delete_node=current_node;
}
current_node->data=delete_node->data;
remove_node(delete_node);
return true;
}