avl.h

本学期所有数据结构的大作业一

// AVL.h: interface for the AVL class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_AVL_H__98DB5A91_65E1_4989_B059_326A84371D42__INCLUDED_)
#define AFX_AVL_H__98DB5A91_65E1_4989_B059_326A84371D42__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class AVL  
//平衡二叉树类
{
public:
	AVL(int e);
	AVL();
	void leftRotate();
	//左旋该二叉树

	void rightRotate();
	//右旋该二叉树

	virtual void inOrderTraverse(CString &result);
	//中序遍历二叉树，并输出各个结点的数据

	virtual int insert(int e);
	//往该平衡二叉树中插入数据元素，并保持该二叉树的平衡
	//该树长高了返回1,否则返回0

	static AVL *makeAVL(int table[],int n);
	//根据所给数列构造一个平衡二叉树


	void calculateASL(int &numOfNode,int &total,int level);
	//用先序遍历该树的方法，统计结点的数目numOfNode,
	//及各结点的层次之和total,从而可计算出树的平均查找长度
	//level初始应为1

	void printASL(CString &result);
	//打印该树的ASL

	int whetherAVL();
    //用递归方法判断该二叉排序树是否为平衡二叉树，是返回该树的深度,否返回-1


	virtual ~AVL();

protected:
	int bf;//结点的平衡因子
	int data;
	AVL *rchild,*lchild;

};

#endif // !defined(AFX_AVL_H__98DB5A91_65E1_4989_B059_326A84371D42__INCLUDED_)