AVL 树节点（打印）

Question

我目前正在研究 AVL 树，我很好奇为什么输出（前序遍历）只显示两级缩进，就好像其中一个二阶节点指向三个独立的三级节点一样。我确定这是我的打印功能或实际代码的问题。


#include <iostream>
#include <list>
#include <vector>
#include <iomanip>
using namespace std;

template <class T>
class BST;

template <class T>
class BSTNode{
    T data;
    BSTNode<T>* parent;
    BSTNode<T>* left;
    BSTNode<T>* right;
    int height;
public:
    BSTNode(T data = T(), BSTNode<T>* parent = nullptr, BSTNode<T>* left = nullptr,
            BSTNode<T>* right = nullptr, int height = 0) : data(data), parent(parent), left(left), right(right), height(height){}
    friend class BST<T>;
    int getSize() const;
};

template <class T>
class BST{
public:
    BSTNode<T>* root = nullptr;
    BST() {}
    ~BST();
    BST(const BST& rhs) {*this = rhs;};
    BST& operator=(const BST& rhs);
    void printPreOrder(BSTNode<T>* p, int indent);
    void insert(T item, BSTNode<T> * & node);
    void remove(BSTNode<T>*& temp); //pass pointer by reference because we will be changing the pointer
    void clear(BSTNode<T>*& root); //clears the entire tree;
    BST<T>* clone(BSTNode<T>* start);
    void rotateRight(BSTNode<T> * & node); //rotate the left child (the left child becomes the parent and parent becomes the right child)
    void rotateLeft(BSTNode<T> * & node); //rotate the right child (the right child becomes the parent and the parent becomes the left child)
    void doubleRotateRight(BSTNode<T> *& node); //same result as rotate right
    void doubleRotateLeft(BSTNode<T> *& node); //same result as rotate left
    int height(BSTNode<T> * node); //return height
    void balance(BSTNode<T> * &node);
};

template <class T>
int BSTNode<T>::getSize() const {
    int count = 1;
    if(left != nullptr){
        count += left->getSize();
    };
    if(right != nullptr){
        count += right->getSize();
    };
    return count;
}
template <class T>
void BST<T>::printPreOrder(BSTNode<T>* p, int indent){
    if(p) {
        if (indent) {
            std::cout << std::setw(indent) << '\t';
        }
        cout<< p->data << "\n ";
        if(p->left) printPreOrder(p->left, indent+2);
        if(p->right) printPreOrder(p->right, indent+2);
    }
}
template <class T>
void BST<T>::insert(T item, BSTNode<T> * & node){
    if(!node){
        node = new BSTNode<T>(item);
    }
    else if(item < node->data){
        insert(item, node->left);
    }
    else{
        insert(item, node->right);
    }
    balance(node);
}
template <class T>
void BST<T>::remove(BSTNode<T>*& temp){
    if(temp->left == nullptr && temp->right == nullptr){
        if(temp->parent == nullptr){
            root = nullptr;
        }
        else if(temp->parent->left == temp){
            temp->parent->left = nullptr;
        }
        else{
            temp->parent->right = nullptr;
        }
        delete temp;
    }
    else if(temp->left == nullptr){ //promote right
        BSTNode<T>* toDelete = temp->right;
        temp->data = toDelete->data;
        temp->left = toDelete->left;
        temp->right = toDelete->right;
        if(temp->left){
            temp->left->parent = temp->left;
        }
        if(temp->right){
            temp->right->parent = temp;
        }
        delete toDelete;
    }
    else if(temp->right == nullptr){ //promote left
        BSTNode<T>* toDelete = temp->left;
        temp->data = toDelete->data;
        temp->left = toDelete->left;
        temp->right = toDelete->right;
        if(temp->left){
            temp->left->parent = temp->left;
        }
        if(temp->right){
            temp->right->parent = temp;
        }
        delete toDelete;
    }
    else{
        BSTNode<T>* maxOfLeft = temp->left;
        while(maxOfLeft){
            maxOfLeft = maxOfLeft->right;
        }
        temp->data = maxOfLeft->data;
        remove(maxOfLeft);
    }
    balance(temp);
}
template <class T>
void BST<T>::clear(BSTNode<T>*& root) {
    if (root) {
        if (root->left) {
            clear(root->left);
        }
        if (root->right) {
            clear(root->right);
        }
        delete root;
    }
    root = nullptr;
};
template <class T>
BST<T>::~BST(){
    clear(root);
}
template <class T>
BST<T>* BST<T>::clone(BSTNode<T>* start){
    if(!start){
        return nullptr;
    }
    else{
        return new BSTNode<T>(start->data, clone(start->left), clone(start->right));
    }
}
template <class T>
BST<T>& BST<T>::operator=(const BST<T>& rhs){
    if(this == &rhs){
        return *this;
    }
    clear(root);
    root = clone(rhs.root);
    return *this;
}
template <class T>
void BST<T>::rotateRight(BSTNode<T> * & node){

    BSTNode<T> * newParent = node->left;
    node->left = newParent->right;
    newParent->right = node;

    node->height = max(height(node->right),height(node->left)) + 1;
    newParent->height = max(height(newParent->left), node->height) + 1;

    node = newParent; //set new root (we can't access newParent outside of this function!)
}
template <class T>
void BST<T>::rotateLeft(BSTNode<T> * & node){

    BSTNode<T> * newParent = node->right;
    node->right = newParent->left;
    newParent->left = node;

    node->height = max(height(node->right), height(node->left)) + 1;
    newParent->height = max(height(newParent->right), node->height) + 1;

    node = newParent; //set new root (we can't access newParent outside of this function!)
}
template <class T>
int BST<T>::height(BSTNode<T> *node){
    if(node){
        return node->height;
    };
    return -1;
}
template <class T>
void BST<T>::doubleRotateRight(BSTNode<T> * &node){
    rotateLeft(node->left);
    rotateRight(node);
}
template<class T>
void BST<T>::doubleRotateLeft(BSTNode<T> * &node){
    rotateRight(node->right);
    rotateLeft(node);
}
template<class T>
void BST<T>::balance(BSTNode<T> * &node){
    if(!node){
        return;
    }
    if(height(node->left) > height(node->right) + 1){
        if(height(node->left->left) >= height(node->left->right)){
            rotateRight(node);
        }
        else{
            doubleRotateRight(node);
        };
    };
    if(height(node->right) > height(node->left) + 1){
        if(height(node->right->right) >= height(node->right->left)){
            rotateLeft(node);
        }
        else{
            doubleRotateLeft(node);
        }
    }
    node->height = max(height(node->right), height(node->left)) + 1;
}

int main() {

    vector<int>data = {5, 3, 4, 2, 1, 2, 6, 7};
    BST<int> test;

    for(int r : data){
        test.insert(r, test.root);
    }

    test.printPreOrder(test.root,0);
    cout << endl;

    return 0;
}

这是我得到的输出：

根据我的理解，我应该得到以下输出：

Answer 1

不要使用制表符。

考虑这个例子：

#include <iostream>
#include <iomanip>

int main() {

    for (int indent=0;indent<5;++indent) {
        if (indent) {
            std::cout << std::setw(indent) << "\t" << "tabs" << "\n";
            std::cout << std::setw(indent) << " " << "spaces" << "\n";
        }
    }
}

可能的输出是：

    tabs
 spaces
    tabs
  spaces
    tabs
   spaces
    tabs
    spaces

AVL 树节点（打印）

AVL Tree Nodes (Print)

c++

tree

binary-tree

binary-search-tree

avl-tree