小甲鱼来看看AVL树的问题
我按你的教程敲的代码(虽然是C++的),测试正常,不过我前序遍历树时,根据遍历结果画出来的树不是AVL树,求解决#ifndef AVL_H_INCLUDED#define AVL_H_INCLUDED
#include <memory>
#include <initializer_list>
#include <iostream>
template <class Type>
class AVL{
enum BF{RH = -1, EH, LH};
struct BiTreeNode {
Type _data;
BF _bf;
std::shared_ptr<BiTreeNode> _lChild;
std::shared_ptr<BiTreeNode> _rChild;
};
typedef std::shared_ptr<BiTreeNode> Tree;
public:
typedef size_t size_type;
typedef Type value_type;
typedef value_type& reference;
typedef const reference const_reference;
AVL(const AVL<Type>&) = delete;
AVL<Type>& operator=(const AVL<Type>&) = delete;
AVL() = default;
AVL(const std::initializer_list<Type>& li) : AVL(li.begin(), li.end()) {}
template <class In> AVL(In first, In last);
AVL<Type>& push(const Type&);
// AVL<Type>& pop(const Type&);
bool find(const Type&)const;
size_type size()const { return _size; }
bool empty()const { return _size == 0; }
const_reference root() const { return _root ->_data; }
void show()const { show(_root); }
private:
bool push(Tree& root, const Type&, bool& taller);
void left_balance(Tree& root);
void left_rotate(Tree& root); // 左旋操作
void right_balance(Tree& root);
void right_rotate(Tree& root); // 右旋操作
bool find(const Tree&, const Type&)const;
void show(const Tree&)const;
Tree _root;
size_type _size = 0;
};
template <class Type>
bool AVL<Type>::push(Tree& root, const Type& item, bool& taller)
{
if (!root) {
root = std::make_shared<BiTreeNode>();
root ->_bf = EH;
root ->_data = item;
taller = true;
++_size;
}
else if (item == root ->_data)
return taller = false;
else if (item < root ->_data) {
if (!push(root ->_lChild, item, taller))
return false;
if (taller) { // 树的高度增加了
switch (root ->_bf) {
case LH: // 未插入时左子树比右子树高
// 形成不平衡局面
left_balance(root); // 调整
taller = false; // 平衡后树的高度不增加
break;
case EH: // 未插入时树左右一样高
root ->_bf = LH; // 插入后左子树比右子树高
taller = true; // 树的高度增加了
break;
case RH: // 未插入时右子树高
root ->_bf = EH; // 插入后左右子树一样高
taller = false; // 树的高度未增加
break;
}
}
else { // 没有成功地插入左子树
if (!push(root ->_rChild, item, taller))
return false;
if (taller) {
switch (root ->_bf) {
case LH:
root ->_bf = EH;
taller = false;
break;
case EH:
root ->_bf = RH;
taller = true;
break;
case RH:
right_balance(root);
taller = false;
break;
}
}
}
}
else {
if (!push(root ->_rChild, item, taller))
return false;
if (taller) {
switch (root ->_bf) {
case LH:
root ->_bf = EH;
taller = false;
break;
case EH:
root ->_bf = RH;
taller = true;
break;
case RH:
right_balance(root);
taller = false;
break;
}
}
else {
if (!push(root ->_lChild, item, taller))
return false;
if (taller) {
switch (root ->_bf) {
case LH:
left_balance(root);
taller = false;
break;
case EH:
root ->_bf = LH;
taller = true;
break;
case RH:
root ->_bf = EH;
taller = false;
break;
}
}
}
}
return false;
}
template <class Type>
void AVL<Type>::left_balance(Tree& root)
{
Tree l = root ->_lChild, lr;
switch (l ->_bf) {
case LH: // 若左子树比右子树高
root ->_bf = l ->_bf = EH;
right_rotate(root); // 右旋
break;
case RH:
lr = l ->_rChild;
switch (lr ->_bf) {
case LH:
root ->_bf = RH;
l ->_bf = EH;
break;
case EH:
root ->_bf = l ->_bf = EH;
break;
case RH:
root ->_bf = EH;
l ->_bf = LH;
break;
}
lr ->_bf = EH;
left_rotate(root ->_lChild); // 双旋处理
right_rotate(root);
break;
}
}
template <class Type>
void AVL<Type>::right_rotate(Tree& root)
{
Tree l = root ->_lChild;
root ->_lChild = l ->_rChild;
l ->_rChild = root;
root = l;
}
template <class Type>
void AVL<Type>::left_rotate(Tree& root)
{
Tree r = root ->_rChild;
root ->_rChild = r ->_lChild;
r ->_lChild = root;
root = r;
}
template <class Type>
void AVL<Type>::right_balance(Tree& root)
{
Tree l = root ->_lChild, lr;
switch (l ->_bf) {
case RH:// 若右子树比左子树高
root ->_bf = l ->_bf = EH;
left_rotate(root);
break;
case LH:
lr = l ->_rChild;
switch (lr ->_bf) {
case LH:
root ->_bf = RH;
l ->_bf = EH;
break;
case EH:
root ->_bf = l ->_bf = EH;
break;
case RH:
root ->_bf = EH;
l ->_bf = LH;
break;
}
lr ->_bf = EH;
right_rotate(root ->_rChild); // 双旋处理
left_rotate(root);
break;
}
}
template <class Type>
AVL<Type>& AVL<Type>::push(const Type& item)
{
bool taller;
push(_root, item, taller);
return *this;
}
template <class Type>
template <class In>
AVL<Type>::AVL(In first, In last)
{
while (first != last)
push(*first++);
}
template <class Type>
bool AVL<Type>::find(const Type& item)const
{
return find(_root, item);
}
template <class Type>
bool AVL<Type>::find(const Tree& root, const Type& item)const
{
if (root) {
if (root ->_data == item)
return true;
if (item < root ->_data)
return find(root ->_lChild, item);
else
return find(root ->_rChild, item);
}
return false;
}
template <class Type>
void AVL<Type>::show(const Tree& root)const
{
if (root) {
std::cout << "root:\n";
std::cout << root ->_data << '\n';
std::cout << "lChild:\n";
show(root ->_lChild);
if (root == _root)
std::cout << "真*根节点";
std::cout << "rChild:\n";
show(root ->_rChild);
if (!root ->_lChild && !root ->_rChild)
std::cout << "*************************\n";
}
}
#endif // AVL_H_INCLUDED测试代码#include "AVL.h"
#include <iostream>
int main()
{
AVL<int> avl {5,7,8,9,3,0,1,2,4,1,5};
std::cout << "size: " << avl.size() << "\nfind(5) = " << avl.find(5) << "\nfind(1) = " << avl.find(1)
<< "\nfind(8) = " << avl.find(8) << "\nfind(10) = " << avl.find(10) << "\nfind(0) = " << avl.find(0)
<< "\nfind(4) = " << avl.find(4) << "\nfind(3) = " << avl.find(3) << "\nfind(2) = " << avl.find(2) << "\nfind(7) = "
<< avl.find(7) << "\nfind(9) = " << avl.find(9) << "\n";
avl.show();
avl.push(10);
std::cout << "\nfind(10) = " << avl.find(10) << "\n";
return 0;
}
页:
[1]