//?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?data）?z=z->LiftNode;
			else?if（v->data?>?z->data）?z=z->RightNode;
			else?cout<<“對不起，你所要輸入的元素已存在！“<		}

		if（root）{//樹非空
		if（v->data?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