avltree.h

一个用C++实现的平衡二叉树算法

#pragma once

typedef struct avlTree_Node
{
	int data;                         // 二叉树节点数据
    int balanceNO;                    // 二叉树节点的平衡度
	int height;                       // 指示该节点所在的层次

	struct avlTree_Node* lChild;      // 二叉平衡树的左孩子节点
	struct avlTree_Node* rChild;      // 二叉平衡树的右孩子节点
	struct avlTree_Node* parent;
}avlTreeNode;

typedef struct queue_Node             // 定义队列节点
{
	avlTreeNode* data;
	struct queue_Node* next;
}queueNode;
typedef struct                        // 定义队列的数据结构
{     
	queueNode* front;
    queueNode* tail;
}queue;

typedef struct stack_Node             // 定义堆栈节点结构
{
	avlTreeNode* data;
	struct stack_Node *next;
}stackNode;

class avlTree
{
private:
	void AVLTree_HeightChange(  avlTreeNode* nodeTempPoint , int operationChoice );
	void AVLTree_BalanceChange( avlTreeNode** tree , avlTreeNode* tempPoint1 , avlTreeNode* tempPoint2 , char directionChoice );          // 调整节点平衡度
	void AVLTree_LChange( avlTreeNode** tree );                // 根据平衡度来判断进行LL旋转或LR旋转
	void AVLTree_RChange( avlTreeNode** tree );                //根据平衡度进行RR旋转或者进行RL旋转
	void AVLTree_Swap( avlTreeNode* tempPoint1 , avlTreeNode* tempPoint2 );
	void AVLTree_BalanceSwitch( avlTreeNode** tree , int* unbalance );
	//void AVLTree_ParentBalanceChange( avlTreeNode* avlTreeNodeTempPoint );
	//avlTreeNode* AVLTree_ResearchNode( avlTreeNode** tree , int researchValue );

public:
	avlTree( void );
	~avlTree( void );

	void AVLTreeInsert( avlTreeNode** tree , int tempData , int *ifHeight , int heightCount );  // 平衡二叉树的插入算法，第一个int数据为待插入的数据，第二int数据传递高度变化，*IfHeight指示插入新节点后树的高度是否改变
	void AVLTreeCreate( avlTreeNode** tree );
	void AVLTreeOrder( avlTreeNode** tree );
	void AVLTreeDelete( avlTreeNode** tree , int deleteValue , int* unbalance );
    //void AVLTreePrint( avlTreeNode** tree );
};