算法思想：每次先從前往后冒泡，當(dāng)一次往后之后再?gòu)暮笸懊芭菀槐?，并且每次冒泡后都需要更新上下?/p>

void bubble2(int a[], int n)//交替
{?	int low = 0, high = n - 1;
?	bool flag = true;//一趟冒泡后記錄元素是否發(fā)生交換的標(biāo)志，若沒(méi)有發(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ù)進(jìn)行拆分，直至拆到最小再進(jìn)行排序合并。首先選取第一個(gè)數(shù)作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個(gè)過(guò)程稱(chēng)為一趟快速排序，之后遞歸直至所有元素排完。

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];								//將表第一個(gè)元素設(shè)置為中心點(diǎn)	
while (low< high)
?	{?		while (low< high && a[high] >= pivot)  --high;		//先從后往前找第一個(gè)小于pivot的位置
?		a[low] = a[high];							//更新
?		while (low< high && a[low]<= pivot)  ++low;		//再?gòu)那巴笳业谝粋€(gè)大于pivot的位置
?		a[high] = a[low];							//更新
?	}
?	a[high] = pivot;								//pivot放入，這時(shí)high=low
?	return high;
}

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

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)造成一個(gè)大頂堆，此時(shí)，整個(gè)序列的大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。

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為根的子樹(shù)進(jìn)行調(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é)點(diǎn)
?		if (a[0] >a[i])        break;	//若較大的子結(jié)點(diǎn)小于k，則不用再比
?		else
?		{?			a[k] = a[i];				//若子結(jié)點(diǎn)小于k，則和子結(jié)點(diǎn)互換
?			k = i;					//指向k的新位置，以便繼續(xù)向下篩選
?		}
?	}
?	a[k] = a[0];						//被篩選的值放在最終位置
}
void heapsort(int a[ ], int n)
{?	buildmaxheap(a, n);				//初始建堆
?	for (int i = n; i >1; i--)				//將堆頂和最后一個(gè)結(jié)點(diǎn)互換，放到其排序的位置
?	{?		Swap(a[1],a[i]);				//互換
?		headadjust(a, 1, i - 1);			//i-1之后的已經(jīng)有序，只用排之前的
?	}
}

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

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

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

void MergeSort(int a[], int low, int high)	//合并兩個(gè)有序的子序列
{?	if (low< high)
?	{?		int mid = (low + high) / 2;	//從中劃分成兩個(gè)子序列
?		MergeSort(a, low, mid);		//對(duì)左側(cè)進(jìn)行歸并排序
?		MergeSort(a, mid + 1, high);	//對(duì)右側(cè)進(jìn)行歸并排序
?		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]合并成一個(gè)有序序列
{?	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++]; 	//若沒(mé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];					//頂點(diǎn)表
	int Edge[Max_Vexnum] [Max_Vexnum];		//鄰接矩陣，邊表
	int vexnum,arcnum;					//頂點(diǎn)數(shù)和邊數(shù)
}MGraph;

②鄰接表法

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

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

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

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

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

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

算法思想：因?yàn)锽FS算法是以根開(kāi)始廣度優(yōu)先遍歷

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

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

bool visited[max_vex_num];					//訪問(wèn)標(biāo)記數(shù)組
void DFSTraverse(Graph G)
{?	for (int i = 0; i< G.Vexnum; i++)
?		visited[i] = false;					//初始化訪問(wèn)標(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的尚未訪問(wèn)的鄰接頂點(diǎn)
?		if (!visited[w])
?			DFS(G, w);
}

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

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

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

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

①雙棧法

算法思想：用兩個(gè)棧來(lái)存儲(chǔ)，1.先將根結(jié)點(diǎn)入棧1；2.出棧頂元素入站2，依次將左右子樹(shù)入棧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)		//左右子樹(shù)入棧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.棧頂元素出棧，若其右孩子不空且未被訪問(wèn)過(guò)，則右孩子入棧執(zhí)行1；否則棧頂元素出棧訪問(wèn)并且標(biāo)記。因?yàn)楹笮虮闅v，當(dāng)前結(jié)點(diǎn)若右子樹(shù)存在，則當(dāng)前結(jié)點(diǎn)的前驅(qū)為其右孩子

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

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

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

①非遞歸（層序遍歷）

算法思想：設(shè)置標(biāo)記層數(shù)的depth和一個(gè)指向下一行最后一個(gè)結(jié)點(diǎn)的指針p。1.根入隊(duì)，設(shè)置p=rear2.隊(duì)頭出隊(duì)并將左右子樹(shù)入隊(duì)，若當(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)建隊(duì)列和輔助指針p
?	int front = 0, rear = 0;
?	Q[rear++] = T;					//根入隊(duì)
?	int depth = 0, tag = rear;			//下一層最后一個(gè)為rear=1
?	while (front< rear)				//隊(duì)非空
?	{?		p = Q[front++];				//隊(duì)頭出隊(duì)
?		if (p->lchild)	Q[rear++] = p->lchild;
?		if (p->rchild)	Q[rear++] = p->rchild;
?		if (front == tag)				//當(dāng)遍歷完當(dāng)前行最后一個(gè)后
?		{?			depth++;				//層數(shù)增加并更新標(biāo)記最后結(jié)點(diǎn)的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;
}

①非遞歸（簡(jiǎn)化）

用5①的非遞歸，當(dāng)發(fā)現(xiàn)所查結(jié)點(diǎn)時(shí)輸出depth+1（因?yàn)檫@時(shí)當(dāng)前行還沒(méi)運(yùn)行完，depth還沒(méi)有+1）

while (front< rear)				//隊(duì)非空
{?	p = Q[front++];	//隊(duì)頭出隊(duì)
?	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)前行最后一個(gè)后
?	{?		depth++;				//層數(shù)增加并更新標(biāo)記最后結(jié)點(diǎn)的tag
?		tag = rear;
?	}
}

②遞歸

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

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)（簡(jiǎn)化）

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

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

②遞歸

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

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

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

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

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

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

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

算法思想：1.若結(jié)點(diǎn)為空則返回0；2.若結(jié)點(diǎn)度為2則返回1+左右子樹(shù)度為2的結(jié)點(diǎn)之和；3.否則返回左子樹(shù)和右子樹(shù)葉子結(jié)點(diǎn)的和。遞歸調(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);	//返回左右子樹(shù)的度為2的結(jié)點(diǎn)個(gè)數(shù)和+1
?	else return Degree2(T->lchild) + Degree2(T->rchild);		//否則當(dāng)前結(jié)點(diǎn)不是度為2，結(jié)點(diǎn)數(shù)不+1
}

算法思想：1.若結(jié)點(diǎn)為空則返回0；2.若結(jié)點(diǎn)度為2則返回1+左右子樹(shù)度為2的結(jié)點(diǎn)之和；3.否則返回左子樹(shù)和右子樹(shù)葉子結(jié)點(diǎn)的和。遞歸調(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);
}

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

算法思想：因?yàn)橄刃虻谝粋€(gè)是根結(jié)點(diǎn)，后續(xù)最后一個(gè)是根結(jié)點(diǎn)，并且滿二叉樹(shù)的任意一個(gè)結(jié)點(diǎn)的左右子樹(shù)均有相等的結(jié)點(diǎn)數(shù)，所以將先序的第一個(gè)放到后續(xù)的最后一個(gè)，再將先序除第一個(gè)結(jié)點(diǎn)的剩下所有結(jié)點(diǎn)分成兩份繼續(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é)點(diǎn)；若樹(shù)中存在相同的值則返回0；若小于結(jié)點(diǎn)的值則插入到左子樹(shù)中；若大于結(jié)點(diǎn)的值則插入到右子樹(shù)

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

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

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

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

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

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

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è)置二叉樹(shù)的平衡標(biāo)記balance，標(biāo)記返回二叉樹(shù)T是否為平衡二叉樹(shù)，若為平衡二叉樹(shù)則返回1，否則返回0；h為二叉樹(shù)T的高度。采用后序遍歷的遞歸算法：

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

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

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

T的高度為最高的子樹(shù)的高度+1.

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

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

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

①定長(zhǎng)順序存儲(chǔ)

typedef struct SString  selected選定
{char ch[Max_Size];	//每個(gè)分量存儲(chǔ)一個(gè)字符
	int length;			//串的實(shí)際長(zhǎng)度
}SString;

②堆分配存儲(chǔ)

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

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

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

void get_next(String T, int next[])
{?	int i = 1, j = 0;				//i表示next的位置
?	next[1] = 0;					//初始化第一個(gè)值
?	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)//此時(shí)j=T.length+1；因?yàn)樯厦嬉徊綍?huì)j++
?		return i - T.length;//匹配成功
?	else
?		return 0;
}

①順序存儲(chǔ)

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

②鏈?zhǔn)酱鎯?chǔ)：入棧和出棧在對(duì)頭進(jìn)行

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

①順序存儲(chǔ)

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

②鏈?zhǔn)酱鎯?chǔ)

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

①順序存儲(chǔ)

靜態(tài)分配：

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

②堆分配存儲(chǔ)

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

②鏈?zhǔn)酱鎯?chǔ)

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

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

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

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

廣告

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