AVL 二叉树旋转和删除树的 c++ 问题

Question

我正在研究一个 AVL 二叉树实现，除了我的旋转和删除函数之外，我的大部分代码都在工作。我尝试了不同的实现方法，但我仍然无法弄清楚我做错了什么。如果有人可以帮助我解决方案，将不胜感激。如果我注释掉平衡函数，代码将根据需要工作并插入导入的文本文件中的所有单词，但当我尝试平衡节点时，代码就会崩溃。由于某种原因，我的有问题:

删除节点；

我的代码部分，但我不确定为什么这会成为问题。遍历树的递归没有问题，但是一旦它到达删除节点部分就会出现问题，这对我来说毫无意义......

标题:

#ifndef AVLBINARYTREE_H
#define AVLBINARYTREE_H
#include <iostream>
#include <string>
using namespace std;

class LinkedBinaryTree {
private:
    struct Node {
        string word;
        Node* left;
        Node* right;
        Node* parent;
        int wordCount;
        int height;
        Node() : word(), left(NULL), right(NULL), parent(NULL), wordCount(1), height(0) {}
        Node(string s, Node* l, Node* r, Node* p) {
            word = s;
            left = NULL;
            right = NULL;
            parent = p;
            wordCount = 1;
            height = 0;
        }
    };

    Node* _root;

public:
    LinkedBinaryTree();
    ~LinkedBinaryTree();
    void destroyTree();
    void destroyTree(Node* node);
    void insert(string word);
    void display(Node* ptr, int level);
    Node* root();
    void inOrder(Node* node);
    int avlNum(Node* node);
    int getNumWords();

    void insertNode(Node* node, string word);
    int height(Node* node);
    int bfactor(Node* node);
    void fixHeight(Node* node);
    void balance(Node* node);
    void rightRotate(Node* node);
    void leftRotate(Node* node);
    void rightLeftRotate(Node* node);
    void leftRightRotate(Node* node);

    int n;
};
#endif

.cpp:

#include "AVLBinaryTree.h"
#include <algorithm>

void LinkedBinaryTree::inOrder(Node* node) {

    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->wordCount << " " << node->word << endl;
    inOrder(node->right);
}

void LinkedBinaryTree::rightRotate(Node* node) {

    Node* temp;
    temp = node->left;
    node->left = temp->right;
    //node->left->parent = node;
    temp->parent = node->parent;
    temp->right = node;
    node->parent = temp;
    node = temp;
    if (temp->parent == NULL) {
        _root = node;
    }
    fixHeight(node);
    fixHeight(node->right);
    fixHeight(node->left);
}

void LinkedBinaryTree::leftRotate(Node* node) {

    Node* temp;
    temp = node->right;
    node->right = temp->left;
    temp->parent = node->parent;
    temp->left = node;
    node->parent = temp;
    node = temp;
    if (temp->parent == NULL) {
        _root = node;
    }
    fixHeight(node);
    fixHeight(node->right);
    fixHeight(node->left);
}

void LinkedBinaryTree::rightLeftRotate(Node* node) {

    rightRotate(node->left);
    leftRotate(node);
}

void LinkedBinaryTree::leftRightRotate(Node* node) {

    leftRotate(node->right);
    rightRotate(node);
}

int LinkedBinaryTree::height(Node* node) {

    int h = 0;

    if (node != NULL) {
        h = node->height;
    }
    return h;
}

int LinkedBinaryTree::bfactor(Node* node) {

    return height(node->right) - height(node->left);
}

void LinkedBinaryTree::fixHeight(Node* node) {

    int hl = height(node->left);
    int hr = height(node->right);
    node->height = (hl > hr ? hl : hr) + 1;
}

int LinkedBinaryTree::avlNum(Node* node) {

    int leftH = height(node->left);
    int rightH = height(node->right);
    int avlNum = rightH - leftH;
    return avlNum;
}

LinkedBinaryTree::LinkedBinaryTree() {

    _root = NULL;
}

LinkedBinaryTree::~LinkedBinaryTree() {

    destroyTree();
}
void LinkedBinaryTree::destroyTree() {

    destroyTree(_root);
}
//**********************************************************
// destroyTree is called by the destructor. It deletes  
// all nodes in the tree.                                  
//**********************************************************
void LinkedBinaryTree::destroyTree(Node* node) {

    if (node != NULL) {
        if (node->left != NULL)
            destroyTree(node->left);
        if (node->right != NULL)
            destroyTree(node->right);
        delete node;
    }
}

void LinkedBinaryTree::insertNode(Node* node, string word) {

    if (word < node->word) {
        if (node->left != NULL)
            insertNode(node->left, word);
        else {
            node->left = new Node(word, NULL, NULL, node);
            n++;
            fixHeight(node->left);
        }
    }
    else if (word > node->word) {

        if (node->right != NULL)
            insertNode(node->right, word);
        else {
            node->right = new Node(word, NULL, NULL, node);
            n++;
            fixHeight(node->right);
        }
    }
    else if (word == node->word) {
        node->wordCount++;
    }
    balance(node);
}

void LinkedBinaryTree::insert(string word) {

    if (_root == NULL) {
        _root = new Node(word, NULL, NULL, NULL);
        n++;
    }
    else {
        insertNode(_root, word);
    }
}
void LinkedBinaryTree::display(Node* ptr, int level) {

    int i;
    if (ptr != NULL)
    {
        display(ptr->right, level + 1);
        printf("\n");
        if (ptr == _root)
            cout << "Root -> ";
        for (i = 0; i < level && ptr != _root; i++)
            cout << "        ";
        cout << ptr->word;
        display(ptr->left, level + 1);
    }
}

LinkedBinaryTree::Node * LinkedBinaryTree::root() {

    return _root;
}

void LinkedBinaryTree::balance(Node* node) {

    fixHeight(node);
    if (bfactor(node) == 2) {
        if (bfactor(node->right) < 0)
            rightRotate(node->right);
        else
            leftRotate(node);
    }
    if (bfactor(node) == -2) {
        if (bfactor(node->left) > 0)
            leftRotate(node->left);
        else
            rightRotate(node);
    }
}

int LinkedBinaryTree::getNumWords() {

    return n;
}

主要内容:

#include "AVLBinaryTree.h"
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <functional>

int main(int argv, char *argc[]) {

    LinkedBinaryTree t;
    string word("Test."), lastword("");

    for (int i = 0; i < argv; i++)
        cout << argc[i] << endl;

    if (argv < 2) {
        cerr << "No input file specified" << endl;
        system("pause");
        exit(1);
    }
    for (int count = 1; count < argv; count++)
    {
        ifstream input(argc[count]);
        if (!input) {
            cerr << "Cannot open input file" << argc[count] << endl;
            system("pause");
            exit(1);
        }
        while (input >> word)
        {
            transform(word.begin(), word.end(), word.begin(), ::tolower);

            word.erase(remove_if(word.begin(), word.end(), ispunct));

            t.insert(word);
        }
    }

    t.inOrder(t.root());
    cout << endl;

    cout << "--------" << endl;
    cout << t.getNumWords() << "  " << "Total number of different words";
    cout << endl;


    /*t.insert("Yes");
    t.insert("No");
    t.insert("Maybe");
    t.insert("Hopefully");
    t.insert("Absolutely");

    t.display(t.root(), 1);

    cout << endl;
    cout << endl;

    t.inOrder(t.root());
    */

    system("PAUSE");

    t.~LinkedBinaryTree();

    return EXIT_SUCCESS;
}

提前致谢!

Answer 1

旋转函数中的 node = temp; 行正在更改属于该函数的指针的本地值，不是存储在树中的值。例如，当你调用rightRotate(node->right)时，node->right的值在应该更新的时候调用后是一样的。

可能的解决方案包括将节点指针作为引用传递给旋转函数 (void LinkedBinaryTree::rightRotate(Node*& node)) 以便更新原始值，或者返回更新后的值value (Node *LinkedBinaryTree::rightRotate(Node* node)) 并适本地存储它。

您的balance 函数和其他旋转函数可能会受到类似的影响。