avl.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 196 行

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>

typedef char BELEM;

#include "..\include\book.h"
#include "..\include\avlbintree.h"

/*
class AVLTreeNode: public AVLBinNode
{
	private:
		// additional data member neede by6 AVLTreeNode
		int bf;
		// used by AVLTree class methods to allow casting
		// to a tree node pointer without casting
		AVLTreeNode* & left(void);
		AVLTreeNode* & right(void);

	public:
		// constructor
		AVLTreeNode (const BELEM & item, AVLTreeNode *lptr = NULL,
			AVLTreeNode *rptr = NULL, int balfac = 0);

		// return left/right TreeNode pointers as
		// AVLTreeNode pointers; handles casting of types
		AVLTreeNode *left(void) const;
		AVLTreeNode *right(void) const;

		// method to access new data field
		int GetBalceFactor(void);

		// AVLTree methods needs access to Left and Right
	friend class AVLTree;
};

// constructor; initialize balanceFacto and the base class.
// default pointer value NULL initialize node as a leaf node
AVLTreeNode::AVLTreeNode (const BELEM& item, AVLTreeNode *lptr,
							 AVLTreeNode *rptr, int balfac):
	AVLBinNode(item,lptr,rptr), bf(balfac)
	{ }

AVLTreeNode * AVLTreeNode::left(void) {
	return (AVLTreeNode *)left;
}

AVLTreeNode * AVLTreeNode::right(void) {
	return (AVLTreeNode *)right;
}

int AVLTreeNode::GetBalceFactor(void) {
	return balanceFactor;
}

*/



// LL型旋转以a为根的子树
void LL_rotation(AVLBinNode* a, AVLBinNode* &b) {   
   b = a->left;
   a->left = b->right;   a->bf = 0;
   b->right = a;         b->bf = 0;
}

// LR型旋转以a为根的子树
void LR_rotation(AVLBinNode* a, AVLBinNode* &b) {   
   AVLBinNode *c;
   b = a->left;   c = b->right;
   a->left = c->right;   b->right = c->left;
   c->right = a;         c->left = b;
   switch(c->bf)  {
      case  -1 : a->bf = 1;   b->bf = 0; // insert to c's left
                 break;
      case   1 : a->bf = 0;   b->bf = -1;  // insert to c's right
                 break;
      case   0 : a->bf = b->bf = 0;   // the inserted node is c itself
                 break;
   }
   c->bf = 0;    b = c;
}

// RR型旋转以a为根的子树
void RR_rotation(AVLBinNode* a, AVLBinNode* &b) {   
   b = a->right;
   a->right = b->left;   a->bf = 0;
   b->left = a;         b->bf = 0;
}

// RL型旋转以a为根的子树
void RL_rotation(AVLBinNode* a, AVLBinNode* &b) {   
   AVLBinNode *c;
   b = a->right;   c = b->left;
   a->right = c->left;   b->left = c->right;
   c->left = a;          c->right = b;
   switch(c->bf)  {
      case  -1 : a->bf = 0;   b->bf = 1;  // insert to c's left
                 break;
      case   1 : a->bf = -1;   b->bf = 0;  // insert to c's right
                 break;
      case   0 : a->bf = b->bf = 0;
                 break;
   }
   c->bf = 0;    b = c;
}

void ins_AVLtree(AVLBinNode* &rt, BELEM key) {
   AVLBinNode *s, *a, *b, *f, *p, *q;
   bool balanced;
   int d;
   s = new AVLBinNode;   s->element = key;
   s->left = s->right = NULL;   s->bf = 0;
   if (rt == NULL) { rt = s; return; }
   f = NULL;  a = p = rt; q = NULL;
   // 查找s的插入位置，并记录a(离插入结点最近，且平衡因子绝对值不等于0的结点)
   while (p != NULL) {   // 找插入位置
      if (p->bf != 0)  { a = p; f = q; }  // 记录a和其父结点f
      q = p;
      if (s->element < q->element)
         p = p->left;
      else p = p->right;
   }
   if (s->element < q->element)   // 插入s
      q->left = s;
   else q->right = s;
   if (s->element < a->element)  {  // s插入在a的左子树
      p = a->left;  b = p;  d = -1;
   }
   else  { p = a->right;  b = p;  d = 1; } // s插入在a的右子树
   // 把a的插入新结点部分的子树中结点的平衡因子都修改为不平衡
   while (p != s) { 
      if (s->element < p->element)  {
          p->bf = -1;   p = p->left;
      }
      else { p->bf = 1;   p = p->right; }
   }
   // 判断以a为根的子树是否失衡
   balanced = TRUE;
   if (a->bf == 0)  a->bf = d;   // a为根
   else if (a->bf + d == 0)  a->bf = 0;  // 正好调整为平衡
   else {  // 失衡
      balanced = FALSE;
      if (d == -1)  {
         if (b->bf == -1) LL_rotation(a, b);
         else LR_rotation(a, b);   // b->bf == +1
      }
      else  {
         if (b->bf == +1) RR_rotation(a, b);
         else RL_rotation(a, b);   // b->bf == -1
      }
   }
   if (!balanced)  {
      if (f == NULL)  rt = b;  // a为根
      else if (f->left == a)  f->left = b;
           else f->right = b;  // f->right == a
   }  
} 

void in_traverse(AVLBinNode *rt) {      // Inorder traversal
  if (rt == NULL) return;            // Nothing to visit
  in_traverse(rt->left);
  cout << rt->element << '(' << rt->bf <<')' << " ";
  in_traverse(rt->right);
}

void pre_traverse(AVLBinNode *rt) {      // Inorder traversal
  if (rt == NULL) return;            // Nothing to visit
  cout << rt->element << '(' << rt->bf <<')' << " ";
  pre_traverse(rt->left);
  pre_traverse(rt->right);
}

void main() {
	AVLBinNode *root;

	BELEM key;

	root = NULL;
	cout << "characters as the binary search key value" <<endl;
	cout << "X as EOF" << endl;	

	cin >> key;
	while (key != 'X') {		
		ins_AVLtree(root, key); 
		cin >> key;
	}
	cout << "*** preorder recursive ***" << endl;
	pre_traverse(root);    cout << endl;
	cout << "*** inorder recursive ***" << endl;
	in_traverse(root);    cout << endl;
}