|
#include<iostream>
#include<queue>
#include<String.h>
using namespace std;
enum State_code { success, fail, range_error, underflow, overflow, fatal, not_present, duplicate_error, entry_inserted, entry_found, internal_error };
enum Balance_factor { left_higher, equal_height, right_higher };
template <class Record> struct AVL_node
{
?? ?Record data;
?? ?AVL_node<Record>* left;
?? ?AVL_node<Record>* right;
?? ?Balance_factor balance; //4个方法 // constructors:?
?? ?AVL_node();//
?? ?AVL_node(const Record& x);//
?? ?void set_balance(Balance_factor b);//
?? ?Balance_factor get_balance() const;//
};
template <class Record> class AVL_tree
{
public: //17+2方法数
?? ?AVL_tree();//
?? ?bool empty() const;//判空?
?? ?void preorder(void (*visit)(Record&));//先序遍历?
?? ?void inorder(void (*visit)(Record&));//中序遍历
?? ?void postorder(void (*visit)(Record&));//后序遍历
?? ?void level_traverse(void (*visit)(Record&));//按层次遍历?
?? ?int size() const;//树中节点总数?
?? ?int height() const;//树高?
?? ?int width() const;//树宽?
?? ?void clear();//置空
?? ?AVL_tree(const AVL_tree<Record>& original);//构造?
?? ?AVL_tree& operator =(const AVL_tree<Record>& original);//拷贝构造?
?? ?~AVL_tree();//析构 ok
?? ?State_code insert(const Record& new_data);//插入新节点，数据为new_data?
?? ?State_code remove(const Record& old_data);//找到数据为old_data的节点删除
?? ?State_code retrieve(Record& target) const;//查找关键字为target的节点带回
?? ?State_code replace(Record& target);//查找关键字为target的节点，修改非关键字部分?
?? ?void print_tree(void (*f)(int indentation, AVL_node<Record>*&)); // 用于验证树形结构
?? ?void prenode(int indentation, AVL_node<Record>* root, void (*f)(int indentation, AVL_node<Record>*&));// 用于验证树形结构
?? ?
?? ?
private:
?? ?AVL_node<Record>* root; //此处添加需要用到的其他私有方法?
?? ?State_code avl_insert(AVL_node<Record>*& sub_root, const Record& new_data, bool& taller);//avl树的插入
?? ?void rotate_left(AVL_node<Record>*& sub_root);//左转
?? ?void rotate_right(AVL_node<Record>*& sub_root);//右转
?? ?void right_balance(AVL_node<Record>*& sub_root);
?? ?void left_balance(AVL_node<Record>*& sub_root);
?? ?int recursive_height(AVL_node<Record>* sub_root)const;
?? ?void recursive_preorder(AVL_node<Record>* sub_root, void(*visit)(Record&));
?? ?void recursive_inorder(AVL_node<Record>* sub_root, void(*visit)(Record&));
?? ?void recursive_postorder(AVL_node<Record>* sub_root, void(*visit)(Record&));
?? ?void recursive_clear(AVL_node<Record>*& sub_root);
?? ?int recursive_size(AVL_node<Record>* sub_root) const;
?? ?State_code remove_avl(AVL_node<Record>*& sub_root, const Record &target, bool& shorter);
?? ?State_code remove_avl_left(AVL_node<Record>*& sub_root, const Record &target, bool& shorter);
?? ?State_code remove_avl_right(AVL_node<Record>*& sub_root, const Record &target, bool& shorter);
?? ?AVL_node<Record>* recursive_copy(AVL_node<Record>* sub_root);
?? ?AVL_node<Record>* search_for_node(AVL_node<Record>* sub_root, const Record& target) const;
?? ?int recursive_width(AVL_node<Record>* sub_root)const;
};
template <class Record>?
AVL_node<Record>::AVL_node()
{
?? ?balance = equal_height;
?? ?left = right = NULL;
}
template <class Record>?
AVL_node<Record>::AVL_node(const Record& x)
{
?? ?balance = equal_height;
?? ?left = right = NULL;
?? ?data = x;
}
template <class Record>?
void AVL_node<Record>::set_balance(Balance_factor b)
{
?? ?balance = b;
}
template <class Record>?
Balance_factor AVL_node<Record>::get_balance() const
{
?? ?return balance;
}
template <class Record>
AVL_tree<Record>::AVL_tree()
{
?? ?root = NULL;
}
template <class Record>
bool AVL_tree<Record>::empty()const
{
?? ?return root == NULL;
}
//先序遍历：根左右
template <class Record>
void AVL_tree<Record>::preorder(void (*visit)(Record&))
{
?? ?recursive_preorder(root, visit);
}
template <class Record>
void AVL_tree<Record>::recursive_preorder(AVL_node<Record>* sub_root, void(*visit)(Record&))
{
?? ?if (sub_root != NULL)
?? ?{
?? ??? ?(*visit)(sub_root->data);
?? ??? ?recursive_preorder(sub_root->left, visit);
?? ??? ?recursive_preorder(sub_root->right, visit);
?? ?}
}
//中序遍历：左根右
template <class Record>
void AVL_tree<Record>::inorder(void (*visit)(Record&))
{
?? ?recursive_inorder(root, visit);
}
template <class Record>
void AVL_tree<Record>::recursive_inorder(AVL_node<Record>* sub_root, void(*visit)(Record&))
{
?? ?if (sub_root != NULL)
?? ?{
?? ??? ?recursive_inorder(sub_root->left, visit);
?? ??? ?(*visit)(sub_root->data);
?? ??? ?recursive_inorder(sub_root->right, visit);
?? ?}
}
//后序遍历：左右根
template <class Record>
void AVL_tree<Record>::postorder(void (*visit)(Record&))
{
?? ?recursive_postorder(root, visit);
}
template <class Record>
void AVL_tree<Record>::recursive_postorder(AVL_node<Record>* sub_root, void(*visit)(Record&))
{
?? ?if (sub_root != NULL)
?? ?{
?? ??? ?recursive_postorder(sub_root->left, visit);
?? ??? ?recursive_postorder(sub_root->right, visit);
?? ??? ?(*visit)(sub_root->data);
?? ?}
}
//按层次遍历
template <class Record>
void AVL_tree<Record>::level_traverse(void (*visit)(Record&))
{
?? ?queue<AVL_node<Record>*> waiting_nodes;
?? ?if (root!=NULL)
?? ??? ?waiting_nodes.push(root);
?? ?do
?? ?{
?? ??? ?AVL_node<Record>* temp = waiting_nodes.front(); //读出队列第一个元素赋给temp
?? ??? ?cout << temp->data << " ? ?"; ?//输出temp中的数据
?? ??? ?waiting_nodes.pop(); ?//出队
?? ??? ?//有左子，加入队列
?? ??? ?if (temp->left)
?? ??? ??? ?waiting_nodes.push(temp->left);
?? ??? ?//有右子，加入队列
?? ??? ?if (temp->right)
?? ??? ??? ?waiting_nodes.push(temp->right);
?? ?}while (!waiting_nodes.empty());
}
template <class Record>?
State_code AVL_tree<Record>::retrieve(Record& target) const
{
?? ?State_code result = success;
?? ?AVL_node<Record>* found = search_for_node(root, target);
?? ?if (found == NULL)
?? ??? ?result = not_present;
?? ?else
?? ??? ?target = found->data;
?? ?return result;
}
template <class Record>?
AVL_node<Record>* AVL_tree<Record>::search_for_node(AVL_node<Record>* sub_root, const Record& target) const
{
?? ?while (sub_root != NULL && sub_root->data != target)
?? ??? ?//待查元素大，往右找
?? ??? ?if (sub_root->data < target)
?? ??? ??? ?sub_root = sub_root->right;
?? ??? ?//待查元素小，往左找
?? ??? ?else sub_root = sub_root->left;
?? ?return sub_root;
}
template <class Record>
int AVL_tree<Record>::size() const
{
?? ?return recursive_size(root);
}
template <class Record>
int AVL_tree<Record>::recursive_size(AVL_node<Record>* sub_root) const
{
?? ?if (sub_root == NULL)
?? ??? ?return 0;
?? ?return 1 + recursive_size(sub_root->left) + recursive_size(sub_root->right);
}
template <class Record>
int AVL_tree<Record>::height()const
{
?? ?return recursive_height(root);
}
template <class Record>
int AVL_tree<Record>::recursive_height(AVL_node<Record>* sub_root)const
{
?? ?if (sub_root == NULL) return 0;
?? ?if (sub_root -> get_balance() == right_higher)
?? ??? ?return 1 + recursive_height(sub_root -> right);
?? ?return 1 + recursive_height(sub_root -> left);
}
template <class Record>
int AVL_tree<Record>::width()const
{
?? ?return recursive_width(root);
}
template <class Record>
int AVL_tree<Record>::recursive_width(AVL_node<Record>* sub_root)const
{
?? ?if (sub_root == NULL) {
?? ??? ?return 0;
?? ?}
?? ?int maxwidth = 0;
?? ?if (sub_root->left == NULL && sub_root->right == NULL) {
?? ??? ?return 1;
?? ?}
?? ?else {
?? ??? ?maxwidth = max(recursive_width(sub_root->left) + recursive_width(sub_root->right), maxwidth);
?? ?}
?? ?return maxwidth;
}
template <class Record>
void AVL_tree<Record>::clear()
{
?? ?recursive_clear(root);
}
template <class Record>
void AVL_tree<Record>::recursive_clear(AVL_node<Record>*& sub_root)
{
?? ?AVL_node<Record>* temp = sub_root;
?? ?if (sub_root == NULL)return;
?? ?recursive_clear(sub_root->left);
?? ?recursive_clear(sub_root->right);
?? ?sub_root = NULL;
?? ?delete temp;
}
template <class Record>
AVL_tree<Record>::~AVL_tree()
{
?? ?clear();
}
template <class Record>
AVL_tree<Record>& AVL_tree<Record>::operator =(const AVL_tree<Record>& original)
{
?? ?AVL_tree<Record> new_copy(original);
?? ?clear();
?? ?root = new_copy.root;
?? ?new_copy.root = NULL;
?? ?return*this;
}
template <class Record>
AVL_tree<Record>::AVL_tree(const AVL_tree<Record>& original)
{
?? ?root = recursive_copy(original.root);
}
template <class Record>
AVL_node<Record>* AVL_tree<Record>::recursive_copy(AVL_node<Record>* sub_root)
{
?? ?if (sub_root == NULL)
?? ??? ?return NULL;
?? ?AVL_node<Record>* temp = new AVL_node<Record>(sub_root->data);
?? ?temp->left = recursive_copy(sub_root->left);
?? ?temp->right = recursive_copy(sub_root->right);
?? ?return temp;
}
template <class Record>?
State_code AVL_tree<Record>::insert(const Record& new_data)
{
?? ?bool taller;
?? ?return avl_insert(root, new_data, taller);
}
template <class Record>?
State_code AVL_tree<Record>::avl_insert(AVL_node<Record>* &sub_root, const Record& new_data, bool& taller)
{
?? ?State_code result = success;
?? ?if (sub_root == NULL)
?? ?{
?? ??? ?sub_root = new AVL_node<Record>(new_data);
?? ??? ?taller = true;
?? ?}
?? ?else if (new_data == sub_root -> data)
?? ?{
?? ??? ?result = duplicate_error;
?? ??? ?taller = false;
?? ?}
?? ?else if (new_data < sub_root -> data)
?? ?{
?? ??? ?result = avl_insert(sub_root -> left, new_data, taller);
?? ??? ?if (taller == true)
?? ??? ??? ?switch (sub_root -> get_balance())
?? ??? ??? ?{
?? ??? ??? ?case left_higher: ?//本来是左高，往左插入一个数据，变成左高2，不平衡
?? ??? ??? ??? ?left_balance(sub_root);
?? ??? ??? ??? ?taller = false;
?? ??? ??? ??? ?break;
?? ??? ??? ?case equal_height: ?//本来是等高，变成左高
?? ??? ??? ??? ?sub_root -> set_balance(left_higher);
?? ??? ??? ??? ?break;
?? ??? ??? ?case right_higher: ?//本来是右高，变成等高
?? ??? ??? ??? ?sub_root -> set_balance(equal_height); ?
?? ??? ??? ??? ?taller = false;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ?}
?? ?else
?? ?{
?? ??? ?result = avl_insert(sub_root -> right, new_data, taller);
?? ??? ?if (taller == true)
?? ??? ??? ?switch (sub_root -> get_balance())
?? ??? ??? ?{
?? ??? ??? ?case left_higher:
?? ??? ??? ??? ?sub_root -> set_balance(equal_height);
?? ??? ??? ??? ?taller = false;
?? ??? ??? ??? ?break;
?? ??? ??? ?case equal_height:
?? ??? ??? ??? ?sub_root -> set_balance(right_higher);
?? ??? ??? ??? ?break;
?? ??? ??? ?case right_higher:
?? ??? ??? ??? ?right_balance(sub_root);
?? ??? ??? ??? ?taller = false;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ?}
?? ?return result;
}
template <class Record>
void AVL_tree<Record>::rotate_left(AVL_node<Record>*& sub_root)
{
?? ?if (sub_root == NULL||sub_root -> right == NULL)
?? ??? ?cout<<"WARNINGprogram error detected in rotate_left"<<endl;
?? ?else
?? ?{
?? ??? ?AVL_node<Record> *right_tree = sub_root -> right;?
?? ??? ?sub_root -> right = right_tree -> left; ?//让right_tree的左子成为sub_root的右子
?? ??? ?right_tree -> left = sub_root; ?//让sub成为right的左子
?? ??? ?sub_root = right_tree; ?//让right成为新的sub
?? ?}
}
template <class Record>
void AVL_tree<Record>::rotate_right(AVL_node<Record>*& sub_root)
{
?? ?if (sub_root == NULL||sub_root -> left == NULL) ??
?? ??? ?cout<<"WARNINGprogram error in detected in rotate_right"<<endl;
?? ?else
?? ?{
?? ??? ?AVL_node<Record> *left_tree = sub_root -> left;
?? ??? ?sub_root -> left = left_tree -> right;
?? ??? ?left_tree -> right = sub_root;
?? ??? ?sub_root = left_tree;
?? ?}
}
template <class Record>
void AVL_tree<Record>::right_balance(AVL_node<Record>*& sub_root)
{
?? ?AVL_node<Record>*& right_tree = sub_root -> right;
?? ?switch (right_tree -> get_balance())
?? ?{
?? ?case right_higher:
?? ??? ?sub_root -> set_balance(equal_height);
?? ??? ?right_tree -> set_balance(equal_height);
?? ??? ?rotate_left(sub_root);
?? ??? ?break;
?? ?case equal_height:
?? ??? ?cout<<"WARNINGprogram error deteced in right_balance"<<endl;
?? ?case left_higher:
?? ??? ?AVL_node<Record>*& sub_tree = right_tree -> left;
?? ??? ?switch (sub_tree -> get_balance())
?? ??? ?{
?? ??? ?case equal_height:
?? ??? ??? ?sub_root -> set_balance(equal_height);
?? ??? ??? ?right_tree -> set_balance(equal_height);
?? ??? ??? ?break;
?? ??? ?case left_higher:
?? ??? ??? ?sub_root -> set_balance(equal_height);
?? ??? ??? ?right_tree -> set_balance(right_higher);
?? ??? ??? ?break;
?? ??? ?case right_higher:
?? ??? ??? ?sub_root -> set_balance(left_higher);
?? ??? ??? ?right_tree -> set_balance(equal_height);
?? ??? ??? ?break;
?? ??? ?}
?? ??? ?sub_tree -> set_balance(equal_height);
?? ??? ?rotate_right(right_tree);
?? ??? ?rotate_left(sub_root);
?? ??? ?break;
?? ?}
}
template <class Record>
void AVL_tree<Record>::left_balance(AVL_node<Record>*& sub_root)
{
?? ?AVL_node<Record>*& left_tree = sub_root -> left;
?? ?switch (left_tree -> get_balance())
?? ?{
?? ?case left_higher:
?? ??? ?sub_root -> set_balance(equal_height);
?? ??? ?left_tree -> set_balance(equal_height);
?? ??? ?rotate_right(sub_root);
?? ??? ?break;
?? ?case equal_height:
?? ??? ?cout<<"WARNINGprogram error detected in left_balance"<<endl;
?? ?case right_higher:
?? ??? ?AVL_node<Record>*& sub_tree = left_tree -> right;
?? ??? ?switch (sub_tree -> get_balance())
?? ??? ?{
?? ??? ?case equal_height:
?? ??? ??? ?sub_root -> set_balance(equal_height);
?? ??? ??? ?left_tree -> set_balance(equal_height);
?? ??? ??? ?break;
?? ??? ?case right_higher:
?? ??? ??? ?sub_root -> set_balance(equal_height);
?? ??? ??? ?left_tree -> set_balance(left_higher);
?? ??? ??? ?break;
?? ??? ?case left_higher:
?? ??? ??? ?sub_root -> set_balance(right_higher);
?? ??? ??? ?left_tree -> set_balance(equal_height);
?? ??? ??? ?break;
?? ??? ?}
?? ??? ?sub_tree -> set_balance(equal_height);
?? ??? ?rotate_left(left_tree);
?? ??? ?rotate_right(sub_root);
?? ??? ?break;
?? ?}
}
template <class Record>
State_code AVL_tree<Record>::remove(const Record& target)
{
?? ?bool shorter;
?? ?return remove_avl(root, target, shorter);
}
template <class Record>
State_code AVL_tree<Record>::remove_avl(AVL_node<Record>*& sub_root, const Record &target, bool& shorter)
{
?? ?AVL_node<Record>* temp;
?? ?if (sub_root == NULL)
?? ??? ?return fail;
?? ?else if (target < sub_root->data)
?? ??? ?return remove_avl_left(sub_root, target, shorter);
?? ?else if (target > sub_root->data)
?? ??? ?return remove_avl_right(sub_root, target, shorter);
?? ?else if (sub_root->left == NULL)
?? ?{
?? ??? ?temp = sub_root;
?? ??? ?sub_root = sub_root->right;
?? ??? ?delete temp;
?? ??? ?shorter = true;
?? ?}
?? ?else if (sub_root->right == NULL)
?? ?{
?? ??? ?temp = sub_root;
?? ??? ?sub_root = sub_root->left;
?? ??? ?delete temp;
?? ??? ?shorter = true;
?? ?}
?? ?else if (sub_root->get_balance() == left_higher)
?? ?{
?? ??? ?temp = sub_root->left;
?? ??? ?while (temp->right != NULL) temp = temp->right;
?? ??? ?sub_root->data = temp->data;
?? ??? ?remove_avl_left(sub_root, temp->data, shorter);
?? ?}
?? ?else
?? ?{
?? ??? ?temp = sub_root->right;
?? ??? ?while (temp->left != NULL) temp = temp->left;
?? ??? ?sub_root->data = temp->data;
?? ??? ?remove_avl_right(sub_root, temp->data, shorter);
?? ?}
}
template <class Record>
State_code AVL_tree<Record>::remove_avl_left(AVL_node<Record>*& sub_root, const Record &target, bool& shorter)
{
?? ?State_code result = remove_avl(sub_root->left, target, shorter);
?? ?if (shorter == true)
?? ??? ?switch (sub_root->get_balance())
?? ??? ?{
?? ??? ?case equal_height: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?? ??? ??? ?sub_root->set_balance(right_higher);
?? ??? ??? ?shorter = false;
?? ??? ??? ?break;
?? ??? ?case left_higher: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ?break;
?? ??? ?case right_higher: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?? ??? ??? ?AVL_node<Record>* temp = sub_root->right;
?? ??? ??? ?switch (temp->get_balance()) {
?? ??? ??? ?case equal_height: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?? ??? ??? ??? ?temp->set_balance(left_higher);
?? ??? ??? ??? ?rotate_left(sub_root);
?? ??? ??? ??? ?shorter = false;
?? ??? ??? ??? ?break;
?? ??? ??? ?case right_higher:
?? ??? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ??? ?temp->set_balance(equal_height);
?? ??? ??? ??? ?rotate_left(sub_root);
?? ??? ??? ??? ?break;
?? ??? ??? ?case left_higher: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?? ??? ??? ??? ?AVL_node<Record>* temp_left = temp->left;
?? ??? ??? ??? ?switch (temp_left->get_balance())
?? ??? ??? ??? ?{
?? ??? ??? ??? ?case equal_height:
?? ??? ??? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ??? ??? ?temp->set_balance(equal_height);
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case right_higher:
?? ??? ??? ??? ??? ?sub_root->set_balance(left_higher);
?? ??? ??? ??? ??? ?temp->set_balance(equal_height);
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case left_higher:
?? ??? ??? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ??? ??? ?temp->set_balance(right_higher);
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?temp_left->set_balance(equal_height);
?? ??? ??? ??? ?rotate_right(sub_root->right);
?? ??? ??? ??? ?rotate_left(sub_root);
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ?}
?? ?return result;
}
template <class Record>
State_code AVL_tree<Record>::remove_avl_right(AVL_node<Record>*& sub_root, const Record &target, bool& shorter)
{
?? ?State_code result = remove_avl(sub_root->right, target, shorter);
?? ?if (shorter == true)
?? ??? ?switch (sub_root->get_balance())
?? ??? ?{
?? ??? ?case equal_height: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?? ??? ??? ?sub_root->set_balance(left_higher);
?? ??? ??? ?shorter = false;
?? ??? ??? ?break;
?? ??? ?case right_higher: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ?break;
?? ??? ?case left_higher: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
?? ??? ??? ?AVL_node<Record>* temp = sub_root->left;
?? ??? ??? ?switch (temp->get_balance()) {
?? ??? ??? ?case equal_height: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?? ??? ??? ??? ?temp->set_balance(right_higher);
?? ??? ??? ??? ?rotate_right(sub_root);
?? ??? ??? ??? ?shorter = false;
?? ??? ??? ??? ?break;
?? ??? ??? ?case left_higher: ? ? ? ? ? ?
?? ??? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ??? ?temp->set_balance(equal_height);
?? ??? ??? ??? ?rotate_right(sub_root);
?? ??? ??? ??? ?break;
?? ??? ??? ?case right_higher: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?? ??? ??? ??? ?AVL_node<Record>* temp_right = temp->right;
?? ??? ??? ??? ?switch (temp_right->get_balance())
?? ??? ??? ??? ?{
?? ??? ??? ??? ?case equal_height:
?? ??? ??? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ??? ??? ?temp->set_balance(equal_height);
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case left_higher:
?? ??? ??? ??? ??? ?sub_root->set_balance(right_higher);
?? ??? ??? ??? ??? ?temp->set_balance(equal_height);
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?case right_higher:
?? ??? ??? ??? ??? ?sub_root->set_balance(equal_height);
?? ??? ??? ??? ??? ?temp->set_balance(left_higher);
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?temp_right->set_balance(equal_height);
?? ??? ??? ??? ?rotate_left(sub_root->left);
?? ??? ??? ??? ?rotate_right(sub_root);
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ?}
?? ?return result;
}
template <class Record>
State_code AVL_tree<Record>::replace(Record& target)
{
?? ?AVL_node<Record>* found = search_for_node(root,target);
?? ?found->balance = equal_height; //修改非关键字部分
?? ?cout << "change success" << endl;
?? ?return success;
}
template <class Record>
void AVL_tree<Record>::prenode(int indentation, AVL_node<Record>* root, void (*f)(int indentation, AVL_node<Record>*&))
{
?? ?if (root != NULL)
?? ?{
?? ??? ?(*f)(indentation, root);
?? ??? ?prenode(indentation + 1, root->left, f);
?? ??? ?prenode(indentation + 1, root->right, f);
?? ?}
}
template <class Record> void AVL_tree<Record>::print_tree(void (*f)(int indentation, AVL_node<Record>*&))
{
?? ?prenode(0, root, f);
}
void print_node(int indentation, AVL_node<int>*& x) // tree printing function?
{?
?? ?for(int i=0; i<indentation; i++) std::cout <<" ";
? ? std::cout << "( " << x->data << " : -> " << " ";?
? ? switch (x->get_balance())?
?? ?{?
?? ? ? ? case left_higher: std::cout << "L"; break;?
?? ??? ? case right_higher: std::cout << "R"; break;?
?? ??? ? case equal_height: std::cout << "E"; break;?
?? ?}
?? ?std::cout << " ) ===> ";?
?? ?if (x->left != NULL) std::cout << (x->left)->data << " ";?
?? ?if (x->right != NULL) std::cout << (x->right)->data << " ";?
?? ?std::cout << " \n" << std::flush;?
}
|