我有一个任务要实现一个 AVL 树，我首先要实现一个二叉搜索树。我正在努力弄清楚我在执行删除有两个孩子的节点时做错了什么。 remove 函数在删除叶节点或具有一个子节点的节点时起作用。
函数 removal() 是实际实现的地方。
下面是头文件
#pragma once
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
// AVL Node Class
template <class T>
class AVLTreeNode {
public:
// Node attributes
AVLTreeNode* parent;
AVLTreeNode* left;
AVLTreeNode* right;
T data;
unsigned int height;
// Default constructor
AVLTreeNode(T val) {
data = val;
parent = nullptr;
left = nullptr;
right = nullptr;
height = 0;
}
};
// AVL Tree class
template <class T>
class AVLTree {
private:
// pointer to root of the tree
AVLTreeNode<T>* root;
// variable to record the the current number of values in the tree
int currentSize;
// Private helper methods
// POST: deallocates dynamic memory of the tree
void deleteTree(AVLTreeNode<T>* node);
// PARAM: node - starting node to search from
// target - value to search for
// POST: Return true if target is in tree, otherwise return false
bool BSTSearch(AVLTreeNode<T>* node, T target) const;
// PARAM: node - starting node to traverse
// value - value to be inserted into tree
// POST: recurse through the tree and find place to insert value, returns node
AVLTreeNode<T>* insertion(AVLTreeNode<T>* node, T value);
// PARAM: node - starting node to traverse
// value - value to be removed from tree
// POST: recurse through the tree and find value to remove, returns node
AVLTreeNode<T>* removal(AVLTreeNode<T>* node, T value);
// PARAM: node - starting node to traverse
// POST: find and return the successor of the node param
AVLTreeNode<T>* findSuccessor(AVLTreeNode<T>* node);
// PARAM: node - starting node to grab values from
// POST: insert values into vector by inorder traversal
void inOrderVector(AVLTreeNode<T>* node, vector<T> &vector) const;
public:
// Default constructor
AVLTree();
// Destructor
~AVLTree();
// Mutators
// PARAM: value - template value to be added into tree
// POST: if val isn't in the tree, insert the value into the tree and return true
// otherwise, don't insert val and return false
bool insert(T value);
// PARAM: value - template value to be added into tree
// POST: removes param value and returns true, return false if value is not within tree
bool remove(T value);
// Accessors
// PARAM: target - template value to be searched within tree
// POST: returns true if target is found, return false otherwise
bool search(T target) const;
// POST: returns a vector with all the values of the tree, in ascending order
vector<T> values() const;
// POST: return the number of values in the tree
int size() const;
};
// AVL Tree Method Implementations
// Default constructor
template <class T>
AVLTree<T>::AVLTree() {
root = nullptr;
currentSize = 0;
}
// Destructor
template <class T>
AVLTree<T>::~AVLTree() {
deleteTree(root);
}
// Mutators
// PARAM: value - template value to be added into tree
// POST: if val isn't in the tree, insert the value into the tree and return true
// otherwise, don't insert param and return false
template <class T>
bool AVLTree<T>::insert(T value) {
// search tree for param
bool exists = BSTSearch(root, value);
// if param is not in tree, insert it and return true
if (exists == false) {
// start from root
root = insertion(root, value);
// increment size
currentSize++;
return true;
// otherwise, return false
} else {
return false;
}
}
// PARAM: value - template value to be added into tree
// POST: removes param value and returns true, return false if value is not within tree
template <class T>
bool AVLTree<T>::remove(T value) {
// search tree for param
bool exists = BSTSearch(root, value);
// if param is not in tree, return false
if (exists == false) {
return false;
}
root = removal(root, value);
currentSize--;
return true;
}
// Accessors
// PARAM: target - value to be searched within tree
// POST: returns true if target is found, return false otherwise
template <class T>
bool AVLTree<T>::search(T target) const {
return BSTSearch(root, target);
}
// POST: returns a vector with all the values of the tree, in ascending order
template <class T>
vector<T> AVLTree<T>::values() const {
// create vector for values
vector<T> values;
inOrderVector(root, values);
// return vector
return values;
}
// POST: return the number of values in the tree
template <class T>
int AVLTree<T>::size() const {
return this->currentSize;
}
// Private Helper Methods
// POST: deallocates dynamic memory of the tree
template <class T>
void AVLTree<T>::deleteTree(AVLTreeNode<T>* node) {
// recursively goes through tree until both children are null
if (node != nullptr) {
// move to left child
deleteTree(node->left);
// move to right child
deleteTree(node->right);
// delete node
delete node;
}
}
// PARAM: node - starting node to search from
// target - value to search for
// POST: Return true if target is in tree, otherwise return false
template <class T>
bool AVLTree<T>::BSTSearch(AVLTreeNode<T>* node, T target) const {
// reached end of path
if (node == nullptr) {
return false;
// if target is found
} else if (target == node->data) {
return true;
// target is less than current node, go down to left
} else if (target < node->data) {
return BSTSearch(node->left, target);
// target is greater than current node, go down to right
} else {
return BSTSearch(node->right, target);
}
}
// PARAM: node - starting node to traverse
// data - value to be inserted into tree
// POST: recurse through the tree and find place to insert value, return node that was inserted
template <class T>
AVLTreeNode<T>* AVLTree<T>::insertion(AVLTreeNode<T>* node, T value) {
// base case
if (node == nullptr) {
// create new node with value and return it
AVLTreeNode<T>* temp = new AVLTreeNode(value);
return temp;
}
// traverse through tree and find position for new node
if (value < node->data) {
// go down to left child
AVLTreeNode<T>* leftChild = insertion(node->left, value);
node->left = leftChild; // set the current node's left*
leftChild->parent = node; // set the parent node of left to be current node
} else {
// go down to right child
AVLTreeNode<T>* rightChild = insertion(node->right, value);
node->right = rightChild; // set the current node's right*
rightChild->parent = node; // set the parent node of right to be current node
}
return node;
}
// PARAM: node - starting node to traverse
// POST: find and return the successor of the node param
template <class T>
AVLTreeNode<T>* AVLTree<T>::findSuccessor(AVLTreeNode<T>* node) {
// create pointer to right child
AVLTreeNode<T>* successor = node;
// loop down to find left most node
while (successor != nullptr && successor->left != nullptr) {
successor = successor->left;
}
// return the successor
return successor;
}
// PARAM: node - starting node to traverse
// value - value to be removed from tree
// POST: recurse through the tree and find value to remove, returns node
template <class T>
AVLTreeNode<T>* AVLTree<T>::removal(AVLTreeNode<T>* node, T value) {
// base case
if (node == nullptr) {
return node;
}
// if value is less than current node, go to left
if (value < node->data) {
node->left = removal(node->left, value);
// if value is greater than current node, go to right
} else if (value > node->data) {
node->right = removal(node->right, value);
// if value is equal to current node, remove it
} else {
// if node has no children
if (node->left == nullptr && node->right == nullptr) {
// delete node and return
delete node;
return nullptr;
// if node has only one child (right)
} else if (node->left == nullptr) {
// check if the node being removed is the left or right child of the parent
// then replace the node with it's subtree
if (node->parent->left == node) {
node->parent->left = node->right;
} else {
node->parent->right = node->right;
}
// delete the node and return the new subtree
delete node;
return node->right;
// if node has only one child (left)
} else if (node->right == nullptr) {
// check if the node being removed is the left or right child of the parent
// then replace the node with it's subtree
if (node->parent->left == node) {
node->parent->left = node->left;
} else {
node->parent->right = node->left;
}
// delete node
delete node;
return node->left;
}
// if node has two children
// find successor first
AVLTreeNode<T>* successor = findSuccessor(node->right);
// detach successor
if (successor->parent->left == successor) {
successor->parent->left = nullptr;
} else {
successor->parent->right = nullptr;
}
// make the successor's children the node's children
successor->right = node->right;
successor->left = node->left;
// make the successor the child of the node's parent
if (node->parent->left == node) {
node->parent->left = successor;
} else {
node->parent->right = successor;
}
// delete the node
delete node;
}
return node;
}
// PARAM: node - starting node to grab values from
// POST: insert values into vector by inorder traversal
template <class T>
void AVLTree<T>::inOrderVector(AVLTreeNode<T>* node, vector<T> &vector) const {
// if tree is empty, return empty vector
if (node == nullptr) {
return;
}
// go to left node
inOrderVector(node->left, vector);
// push data into vector
vector.push_back(node->data);
// go to right node
inOrderVector(node->right, vector);
}
这就是我用来测试功能的东西。
#include "AVLFunctions.h"
int main()
{
AVLTree<int> tree;
cout << "inserting 47: " << tree.insert(47) << endl;
cout << "inserting 32: " << tree.insert(32) << endl;
cout << "inserting 19: " << tree.insert(19) << endl;
cout << "inserting 41: " << tree.insert(41) << endl;
cout << "inserting 37: " << tree.insert(37) << endl;
cout << "inserting 44: " << tree.insert(44) << endl;
cout << "inserting 63: " << tree.insert(63) << endl;
cout << "inserting 96: " << tree.insert(96) << endl;
cout << "inserting 14: " << tree.insert(14) << endl;
cout << "removing: " << tree.remove(41) << endl;
cout << "search removed node: " << tree.search(41) << endl;
vector<int> v = tree.values();
cout << "tree values: {";
for (int i = 0; i < v.size(); i++) {
cout << " " << v.at(i);
}
cout << " }" << endl;
}
这是我运行代码时得到的结果：
inserting 47: 1
inserting 32: 1
inserting 19: 1
inserting 41: 1
inserting 37: 1
inserting 44: 1
inserting 63: 1
inserting 96: 1
inserting 14: 1
removing: 1
search removed node: 1
Segmentation fault