算法思想：每次先從前往后冒泡，當(dāng)一次往后之后再從后往前冒泡一遍，并且每次冒泡后都需要更新上下界

void bubble2(int a[], int n)//交替
{?	int low = 0, high = n - 1;
?	bool flag = true;//一趟冒泡后記錄元素是否發(fā)生交換的標(biāo)志，若沒有發(fā)生則表示已經(jīng)有序
?	while (low< high&&flag)
?	{?		flag = false;//每次排序初始化flag為false
?		for (int i = low; i< high; i++)//從前往后冒泡
?			if (a[i] >a[i + 1])//大的往后
?			{?				swap(a[i], a[i + 1]);
?				flag = true;
?			}
?		high--;//更新上界
?		for (int i = high; i >low; i--)//從后往前冒泡
?			if (a[i]< a[i - 1])//小的往前
?			{?				swap(a[i], a[i - 1]);
?				flag = true;
?			}
?		low++;//更新下界
?	}
}

算法思想：使用分治算法的思想，將數(shù)據(jù)進行拆分，直至拆到最小再進行排序合并。首先選取第一個數(shù)作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個過程稱為一趟快速排序，之后遞歸直至所有元素排完。

void QuickSort(int a[] , int low , int high) 					//分治拆分，遞歸
{?	if (low< high)
?	{?		int pivotpos = Partition(a,low,high);
?		QuickSort(a, low, pivotpos - 1);
?		QuickSort(a, pivotpos + 1, high);
?	}
}

int Partition(int a[], int low, int high)						//從表的兩端交替向中間掃描，一趟劃分
{?	int pivot = a[low];								//將表第一個元素設(shè)置為中心點	
while (low< high)
?	{?		while (low< high && a[high] >= pivot)  --high;		//先從后往前找第一個小于pivot的位置
?		a[low] = a[high];							//更新
?		while (low< high && a[low]<= pivot)  ++low;		//再從前往后找第一個大于pivot的位置
?		a[high] = a[low];							//更新
?	}
?	a[high] = pivot;								//pivot放入，這時high=low
?	return high;
}

算法思想：每次都從序列后的n-i+1個元素中選出最小的元素與該元素組的第1個元素交換，即與整個序列的第i個元素交換。依此類推，直至i=n-1為止。也就是說，每一趟排序從未排好順序的那些元素中選擇一個最小的元素，然后與這些未排好序的元素的第一個元素互換

void SelectSort(int a[], int n)
{?	int min;
?	for (int i = 0; i< n; i++)
?	{?		min = i;					//記錄最小元素位置
?		for (int j = i + 1; j< n; j++)		//找最小
?			if (a[min] >a[j])   min = j;	//更新最小元素位置
?		if (min != i)					//若i不是最小的元素，則互換
?			Swap(a[min] , a[j])
?	}
}

算法思想：將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的大值就是堆頂?shù)母?jié)點。將其與末尾元素進行交換，此時末尾就為大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了。

void buildmaxheap(int a[], int n)			//創(chuàng)建大根堆
{?	for (int i = len / 2; i >0; i--)			//從n/2~1販反復(fù)調(diào)整堆
?		headadjust(a, i, n);
}
void headadjust(int a[ ], int k, int n)			//將元素k為根的子樹進行調(diào)整
{?	a[0] = a[k];
?	for (int i = 2 * k; i<= n; i *= 2)		//一層一層向下
?	{?		if (i< n&&a[i]< a[i + 1])  i++;	//取key較大的子結(jié)點
?		if (a[0] >a[i])        break;	//若較大的子結(jié)點小于k，則不用再比
?		else
?		{?			a[k] = a[i];				//若子結(jié)點小于k，則和子結(jié)點互換
?			k = i;					//指向k的新位置，以便繼續(xù)向下篩選
?		}
?	}
?	a[k] = a[0];						//被篩選的值放在最終位置
}
void heapsort(int a[ ], int n)
{?	buildmaxheap(a, n);				//初始建堆
?	for (int i = n; i >1; i--)				//將堆頂和最后一個結(jié)點互換，放到其排序的位置
?	{?		Swap(a[1],a[i]);				//互換
?		headadjust(a, 1, i - 1);			//i-1之后的已經(jīng)有序，只用排之前的
?	}
}

算法思想：使用分治算法的思想。使用遞歸方法來實現(xiàn)歸并排序時，核心思想是兩個有序子序列的合并，注意這里是有序子序列的合并，因此下面要做兩件事，整個過程：

(1)將待排序序列從中間一分為二，對左右兩邊再進行遞歸分割操作，得到n個相互獨立的子序列；

(2)對n個獨立的子序列遞歸的執(zhí)行合并操作，最終得到有序的序列。

void MergeSort(int a[], int low, int high)	//合并兩個有序的子序列
{?	if (low< high)
?	{?		int mid = (low + high) / 2;	//從中劃分成兩個子序列
?		MergeSort(a, low, mid);		//對左側(cè)進行歸并排序
?		MergeSort(a, mid + 1, high);	//對右側(cè)進行歸并排序
?		Merge(a, low, mid, high);	//將[low-mid]和[mid+1-high]歸并
?	}
}
int *b = (int*)malloc(n*sizeof(int));				 //輔助函數(shù)b
void Merge(int a[], int low, int mid, int high) 	 	 //將序列[low-mid]和[mid+1-high]合并成一個有序序列
{?	int i = low, j = mid + 1, k = low;
?	for (int p = low; p<= high; p++)  b[p] = a[p];	 //將a[ ]中元素都復(fù)制到b[ ]中
?	while (i<= mid && j<= high)			   //合并放入a[ ]
?	{?		if (b[i]< b[j]) a[k++] = b[i++];		 //將小的放入
?		else			a[k++] = b[j++];
?	}
?	while (i<= mid)	 a[k++] = b[i++]; 	//若沒有排完添加到后面
?	while (j<= high) a[k++] = b[j++];
}

算法思想：查找全部元素，若找到則輸出，未找到則輸出-1

int Search(int a[], int n, int x)
{?	for (int i = 0; i< n; i++)
?		if (a[i] == x)  return i;
?	return -1;
}

算法思想：當(dāng)當(dāng)前元素小于關(guān)鍵字則向后找，若大于關(guān)鍵字或者遍歷完，則返回-1

int Search(int a[], int n, int x)
{?	for (int i = 0; i< n ***\*&& a[i] >x\****; i++)
?		if (a[i] == x) return i;
?	return -1;
}

算法思想：將表分為兩部分，關(guān)鍵字和中間的元素比較，若小于則在左邊查找，若大于則在右邊查找，直至找到，若未找到返回-1

int BSearch(int a[], int n, int x)
{?	int low = 0, high = n - 1, mid;
?	while (low<= high)
?	{?		mid = (low + high) / 2;
?		if (a[mid] == x)	return mid;
?		if (a[mid] >x)	high = mid - 1;	//從前半部分找
?		else			low = mid + 1;	//從后半部分找
?	}
?	return -1;
}

①鄰接矩陣

typedef struct MGraph{	char Vex[Max_VexNum];					//頂點表
	int Edge[Max_Vexnum] [Max_Vexnum];		//鄰接矩陣，邊表
	int vexnum,arcnum;					//頂點數(shù)和邊數(shù)
}MGraph;

②鄰接表法

typedef struct ArcNode{//邊表結(jié)點
	int adjvex;							//改弧指向的頂點位置
	struct ArcNode *next;					//指向下一條弧的指針
}ArcNode;

typedef struct VNode{//頂點表結(jié)點
	char data;							//頂點信息
	ArcNode *first;						//指向第一條依附該頂點的弧的指針
}VNode, AdjList[Max_VexNum];				

typedef struct ALGraph{//是以鄰接表存儲的圖類型
	AdjList vertices;						//鄰接表
	Int vexnum,arcnum;					//圖的頂點數(shù)和弧數(shù)
}ALGraph;

算法思想：類似樹的層序遍歷，1.訪問完當(dāng)前頂點的所有鄰接點。2.訪問當(dāng)前已在集合內(nèi)的頂點的鄰接點（鄰接點不包括已在集合內(nèi)的）

bool visited[max_vex_num];					//訪問標(biāo)記數(shù)組
void BFSTraverse(Graph G)
{?	for (int i = 0; i< G.Vexnum; i++)
?		visited[i] = false;					//初始化訪問標(biāo)記數(shù)組
?	for (int j = 0; j< G.Vexnum; j++)			//從0號開始遍歷
?		if (!visited[j])						//對每一連通分量調(diào)用一次BFS
?			BFS(G, j);
}

void BFS(Graph G, int v)						//從頂點v出發(fā)開始廣度優(yōu)先遍歷
{?	int p;
?	int Q[G.Vexnum];					//建立隊列（和DFS的差別就是這個隊）
?	int front = 0, rear = 0;				//初始化隊列
?	visit(v);							//訪問初始結(jié)點
?	visited(v) = true;						//標(biāo)記訪問
?	Q[rear++] = v;						//入隊
?	while (front!=rear)						//隊列非空
?	{?		p =Q[front++];				//頂點出隊
?		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
//檢測v所有鄰接點
?			if (!visited[w])				//若w為v尚未訪問的鄰接點
?			{?				visit(w);			//訪問結(jié)點
?				visited(w) = true;			//標(biāo)記訪問
?				Q[rear++] = w;		//入隊
?			}
?	}
}

算法思想：因為BFS算法是以根開始廣度優(yōu)先遍歷

bool visited[max_vex_num];					//訪問標(biāo)記數(shù)組
void BFS_Min_Distance(Graph G, int u)			//d[i]表示從u到i結(jié)點的最短路徑
{?	visited[u] = true;						//初始化根結(jié)點
?	d[u] = 0;
?	for (i = 0; i< G.vexnum; i++)				//初始化路徑長度
?		d[i] = ∞;
?	int Q[G.vexnum];						//創(chuàng)建隊列
?	int front = 0, rear = 0, x ;				//初始化隊列
?	Q[rear++] = u;						//u入隊
?	while (front != rear)
?	{?		x = Q[front++];					//出隊
?		for (int w = FirstNeighbor(G, x); w >= 0; w = NextNeighbor(G, x, w))
?			if (!visited[w])
?			{?				visited[w] = true;
?				d[w] = d[u]+1;			//路徑長度+1
?				Q[rear++] = w;
?			}
?		
?	}
}

算法思想：類似樹的先序。首先訪問圖中某一起始點v，然后由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點w1，再訪問與w1鄰接且未被訪問的任一頂點w2，重復(fù)上述操作。當(dāng)不能繼續(xù)向下訪問時，退回到最近被訪問的頂點，若它還有鄰接點未被訪問，則從該頂點繼續(xù)上述搜索過程，直至圖中所有結(jié)點都被訪問。

bool visited[max_vex_num];					//訪問標(biāo)記數(shù)組
void DFSTraverse(Graph G)
{?	for (int i = 0; i< G.Vexnum; i++)
?		visited[i] = false;					//初始化訪問標(biāo)記數(shù)組
?	for (int i = 0; i< G.Vexnum; i++)
?		if (!visited[i])
?			DFS(G, i);
}

void DFS(Graph G, int v)
{?	visit(v);
?	visited[v] = true;
?	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
//w為u的尚未訪問的鄰接頂點
?		if (!visited[w])
?			DFS(G, w);
}

void Track(BiTree p)
{if(p)
	{//1.先序
    Track(p->lchild);
    //2.中序
    Track(p->rchild);
    //3.后序
    }	
}

算法思想（先序）：1.沿著根的左孩子，依次入棧并訪問，直到孩子為空。2.棧頂元素出戰(zhàn)，并開始遍歷右子樹

算法思想（中序）：1.沿著根的左孩子，依次入棧，直到孩子為空。2.棧頂元素出棧并訪問，并開始遍歷右子樹

void Order(BiTree T)
{?	if (T)
?	{?		BiTNode *Stack[Max_Size];		//建棧并初始化
?		int top = -1;
?		BiTNode *p = T;
?		while (top != -1 || p != NULL)		//棧非空并且樹未遍歷完時
?		{?			if (p)
?			{?				//1.先序
?				Stack[++top] = p;		//入棧
?				p = p->lchild;		//遍歷左子樹
?			}
?			else
?			{?				p = Stack[top--];		//出棧
?				//2.中序
?				p = p->rchild;		//遍歷右子樹
        	}	
        }	
    }	
}

①雙棧法

算法思想：用兩個棧來存儲，1.先將根結(jié)點入棧1；2.出棧頂元素入站2，依次將左右子樹入棧1。重復(fù)操作2直至棧1為空，再將所有棧2元素出棧

void Post_order(BiTree T)
{?	if (!T)	 return;
?	BiTNode * stack1[Max_Size], * stack2[Max_Size];
?	int top1 = -1, top2 = -1;
?	BiTNode * p;
?	stack1[++top1] = T;	 //根入棧1
?	while (top1 != -1)
?	{?		p = stack1[top1--];//1棧頂元素出棧入棧2
?		stack2[++top2] = p;
?		if (p->lchild)		//左右子樹入棧1
?			stack1[++top1] = p->lchild;
?		if (p->rchild)
?			stack1[++top1] = p->rchild;
?	}//while end
?	while (top2 != -1)			//棧2所有元素出棧
?	{?		p = stack2[top2--];
?		visit(p);
	}	
}

②單棧標(biāo)記法

算法思想：1.沿著根的左孩子，依次入棧，直至左孩子為空；2.棧頂元素出棧，若其右孩子不空且未被訪問過，則右孩子入棧執(zhí)行1；否則棧頂元素出棧訪問并且標(biāo)記。因為后序遍歷，當(dāng)前結(jié)點若右子樹存在，則當(dāng)前結(jié)點的前驅(qū)為其右孩子

void Post_order(BiTree T)
{?	BTNode *stack[Max_Size];				//建棧并初始化
?	int top = -1;
?	BTNode *p = T, *r = NULL;				//r指向最近訪問的點
?	while (top != -1 || p != NULL)				//棧非空或樹未遍歷完時
?	{?		if (p)							//走到最左邊
?		{?			stack[++top] = p;				//入棧
?			p = p->lchild;				//遍歷左子樹
?		}
?		else							//向右
?		{?			p = stack[top--];				//出棧
?			if (p->rchild && p->rchild != r)	//若右子樹存在并且未被訪問
?			{?				stack[++top] = p;			//再次入棧，因為還沒訪問完
?				p = p->rchild;			//遍歷右子樹
?			}
?			else						//否則，彈出結(jié)點并訪問
?			{?				visit(p);				//執(zhí)行結(jié)點
?				r = p;					//標(biāo)記結(jié)點
?				p = NULL;				//指針設(shè)為空，因為要返回雙親結(jié)點
?			}
?		}
?	}
}

算法思想：借助隊列,1.將根結(jié)點入隊。2.出隊并將其左右子樹（若存在）依次入隊。重復(fù)2，直至隊空

void Level_order(BiTree T)
{?	if (!T) return;
?	BTNode* Q[10];			//初始化隊
?	int front = 0, rear = 0;
?	BTNode *p = NULL;
?	Q[rear++] = T;
?	while (front< rear)		//隊非空
?	{?		p = Q[front++];		//出隊
?		visit(p);
?		if (p->lchild)		//左右子樹入隊
?			Q[rear++] = p->lchild;
?		if (p->rchild)
?			Q[rear++] = p->rchild;
?	}
}

①非遞歸（層序遍歷）

算法思想：設(shè)置標(biāo)記層數(shù)的depth和一個指向下一行最后一個結(jié)點的指針p。1.根入隊，設(shè)置p=rear2.隊頭出隊并將左右子樹入隊，若當(dāng)前行已經(jīng)遍歷完即front=tag，則層數(shù)+1并且更新p=rear。

int Tree_Depth2(BiTree T)
{?	if (T == NULL)	return 0;
?	BiTree Q[Max_Size], p;			//創(chuàng)建隊列和輔助指針p
?	int front = 0, rear = 0;
?	Q[rear++] = T;					//根入隊
?	int depth = 0, tag = rear;			//下一層最后一個為rear=1
?	while (front< rear)				//隊非空
?	{?		p = Q[front++];				//隊頭出隊
?		if (p->lchild)	Q[rear++] = p->lchild;
?		if (p->rchild)	Q[rear++] = p->rchild;
?		if (front == tag)				//當(dāng)遍歷完當(dāng)前行最后一個后
?		{?			depth++;				//層數(shù)增加并更新標(biāo)記最后結(jié)點的tag
?			tag = rear;
?		}
?	}
?	return depth;
}

②遞歸

int Tree_Depth(BiTree T)
{?	if (T == NULL)
?		return 0;
?	int ldepth = Tree_Depth(T->lchild);
?	int rdepth = Tree_Depth(T->rchild);
?	if (ldepth >rdepth)
?		return ldepth+1;
?	else
?		return rdepth+1;
}

①非遞歸（簡化）

用5①的非遞歸，當(dāng)發(fā)現(xiàn)所查結(jié)點時輸出depth+1（因為這時當(dāng)前行還沒運行完，depth還沒有+1）

while (front< rear)				//隊非空
{?	p = Q[front++];	//隊頭出隊
?	if (p == x) return depth + 1;	//若找到則返回深度
?	if (p->lchild)	Q[rear++] = p->lchild;
?	if (p->rchild)	Q[rear++] = p->rchild;
?	if (front == tag)				//當(dāng)遍歷完當(dāng)前行最后一個后
?	{?		depth++;				//層數(shù)增加并更新標(biāo)記最后結(jié)點的tag
?		tag = rear;
?	}
}

②遞歸

思想：若當(dāng)前結(jié)點為空則返回0；若找到該結(jié)點則返回該結(jié)點的層數(shù)；遍歷左右子樹，若左右子樹大于0則表示找到了，返回左/右子樹的返回值

int Level(BTree T, BTNode* p, int depth)
{if(!T) return 0;
    if(T==p)  return depth;
    int L = Level(T->lchild, p, depth+1);
    if(L>0)  return L;			//即找到了
    int R = Level(T->lchild, p, depth+1);
    if(R>0)  return R;			//即找到了
    return -1;					//未找到
}

①非遞歸int Width_Depth(BiTree T)（簡化）

算法思想：利用5①的非遞歸遍歷，在遍歷每一行的時候都計算下一行的個數(shù)count=front-rear

int count=1, width=1;				//count表示下一行的結(jié)點個數(shù)，max表示樹的寬度(大count)
?	while (front< rear)				//隊非空
?	{?		p = Q[front++];	//隊頭出隊
?		if (p->lchild)	Q[rear++] = p->lchild;
?		if (p->rchild)	Q[rear++] = p->rchild;
?		if (front == tag)						//當(dāng)遍歷完當(dāng)前行最后一個后
?		{tag = rear;
width= rear - front;				//計算當(dāng)前行的個數(shù)
?			if (width>max)		max = width;	//更新大width
?		}
?	}
?	return width;	//返回width

②遞歸

算法思想：開辟一個數(shù)組count[二叉樹高度],遍歷每一個節(jié)點,然后根據(jù)當(dāng)前節(jié)點所在層次i,則執(zhí)行count[i]++;最后遍歷完求出大的count即為二叉樹寬度

int count[10];
int Max = -1;
void FindWidth(BiTree T, int k)
{?	if (!T)	return;
?	count[k]++;						//k層結(jié)點數(shù)+1
?	if (Max< count[k])	Max = count[k];		//更新大的count
?	FindWidth(T->lchild, k + 1);			//遍歷左右子樹
?	FindWidth(T->rchild, k + 1);
}

①算法思想：使用層序遍歷，但是在每次將左右子樹入隊時改為右左的順序入隊

②遞歸：算法思想：先序遍歷（中序也可）左右子樹，并且每次遍歷將左右子樹互換

void swap(BiTree T)
{   BiTree q;		//左右子樹互換
?	q = T->lchild;
?	T->lchild = T->rchild;
?	T->rchild = q;	
    swap(T->lchild);//遞歸交換左右孩子的左右子樹
?	swap(T->rchild);	
}

算法思想：1.若結(jié)點為空則返回0；2.若結(jié)點為葉子結(jié)點則返回1；3.否則返回左子樹和右子樹葉子結(jié)點的和。遞歸調(diào)用

int Degree0(BiTree T)
{?	if (!T)	return 0;
?	if (T->lchild == NULL && T->rchild == NULL)	return 1;	//若為葉子結(jié)點，返回1
?	else return Degree0(T->lchild) + Degree0(T->rchild);		//否則返回左右子樹葉子數(shù)相加
}

算法思想：1.若結(jié)點為空則返回0；2.若結(jié)點度為2則返回1+左右子樹度為2的結(jié)點之和；3.否則返回左子樹和右子樹葉子結(jié)點的和。遞歸調(diào)用

int Degree2(BiTree T)
{?	if (!T)	return 0;
?	if (T->lchild != NULL && T->rchild != NULL)			//若度為2，則		
return 1+ Degree2(T->lchild) + Degree2(T->rchild);	//返回左右子樹的度為2的結(jié)點個數(shù)和+1
?	else return Degree2(T->lchild) + Degree2(T->rchild);		//否則當(dāng)前結(jié)點不是度為2，結(jié)點數(shù)不+1
}

算法思想：1.若結(jié)點為空則返回0；2.若結(jié)點度為2則返回1+左右子樹度為2的結(jié)點之和；3.否則返回左子樹和右子樹葉子結(jié)點的和。遞歸調(diào)用

int Degree1(BiTree T)
{?	if (!T)	return 0;
?	if (T->lchild != NULL && T->rchild == NULL)	
?		return 1+ Degree1(T->lchild) + Degree1(T->rchild);
else if (T->lchild == NULL && T->rchild != NULL)	
?	return 1+ Degree1(T->lchild) + Degree1(T->rchild);
?	else return Degree1(T->lchild) + Degree1(T->rchild);
}

算法思想：后序遍歷當(dāng)找到任意一個時保存當(dāng)前棧中的元素，若兩個都找到后退出循環(huán)并遍歷找公共組先

BTNode* PrintParents_qp(BiTree T, BTNode *x,BTNode *y)
{?	if (!T) return NULL;
?	BTNode *stack[10], *a[10], *b[10], *p = T, *r = NULL;//初始化棧
?	int top = -1, pa = 0, pb = 0;
?	while (top != -1 || p != NULL)				//棧非空或樹未遍歷完
?	{?		if (p)							//走到最左邊
?		{?			if (p == x)					//若找到x，則保存此時的棧
?			{?				for (int i = 0; i<=top; i++)
?					a[i] = stack[i];
?				pa = top;
?			}
?			if (p == y)					//若找到y(tǒng)，則保存此時的棧
?			{?				for (int i = 0; i<= top; i++)
?					b[i] = stack[i];
?				pb = top;
?			}			
stack[++top] = p;
?			p = p->lchild;
?		}
?		else
?		{?			p = stack[top--];//出棧
?			if (p->rchild&&p->rchild != r)	//若右子樹并且未遍歷
?			{?				stack[++top] = p;		//再把結(jié)點入棧并退出循環(huán)
?				p = p->rchild;		//右子樹入棧
?			}
?			else					//否則直接繼續(xù)循環(huán)
?			{?				r = p;
?				p = NULL;
?			}
?		}
?	}
?	//找公共祖先
?	int i=0;
?	for(i=0; a[i] == b[i]&&i<=pa&&i<=pb;i++) //找第一個不同的點
?	return a[i - 1];//返回前驅(qū)
}

算法思想：因為先序第一個是根結(jié)點，后續(xù)最后一個是根結(jié)點，并且滿二叉樹的任意一個結(jié)點的左右子樹均有相等的結(jié)點數(shù)，所以將先序的第一個放到后續(xù)的最后一個，再將先序除第一個結(jié)點的剩下所有結(jié)點分成兩份繼續(xù)執(zhí)行上述操作。

void pre_post1(int pre[], int a1, int a2, int post[], int b1, int b2)
{?	int half;
?	if (a1<= a2)//若pre[]的首和尾位置合法
?	{?		post[b2] = pre[a1];
?		half = (a2 - a1) / 2;
?		pre_post(pre, a1 + 1, a1 + half, post, b1, b1 + half - 1);
?		pre_post(pre, a1 + half + 1, a2, post, b1 + half, b2-1);
?	}
}

算法思想：若根為空將要插入的值設(shè)置為根節(jié)點；若樹中存在相同的值則返回0；若小于結(jié)點的值則插入到左子樹中；若大于結(jié)點的值則插入到右子樹

int BST_Insert(BiTree &T, int key)//二叉樹插入操作，因為會改變樹所以用&T
{?	if (T == NULL)	//原樹為空，新插入的記錄為根節(jié)點
?	{?		T = (BTNode *)malloc(sizeof(BTNode));
?		T->data = key;
?		T->lchild = T->rchild = NULL;
?		return 1;	//返回1，插入成功
?	}
?	else if (T->data == key)//若樹中存在相同關(guān)鍵字，則插入失敗
?		return 0;
?	else if (T->data >key)	//插入到T的左子樹中
?		return BST_Insert(T->lchild, key);
?	else					//插入到T的右子樹中
?		return BST_Insert(T->rchild, key);
}

算法思想：若等于結(jié)點的值或結(jié)點為空則返回結(jié)點；若小于結(jié)點的值則搜索左子樹；若大于結(jié)點的值則搜索右子樹

BTNode * BST_Search(BiTree T, int key)//非遞歸查找算法
{?	while (T&&T->data != key)//若樹非空或不等于結(jié)點值
?	{?		if (key< T->data)	T = T->lchild;//若小于則向左查找
?		else	T = T->rchild;	//若大于則向右查找
?	}
?	return T;
}

算法思想：通過二叉樹的插入算法，將數(shù)組中的所有結(jié)點都依次插入到二叉排序樹中

void Creat_BST(BiTree &T, int str[], int n)//構(gòu)造二叉樹
{?	T = NULL;	//初始時T為空樹
?	int i = 0;
?	while (i< n)	//依次將數(shù)組中的關(guān)鍵字插入到二叉排序樹中
?	{?		BST_Insert(T, str[i]);
?		i++;
?	}
}

算法思想：若當(dāng)前結(jié)點小于左子樹或者小于右子樹則返回false，若為空返回true，否則返回左右子樹相與

bool Decide(BiTree T)
{?	if (!T)	return true;
?	if (T->lchild&&T->lchild->data >T->data)	return false;
?	if (T->rchild&&T->rchild->data< T->data)	return false;
?	return Decide(T->lchild) && Decide(T->lchild);
}

算法思想:設(shè)置二叉樹的平衡標(biāo)記balance，標(biāo)記返回二叉樹T是否為平衡二叉樹，若為平衡二叉樹則返回1，否則返回0；h為二叉樹T的高度。采用后序遍歷的遞歸算法：

①若T為空，則高度為0，balance=1；

②若T為僅有根結(jié)點（即葉子結(jié)點），則高度為1，balance=1；

③否則，對T的左右子樹進行遞歸操作，返回左右子樹的高度和平衡標(biāo)記，

T的高度為最高的子樹的高度+1.

若左右子樹的高度差大于1，則balance=0；

若左右子樹的高度差小于等于1，*且左右子樹都平衡時*，balance=1，否則balance=0.

void Judge_AVL(BiTree T, int &balance, int &h)//加上取地址符
//balance返回是否是平衡二叉樹，若是則返回1，否則返回0；h是二叉樹的高度
{?	int bl = 0, br = 0, hl = 0, hr = 0;		//左右子樹的平衡標(biāo)記和高度
?	if (!T) //空樹，高度為0
?	{?		h = 0;
?		balance = 1;
?	}
?	else if (T->lchild == NULL && T->rchild == NULL)
?	{	//若為根結(jié)點，則高度為1
?		h = 1;
?		balance = 1;
?	}
?	else
?	{?		Judge_AVL(T->lchild, bl, hl);	//判斷左子樹
?		Judge_AVL(T->rchild, br, hr);	//判斷右子樹
?		h = (hl >hr ? hl : hr) + 1;
?			balance = bl&&br;		//若左右子樹都平衡時，二叉樹平衡
?		else
?			balance = 0;
?	}
}

①定長順序存儲

typedef struct SString  selected選定
{char ch[Max_Size];	//每個分量存儲一個字符
	int length;			//串的實際長度
}SString;

②堆分配存儲

typedef struct HString  heap堆
{char * ch;			//按串長分配存儲區(qū)，ch指向串的基地址
	int length;			//串的實際長度
}HString;

③塊鏈存儲(eg大小為1的鏈表)

typedef struct LString
{char data;			//按串長分配存儲區(qū)，ch指向串的基地址
	struct LString *Next;	//指向下一個結(jié)點
}LString;

void get_next(String T, int next[])
{?	int i = 1, j = 0;				//i表示next的位置
?	next[1] = 0;					//初始化第一個值
?	while (i< T.length)
?	{?		if (j == 0 || T.c[i] == T.c[j])	
?		{?			next[++i] = ++j;		//若pi=pj，則next[j+1]=next[j]+1
?		}
?		else
?			j = next[j];			//否則令j=next[j]，循環(huán)繼續(xù)
?	}
}

int KMP(String S, String T, int next[])
{?	int i = 1, j = 1;
?	while (i< S.length&&j< T.length)
?	{?		if (j == 0 || S.c[i] == T.c[j])
?		{?			i++; j++;
?		}
?		else
?			j = next[j];
?	}
?	if (j >T.length)//此時j=T.length+1；因為上面一步會j++
?		return i - T.length;//匹配成功
?	else
?		return 0;
}

①順序存儲

typedef struct Stack		//順序棧
{?	int data[Max_Size];	//值域
?	int top;			//棧頂指針
}Stack;

②鏈?zhǔn)酱鎯Γ喝霔：统鰲Ｔ趯︻^進行

typedef struct LStack		//鏈?zhǔn)疥犃?{?	int data;			//值域
?	struct LStack *Next;	//指針域
}LStack;

①順序存儲

typedef struct Queue		//順序隊列的結(jié)點
{?	int data[Max_size];		//值域
?	int front, rear;			//隊頭指針和隊尾指針
}Queue;

②鏈?zhǔn)酱鎯?/p>

typedef struct LinkNode		//鏈?zhǔn)疥犃械慕Y(jié)點
{?	int data;				//值域
?	struct LinkNode *Next;	//指針域
}LinkNode;
typedef struct LQueue		//鏈?zhǔn)疥犃?{?	struct LinkNode *front, *rear;	//隊列的頭結(jié)點和尾結(jié)點
}LQueue;

①順序存儲

靜態(tài)分配：

typedef struct SqList
{int data[Max_Size];	//順序表元素
	int length;			//表長度
}SqList;

②堆分配存儲

typedef struct SqList
{int * data;			//動態(tài)分配數(shù)組的指針
	int length;			//表長度
}SqList;

②鏈?zhǔn)酱鎯?/p>

typedef struct LNode	//單鏈表
{?	int data;			//值域
?	struct LNode *Next;	//指針域
}LNode;

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：考研心得：考研數(shù)據(jù)結(jié)構(gòu)算法大全-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://www.chinadenli.net/article26/doepjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計、建站公司、做網(wǎng)站、品牌網(wǎng)站制作、網(wǎng)站制作、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)