C++版AVL树课程设计源代码

该程序通过C++实现了AVL树的一些基础操作：1.编写AVL树判别程序，并判别一个二叉搜索树是否为AVL树；2.实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；3.实现基本操作的动态演示(图形演示)；最重要的是，该程序可以画出你所输入的树

// BNode.cpp: implementation of the BNode class.
//
//////////////////////////////////////////////////////////////////////

#include “AVLDist.h“

void BTree::Initialize（）
{
	int value;
	BNode * temp;
	cout<<“请输入二叉搜索树先序序列（输入0结束）：“<	for（;;）
	{
		cin>>value;
		if（!value）
			break;
		temp=new BNode（value）;
		MakeTree（temp）;
		
	}
}

BTree * BTree::MakeTree（BNode * v）
{
	BNode *z=root *pz=0;

	if（!root）
	{
		root=v;
		count++;
		return this;
	}
	else
	{
		while（z）{
			pz=z;
			if（v->data < z->data） z=z->LiftNode;
			else if（v->data > z->data） z=z->RightNode;
			else cout<<“对不起，你所要输入的元素已存在！“<		}

		if（root）{//树非空
		if（v->data < pz->data） pz->LiftNode = v;
		else pz->RightNode = v;}
	}
	return 0;

}

BNode * BTree::Search（int v）
{
	BNode * temp=root;
	queue tempQ;
	for（;;）
	{
		if（temp->LiftNode）
			tempQ.push（temp->LiftNode）;
		if（temp->RightNode）
			tempQ.push（temp->RightNode）;

		if（temp->data==v）
			return temp;

		if（!tempQ.empty（））
		{
		
			temp=tempQ.front（）;
		    tempQ.pop（）;
		}
		else
		{
			cout<<“没有该父节点。“<			return 0;
		}
		

	}
}

int BTree::sHeight（BNode * node）
{	
	int h1=0h2=0;
	if（!node->LiftNode&&!node->RightNode）
		return 1;
	else
	{
		if（node->LiftNode）
			h1=sHeight（node->LiftNode）;
		if（node->RightNode）
		    h2=sHeight（node->RightNode）;

		if（h1>=h2）
			return （h1+1）;
		else
			return （h2+1）;

	}

}


void BTree::Dist（BNode * node）
{	//判断插入的二叉搜索树是否是AVL树
		if（node->LiftNode）
			Dist（node->LiftNode）;//递归判断是否是AVL树
		if（node->RightNode）
		    Dist（node->RightNode）;
		
		int h1=0h2=0bf;
		if（node->LiftNode） h1=sHeight（node->LiftNode）;//左右节点高度
		if（node->RightNode） h2=sHeight（node->RightNode）;
		bf=h1-h2;

		if（avlTree）{
		if（bf<-1 || bf>1） avlTree=false;
		else avlTree=true;}

}


void BTree::Show（）
{//画树
    int tempC=SHeight（）;
	queue tempQ;
	BNode * temp=root;

	cout<<“该树如下：“<	
	for（int j=tempC;j>0;j--）
	{			
		for（int k=0;k<2*pow（2j-1）;k++）
			cout<<“ “;


        for（int i=0;i		{
            if（temp）
		        temp->ShowNode（）;
			else
				cout<<“ “;
            if（temp&&temp->LiftNode）
		       tempQ.push（temp->LiftNode）;
			else
				tempQ.push（0）;
	        if（temp&&temp->RightNode）
				tempQ.push（temp->RightNode）;
			else
				tempQ.push（0）;

		    
	           temp=tempQ.front（）;
               tempQ.pop（）;
			
			for（int k=0;k				cout<<“ “;
		}
	   cout<	}

}


void BTree::preOrder（BNode * node）
{//前序
	if（node）
	{
		Visit（node）;
		preOrder（node->LiftNode）;
		preOrder（node->RightNode）;
	}
}
void BTree::inOrder（BNode * node）
{//中序
	if（node）
	{
		inOrder（node->LiftNode）;
		Visit（node）;
		inOrder（node->RightNode）;
	}
}
void BTree::postOrder（BNode * node）
{//后序
	if（node）
	{
		postOrder（node->LiftNode）;
		postOrder（node->RightNode）;
		Visit（node）;
	}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-07-08 15:14  MyAVLTree7\
     文件        4581  2014-04-02 13:52  MyAVLTree7\AVLDist.cpp
     文件        1807  2014-04-02 13:50  MyAVLTree7\AVLDist.h
     文件        8193  2014-04-02 13:53  MyAVLTree7\AVLTree.cpp
     文件        1008  2014-04-02 13:50  MyAVLTree7\AVLTree.h
     目录           0  2014-04-16 11:25  MyAVLTree7\Debug\
     文件      292195  2014-04-02 13:53  MyAVLTree7\Debug\AVLDist.obj
     文件      189249  2014-04-02 13:53  MyAVLTree7\Debug\AVLTree.obj
     文件      263441  2014-04-16 11:25  MyAVLTree7\Debug\main.obj
     文件      643180  2014-04-16 11:25  MyAVLTree7\Debug\MyAVLTree7.exe
     文件      955576  2014-04-16 11:25  MyAVLTree7\Debug\MyAVLTree7.ilk
     文件     3264004  2014-04-02 13:53  MyAVLTree7\Debug\MyAVLTree7.pch
     文件     1426432  2014-04-16 11:25  MyAVLTree7\Debug\MyAVLTree7.pdb
     文件      107520  2014-05-11 09:41  MyAVLTree7\Debug\vc60.idb
     文件      143360  2014-04-16 11:25  MyAVLTree7\Debug\vc60.pdb
     文件        2664  2014-04-04 19:35  MyAVLTree7\main.cpp
     文件        4578  2014-04-02 13:52  MyAVLTree7\MyAVLTree7.dsp
     文件         528  2014-04-02 13:48  MyAVLTree7\MyAVLTree7.dsw
     文件       50176  2014-07-08 15:14  MyAVLTree7\MyAVLTree7.ncb
     文件       49664  2014-07-08 15:14  MyAVLTree7\MyAVLTree7.opt
     文件         254  2014-05-11 09:41  MyAVLTree7\MyAVLTree7.plg