//AVL（自動平衡二叉樹）
#include?“stdafx.h“
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
#define?MaxSize?100
typedef?int?ElemType;
//每個結點的平均值
struct?Keytype		//關鍵數據類型
{
	char?id[19];
	char?name[11];
	char?address[21];
	char?phone[12];
};

typedef?enum
{
	EH?=?0
	LH?=?1
	RH?=?-1
}bh_t;

typedef?enum
{
	FALSE?=?0
	TRUE?=?1
}bool_t;

//定義平衡二叉樹
typedef?struct?BSTNode
{
	Keytype?key;
	int?bf;								//平衡值
	struct?BSTNode?*lchild?*rchild;
}BSTNode?*BSTree;

typedef?struct
{
	BSTree?data[MaxSize];
	int?top;
}SqStack;

BSTree?root?=?NULL?r;
int?n;

//判斷棧空函數
bool?StackEmpty（SqStack?*s）
{
	return?（s->top?==?-1）;
}

//初始化棧
void?InitStack（SqStack?*&?s）
{
	s?=?（SqStack?*）malloc（sizeof（SqStack））;
	s->top?=?-1;
}

//進棧
bool?Push（SqStack?*&?s?BSTree?e）
{
	if?（s->top?==?MaxSize?-?1）
		return?false;
	s->top++;
	s->data[s->top]?=?e;
	return?true;
}

//退棧
bool?Pop（SqStack?*&s?BSTree?&e）
{
	if?（s->top?==?-1）
		return?false;
	e?=?s->data[s->top];
	s->top--;
	return?true;
}

//中序遍歷
void?InOrderTraverse（BSTree?root）
{
	if?（NULL?!=?root）
	{
		InOrderTraverse（root->lchild）;
		cout?<key.name?<key.id?<key.address?<key.name?<		InOrderTraverse（root->rchild）;
	}
}

//右旋轉
void?R_Rotate（BSTree?*p）
{
	BSTree?lc?=?（*p）->lchild;
	（*p）->lchild?=?lc->rchild;
	lc->rchild?=?*p;
	*p?=?lc;
}

//左旋轉
void?L_Rotate（BSTree?*p）
{
	BSTree?rc?=?（*p）->rchild;
	（*p）->rchild?=?rc->lchild;
	rc->lchild?=?*p;
	*p?=?rc;
}

//左平衡旋轉
void?LeftBalance（BSTree?*T）
{
	BSTree?lc?=?（*T）->lchild;
	BSTree?rd?=?lc->rchild;
	//判斷進行向哪邊旋轉
	switch?（lc->bf）
	{
	case?LH:
		（*T）->bf?=?lc->bf?=?EH;
		R_Rotate（T）;
		break;
	case?RH:
		switch?（rd->bf）
		{
		case?LH:
			（*T）->bf?=?RH;
			lc->bf?=?EH;
			break;
		case?EH:
			（*T）->bf?=?lc->bf?=?EH;
			break;
		case?RH:
			（*T）->bf?=?EH;
			lc->bf?=?LH;
			break;
		}
		rd->bf?=?EH;
		L_Rotate（&（（*T）->lchild））;
		R_Rotate（T）;
		break;
	}
}

//右平衡旋轉
void?RightBalance（BSTree?*T）
{
	BSTree?rc?=?（*T）->rchild;
	BSTree?ld?=?rc->lchild;
	switch?（rc->bf）
	{
	case?RH:
		（*T）->bf?=?rc->bf?=?EH;
		L_Rotate（T）;
		break;
	case?LH:
		switch?（ld->bf）
		{
		case?RH:
			（*T）->bf?=?LH;
			rc->bf?=?EH;
			break;
		case?EH:
			（*T）->bf?=?rc->bf?=?EH;
			break;
		case?LH:
			（*T）->bf?=?EH;
			rc->bf?=?RH;
			break;
		}
		ld->bf?=?EH;
		R_Rotate（&（（*T）->rchild））;
		L_Rotate（T）;
		break;
	}
}

//插入元素
bool_t?InsertAVL（BSTree?*t?Keytype?e?bool_t?*taller）		//二叉樹插入算法
{
	if?（NULL?==?t）
		return?FALSE;
	if?（NULL?==?*t）
	{
		*t?=?（BSTree）malloc（sizeof（BSTNode））;
		if?（NULL?==?*t）
			return?FALSE;
		（*t）->key?=?e;
		（*t）->lchild?=?（*t）->rchild?=?NULL;
		（*t）->bf?=?EH;
		*taller?=?TRUE;
	}
	else
	{
		if?（e.id?==?（*t）->key.id）
		{
			*taller?=?FALSE;
			return?FALSE;
		}
		if?（e.id

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

?????文件?????????22??2018-02-22?17:12??身份證信息管理系統\f2.dat

?????文件??????16924??2018-02-18?23:21??身份證信息管理系統\身份證信息管理系統.cpp

?????文件?????741567??2018-08-31?23:03??身份證信息管理系統\身份證信息管理系統.docx

?????文件????2582494??2018-02-22?18:42??身份證信息管理系統\身份證信息管理系統.rar

?????目錄??????????0??2018-08-31?23:03??身份證信息管理系統

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

??????????????3341007????????????????????5