bst1.h

数据结构常用算法设计 用C++实现二叉排序树与平衡二叉树

// BST1.h: interface for the BST class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BST1_H__7FDF02D1_D24C_41FC_8087_AC3D37ABCA73__INCLUDED_)
#define AFX_BST1_H__7FDF02D1_D24C_41FC_8087_AC3D37ABCA73__INCLUDED_

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

//二叉排序树类
class BST  
{
public:
	BST(int e);

	BST();

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

	int searchBST(int key,BST *&p );
	//在二叉排序树中查找数据key,找到返回1,p指向对应的结点。找不到
	//返回0,p指向查找路径上最后一个结点

	virtual int insert(int key);
	//在二叉排序树中插入数据结点

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

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

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

	static BST *makeBST(int table[],int n);
	//生成一棵二叉排序树


	virtual ~BST();

protected:
	int data;
	BST *lchild,*rchild;
	
};

#endif // !defined(AFX_BST1_H__7FDF02D1_D24C_41FC_8087_AC3D37ABCA73__INCLUDED_)