#include“AvlTree.h“
#include
using?namespace?std;
void?AvlTree::PreOrderTraversal（AvlNode*?BT）{
	if（BT）{
	cout<val.id（）<<“?“<val.pw（）<<‘?‘;
????PreOrderTraversal（BT->left）;
????PreOrderTraversal（BT->right）;
????}
}
void?AvlTree::InOrderTraversal（AvlNode*BT）{
	if（BT）{
????InOrderTraversal（BT->left）;
????cout<val.id（）<<“?“<val.pw（）<<‘?‘;
????InOrderTraversal（BT->right）;
????}
}
void?AvlTree::PostOrderTraversal（AvlNode*BT）{
	if（BT）{
????PostOrderTraversal（BT->left）;
????PostOrderTraversal（BT->right）;
????cout<val.id（）<<“?“<val.pw（）<<‘?‘;
????}
}

void?AvlTree::LevelOrder（）
{
	queue?q;//建立隊列q?
????AvlNode*front;
????if?（root?==?NULL）return;//如果樹空，則不進行操作?
????q.push（root）;//將根節點壓入隊列
????while?（!q.empty（））//循環直到隊列空?
????{
????????front?=?q.front（）;
????????q.pop（）;//彈出隊列的隊頂元素
????????if?（front->left）//如果節點有左兒子，則把左兒子壓入隊列末端
????????????q.push（front->left）;?
????????if?（front->right）//如果節點有右兒子，則把右兒子壓入隊列末端
????????????q.push（front->right）;
????????cout<val.id（）<<“?“<val.pw（）<<‘?‘;
????}
}
AvlNode?*?AvlTree::Empty（AvlNode?*?cur）//刪除樹
{
????if（cur==NULL）?return?NULL;//如果樹空，則返回NULL?
????Empty（cur->left）;//遞歸刪除?
????Empty（cur->right）;//遞歸刪除?
????free（cur）;//釋放節點?
????return?NULL;
}
?
inline?int?AvlTree::Height（AvlNode?*?cur）//計算高度
{
????if（cur==NULL）?return?0;
????return?cur->height;//獲得樹高?
}
?
AvlNode*?AvlTree::LLchange（AvlNode?*?cur）?//LL旋轉操作
{
?????AvlNode?*?temp=cur->left;
?????cur->left=temp->right;
?????temp->right=cur;
?????cur->height=max（Height（cur->left）Height（cur->right））+1;
?????temp->height=max（Height（temp->left）Height（temp->right））+1;
?????return?temp;
}
?
AvlNode*?AvlTree::RRchange（AvlNode*?cur）//RR旋轉操作
{
????AvlNode?*?temp=cur->right;
????cur->right=temp->left;
????temp->left=cur;
?
????cur->height=max（Height（cur->left）Height（cur->right））+1;
????temp->height=max（Height（temp->left）Height（temp->right））+1;
????return?temp;
}
?
AvlNode*?AvlTree::LRchange（AvlNode*?cur）??//LR旋轉操左
{
?????cur->left=RRchange（cur->left）;
?????return?LLchange（cur）;
}
?
AvlNode*?AvlTree::RLchange（AvlNode?*?cur）
{
????cur->right=LLchange（cur->right）;
????return?RRchange（cur）;
}
?
AvlNode*?AvlTree::Insert（AvlNode?*?curUserInfo?va）
{
	?if（cur==NULL）?//如果到底了，那么創建新的節點
?????{
?????????cur=new?AvlNode（va）;
?????????return?cur;
?????}
?????if（cur->val==va）?return?cur;//有相同的
?????if（cur->val>va）
?????{
?????????cur->left=Insert（cur->leftva）;//注意這里是cur->left=???請認真思考為什么這么寫
?????????if（Height（cur->left）-Height（cur->right）==2）//插入后看是否平衡，如果不平衡顯然是插入的那一邊高度大
?????????{
??????????????if（valeft->val）//判斷是LL還是LR即插入的是left節點的left?還是right
??????????????????cur=LLchange（cur）;
??????????????else
??????????????????cur=LRchange（cur）;
?????????}
?????}
?????else//同理
?????{
????????cur->right=Insert（cur->rightva）;
????????if（Height（cur->right）-Height（cur->left）==2）
????????{
????????????if（va>cur->right->val）

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????6544??2019-01-10?11:31??用戶登入系統\AvlTree.cpp

?????文件???????1630??2019-01-05?11:27??用戶登入系統\AvlTree.h

?????文件?????257795??2019-01-10?11:31??用戶登入系統\AvlTree.o

?????文件??????12517??2019-01-10?10:31??用戶登入系統\Interface.cpp

?????文件????????986??2019-01-05?07:44??用戶登入系統\Interface.h

?????文件?????972863??2019-01-10?10:31??用戶登入系統\Interface.o

?????文件????????159??2019-01-05?08:52??用戶登入系統\main.cpp

?????文件?????934751??2019-01-10?10:31??用戶登入系統\main.o

?????文件???????1328??2019-01-10?11:31??用戶登入系統\Makefile.win

?????文件????????147??2019-01-10?11:34??用戶登入系統\Test.txt

?????文件???????1085??2019-01-05?08:56??用戶登入系統\UserInfo.cpp

?????文件????????862??2019-01-05?10:42??用戶登入系統\UserInfo.h

?????文件??????86518??2019-01-10?10:31??用戶登入系統\UserInfo.o

????..A..H.???????162??2019-04-07?22:04??用戶登入系統\~$登入系統實驗報告.docx

?????文件???????1624??2019-01-10?11:34??用戶登入系統\項目1.dev

?????文件????4010017??2019-01-10?11:31??用戶登入系統\項目1.exe

?????文件????????418??2019-01-10?11:34??用戶登入系統\項目1.layout

?????目錄??????????0??2019-04-07?22:18??用戶登入系統

?????文件????1811089??2019-04-07?22:04??用戶登入系統\用戶登入系統實驗報告.docx

-----------?---------??----------?-----??----

??????????????8100495????????????????????19