算法类问题

#include 
#include
using namespace std;
int main()//木棒三角形 有n根木棍 挑出其中三根构成直角三角形 输出面积最大的三角形面积 输入n再输入每根三角形长度,n> len[i];
		double ans = -1;
		for (int i = 0; i  ans)
							ans = 0.5 * len[i] * len[j];
					}
				}
		if (ans == -1)
			cout 

/顺序查找 从第一个开始查找 关键字与给定值相比较 如果相等则退出
	int order(int array[], int n, int key)
	{
		int i;
		array[n] = key;//监视哨
		for (i = 0; array[i] != key; i++);//分号不可少
		return (i 

int binarysearch(int array[], int key, int n)
{
	int left = 0;
	int right = n - 1;
	while (left  array[middle])
			left = middle + 1;
		if (right 

int n,x,k;
int k[100];
bool binary(int x){
int l = 0,r = n;
while(r - l>=1)
{
int i = (r+l)/2;
if(k[i] == x)return true;
else if(k[i] 

using namespace std;
struct abc
{
	 char str[20];
	///int num;
}que[20000];
int cmp(const void* a, const void* b)
{
	abc* f1 = (abc*)a;
	abc* f2 = (abc*)b;
	return strcmp(f1->str, f2->str);//排序函数用于在qsort函数中将字符串从小到大排序 可以根据cmp的写法来确定从大到小还是从小到大
}
//qsort函数的基本用法：qsort(que,n,sizeof(que[0]),cmp)que为需要排序的序列首地址
//n为序列的元素 sizeof为序列中单个元素所占空间的大小 cmp为排序过程中用到的比较函数 有-1、0、1三种返回值
int main()
{
	int count[20000];//存放种类数 其中[]中的数值是重复的次数
	int n;
	int number = 1;
	while (cin >> n)
	{
		for (int i = 0; i >que[i].str;
			
			count[i] = 0;
		}


		qsort(que, n, sizeof(que[0]), cmp);
		如果后一个元素等于前一个元素则出现次数加一
		int i = 1;
		//while(i 

//求解组合问题 1~n中任取r个数 求所有组合
//输出一个组合
int r;//全局变量
void display(int a[])
{
	for (int i = 0; i = r; i--)
	{
		a[r - 1] = i;
		if (r > 1)
			mm(a, i - 1, r - 1);
		else
			display(a);
	}
}
		




int main() {

	int n;
	int a[8];
	
	cin >> n >> r;
	mm(a, n, r);

}

using namespace std;
//n皇后问题
//每个皇后不能同行不能同列且不能同对角线
const int N = 20;//最多的皇后数
int q[N];//存放皇后的列好 i是行数q[i]是列数即第i个皇后所在的列号place(k,n)是指【已经在1~k-1行上
//放好了k-1个皇后，现要在k~n上放n-k+1个皇后，则place（k+1,n）指已经在1~k行上放了k个皇后，要在k+1~n行
//放n-k个皇后 即place(k+1,n)比place(k,n)少放一个皇后，前者是小问题，后者是大问题
//当同对角线时 即等腰直角三角形 行的绝对值之差=列的绝对值之差
//本代码i从1开始取，最大下标是n
int ccount = 0;//解的个数
void display(int n)
{
	ccount++;
	cout  n)
		display(n);//此时所有皇后放置结束
	else
	for (int j = 1; j > n;
	place(1, n);
}

//设计算法尽可能高效地将所有奇数元素移动到偶数元素前面
//设置两个指针 ij i=0,j = n-1,当ij不相等时循环 a[i]找偶数元素 a[j]找奇数元素 当i!=j时发生交换

void swapp(int a[], int n)
{
	int i = 0, j = n - 1;
	int temp;
	while (i != j)
	{
		j--;
		if (a[j] % 2 == 1)
		{
			for (; i != j; i++)
			{
				if (a[i] % 2 == 0 && a[j] % 2 == 1 && i != j)
				{
					temp = a[i];
					a[i] = a[j];
					a[j] = temp;
					i++;
					break;

				}
			}
		}

	}
}
int main()
{

	m1 = 3;
	int m[] = { 1,2,3,4,4,5,6 };
	swapp(m, 7);
	for (int i = 0; i 

//以a[0]为基准将所有大于a[0]的元素移到该基准后面 小于等于的元素移到该基准前面 得到一个新的数组
void swapp(int a[], int n)
{
	int temp;
	int num = a[0];
	int j = n - 1;//a[j]扫描小于a[0]的 a[i]扫描大于a[0]的 两者发生交换
	int i = 0;
	while (i != j) 
	{
		j--;
		if(a[j] = num)
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				i++;
				break;

				
			}
		}
	}
}

//删除一个已排序好的整数数组的重复元素 返回a[](算法效率问题)
//重建法
int* delee(int a[], int n)
{
	int k = 0;
	for (int i = 0; i 

#include
using namespace std;
int* delee(int a[], int& n)
{
	//删除给定的有序整数数组 两个或两个以上的 重复元素仅仅保留两个
	int k = 0;
	int b[30] = { 0 };
	for (int i = 0; i 

//采用二路归并产生升序数组，用i从a[m-1]的元素开始向前扫描 j从前向后扫描 k=m+n-1指向最后一个位置
void shengxu(int a[], int m,int b[], int n)
{
	int l = 0;
	int r = m - 1;
	int k = m+n-1;
	while (r >= 0 && l  a[r])//如果b更大
		{
			a[k] = b[l];
			k--;
			l++;
		}
		else
		{
			a[k] = a[r];
			r--;
			k--;

		}
		while (r >= 0)//此时a的前半部分没有扫完
		{
			a[k] = a[r];
			k--;
			r--;
		}
		while (l 

//采用二路归并产生升序数组，用i从a[m-1]的元素开始向前扫描 j从前向后扫描 k=m+n-1指向最后一个位置
bool shengxu(int a[], int m,int b[], int n)
{
	int i = 0, j = 0;
	while (i  b[j])
			j++;
		else
			i++;

	}
	return false;
}

//油田问题 一个油田是由m*n个单元组成的矩形，有些里面有石油，一个采油机可以把与该单元油田相连的油田采完，问至少
//需要多少台采油机
//@表示有石油
//采用深度优先搜索算法 设变量many表示采油机 把整个地图搜索完毕 当遇到没有标号的油田时用深度优先搜索把与这块油田相连
//的其他油田全部进行标号
#include 

using namespace std;
int dfs(int i, int j);
int mmap[55][55] = { 0 };
char s[50][50] = { '0' };
int main()
{
	int m, n;
	cin >> m >> n;
	
	for(int i = 0;i > s[i][j];
		}
	int many = 0;
	for (int i = 0; i 

//求一个a矩阵以（i,j)和(m,n)为对角线的子矩阵元素之和
int a[][100];
void sum(int a[][100], int b[][100], int m, int n)
{
    b[0][0] = a[0][0];
    for (int i = 1; i 

//创建一个n阶螺旋矩阵并输出
//对于左上角（ix,iy)右下角(ex,ey)起始元素为start的那一圈，通过调用函数1产生 函数2用于创建整个螺旋矩阵
//设f(x,y,start,n)用于创建左上角为(x,y)起始元素为start的n阶螺旋矩阵，是大问题，则f(x+1,y+1,start,n-2)是小问题
//（去掉最外面一大圈后剩下的部分）
//有递归算法和非递归算法
int a[15][15] = { 0 };
void create(int& start,int ix,int iy,int ex,int ey)//最外面的大圈
{
    if (ix == ex)
        a[ix][iy] = start++;//当该圈只有一个元素时
    else
    {
        int curl = iy;
        while (curl != ey)
            a[ix][curl++] = start ++;
        curl = ix;
        while (curl != ex)
            a[curl++][ey] = start++;
        curl = ey;
        while (curl != iy)
            a[ex][curl--] = start++;
        curl = ex;
        while (curl != ix)
            a[curl--][iy] = start++;
    }
    
}
void spira(int x,int y,int n,int start)//递归调用螺旋矩阵
{
    if (n  y; i--)//下一行
            a[x + n-1][i] = start++;
        for (int i =x+ n-1; i > x; i--)//左一列
            a[i][y] = start++;
        spira(x+1,y + 1, n-2,start);//递归调用自身
    }

}
void spira2(int n)//非递归调用螺旋矩阵
{
    int start = 1;
  
        int i = 0, j = 0, ex = n - 1, ey = n - 1;
        while (i 

//设a-b的元素数组为c
int a[5], b[5];
int c[8] = { 0 };
void chaji(int m,int n,int a[],int b[])
{
    int i = 0, k = 0, j = 0;//k来维护c中元素个数
    while (i  b[j])//如果b中元素更小则跳过
        {
            j++;
        }
        else//如果元素相等 不能放入C中 下标加一
        {
            i++;
            j++;
        }
    }
        while (i 

示例如下：



#include   
  
struct node {  
    int data;  
    struct node *next;  
};  
  
int main(void)  
{  
    struct node *head, first, second;  
  
    head = &first;  
    first.data = 1;  
    first.next = &second;  
      
    second.data = 2;  
    second.next = NULL;  
      
    while (head) {  
        printf("%dn", head->data);  
        head = head->next;  
    }  
    return 0;  
}

1.单链表的初始化，即建立一个空链表。
[plain] view plain copy


//不带头结点的单链表的初始化  
void LinkedListInit1(LinkedList L)  
{  
  L=NULL;  
}  
//带头结点的单链表的初始化  
void LinkedListInit2(LinkedList L)  
{  
  L=(LNode *)malloc(sizeof(LNode));  
  if(L==NULL)  
  {  
    printf("申请空间失败！");  
    exit(0);  
  }  
  L->next=NULL;  
}

struct node *root = &head;

struct linklist
{
	int data;
	linklist* next;
};
void shanchu(linklist* p)
{
	linklist* head = new linklist;
	p = head->next;
linklist* L = head;//p的前驱结点
	int max = p->data;
	while (p != NULL)//查找最大的结点
	{
		p = p->next;
		if (p->data > max)
			max = p->data;
	}
	p = head->next;
	while (p != NULL)
	{
		if (p->data == max)
		{
			L->next = p->next;
			delete p;
			p = L->next;//让p继续指向L结点的后继结点
		}
		else
		{
			L = p;
			p = p->next;//L和p都同时前移
		}
	}
}

struct linknode
{
	int data;
	linknode* next;
};
void guibing(linknode* &L1, linknode* &L2, linknode*& L3)
{
	linknode* p1 = L1->next,*p2 = L2->next,*p3;
	delete L1;//释放L1头结点并置为NULL
	delete L2;
	L1 = NULL;
	L2 = NULL;
	L3 = new linknode;
	L3->next = NULL;
	while (p1 != nullptr && p2 != nullptr)
	{
		if (p1->data > p2->data)
		{
			p3 = p1->next;//临时保存p1结点的后继结点
			p1->next = L3->next;//采用头插法将p1插入到L3中
			L3->next = p1;
			p1 = p3;//p1指向下一个结点
		}
		else
		{
			p3 = p2->next;
			p2->next = L3->next;
			L3->next = p2;
			p2 = p3;
		}
	}
	if (p2 != nullptr)
	{
		p1 = p2;//如果p2没有扫完 让p1指向p2结点
	}
	while (p1 != nullptr)
	{
		p3 = p1->next;//临时保存p1结点的后继结点
		p1->next = L3->next;//采用头插法将p1插入到L3中
		L3->next = p1;
		p1 = p3;//p1指向下一个结点
	}
}

struct linknode
{
	int data;
	linknode* next;
};
//注意下面这个函数参数是值参数(对应的实参不变）而不是引用参数。如果改为引用是错误的
linknode* nizhi(linknode* first)//first为不带头结点的
{
	linknode* p;
	if (first == nullptr || first->next == nullptr)
		return first;
	p = nizhi(first->next);
    first->next->next = first;//first结点连接到first->next结点的后面 注意二者顺序
	first->next = NULL;//first结点作为逆置后的尾结点
	return p;
}
//引用作为参数
void nizhi1(linknode* &L)//L为带头结点的单链表
{
	L->next = nizhi(L->next);//L->next为不带头结点的单链表 调用第一个函数
}

struct linknode
{
	int data;
	linknode* next;
};
//逆置非空单链表中序号从i到j的结点
//为了防止i与j超过范围要先求出长度 且第二个函数为bool型
int length(linknode* m)
{
	int k = 0;
	linknode* p = m;
	while (p != nullptr)
	{
		p = p->next;
		k++;
	}
	return k;//先求出单链表长度
}
bool nizhiij(linknode* &L,int i,int j)
{
	linknode* r;
	int len = length(L);
	if (i  len || j  len)
		return false;
	else
	{
		int n = 0;
		linknode* p = L,*q;
			
		while (n next;
		}//p为第i-1个结点
		linknode* m = p;
		linknode*r = p->next;
		p1 = r;//用p1保存逆置的第一个结点
		p->next = NULL;//断开第i和第i-1个结点
		while (n next;//不断将r结点到第j个结点采用头插法插入到m结点之后
			r->next = m->next;
			m->next = r;
			r = q;
		}
		p1->next = q;//将第j个结点的后继结点接到p1结点之后
		return true;

	}
}

void yidong(linknode* a)
{
	linknode* p = a->next;//p指向首结点
	int data1 = p->data;//cache指向其后继结点 如果cache值小于p值 通过p将cache删除
	linknode* cache = p->next;
	if (a != nullptr || a->next == nullptr)
		return;
	while (cache != nullptr)
	{

		int da2 = cache->data;//da2存放基准值
		if (da2 >= data1)//此时p和cache同步后移
		{
			p = cache;
			cache = p->next;
		}
		else
		{
			p->next = cache->next;//如果cache结点的值小于基准值 删除cache结点 头插法查到表a中
			cache->next = a->next;
			a->next = cache;
			cache = p->next;//cache继续指向p结点的后继结点
		}
	}
}

//方法：用快慢两个指针 快指针一次移动两个结点 循环结束后slow指向的结点即目标结点
linknode* middle(linknode* L)
{
	if (L == nullptr)
		return NULL;
	if (L->next == nullptr)
		return L;
	linknode* fast = L->next,*slow = L->next;
	while (fast != nullptr && fast->next != nullptr)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;

}

//空间复杂度为O(1)
//采用尾插法 建立新表L r作为尾指针 利用上一题求中间结点的函数找到中间结点
void rearrange(linknode* &L)
{
	if (L == NULL)
		return;
	linknode* mid = middle(L);//此题结点个数是偶数
	linknode* r = L;//新链表的尾结点
	linknode* p = r->next;//p指向结点a1
	linknode* q = mid->next;//q指向结点b1
	while (p != nullptr && q != nullptr)
	{
	
		r->next = p;//p结点链接到新链表的表尾
		r = p;
		r->next = q;
		r = q;
		p = p->next;
		q = q->next;

	}
	r->next = NULL;//尾结点的指针域置空（尽管这里不需要，但这是一个好习惯）

}

//非递归算法 找到中间结点 后半部分构成带头结点的单链表p 将p逆置 然后依次按照结点顺序判断数据是否相等

bool ispal(linknode* L)
{
	if (L->next == nullptr || L->next->next == nullptr)
		return true;
	linknode *q,*q2,* p = new linknode;
	linknode* mid = middle(L);//中间结点
	p->next = mid->next;//将后半部分结点构成带头结点的单链表
	
	reverse(p);//逆置带头结点的单链表
	mid->next = p->next;//重新连接
	q = p->next;
	q2 = L->next;
	while (q != nullptr && q2 != mid->next)
	{
		if (q->data !=q2->data)
			return false;
		q = q->next;
		q2 = q2->next;
	}
	return true;
}

//先在A中找到与B结点值相等的结点pa,pb指向B的首结点然后比较值是否相等 相等则同步后移
bool subseq(linknode* A, linknode* B)
{
	linknode* pa = A->next;
	
	while (pa != nullptr)
	{
		linknode* pb = B->next;//每次循环开始pb都是指向B的首结点
		while(pa->next != nullptr && pa->data != pb->data)//只用来求出与B第一个结点相等的A中结点pa 
			
		{
			pa = pa->next;
			
		}
		linknode* q = pa;//用q来保存pa  ,以便pa进行下一轮循环（如果进入下一轮循环仍要匹配A中与B第一个结点相等的其他结点）
		while (q != nullptr && pb != nullptr && q->data == pb->data)
		{
			q = q->next;//如果值相等同步移动
			pb = pb->next;
	}
			if (pb == nullptr)
				return true;
			else if(pa->next != nullptr)//如果A序列没有遍历完 ，则从下一个结点开始重复进行
			{
				pa = pa->next;
			}
		
	}
	return false;
}

reverse(p);//逆置带头结点的单链表
mid->next = p->next;//重新连接
q = p->next;
q2 = L->next;
while (q != nullptr && q2 != mid->next)
{
	if (q->data !=q2->data)
		return false;
	q = q->next;
	q2 = q2->next;
}
return true;

## 9.判断序列B是否是A序列的子序列

```c++
//先在A中找到与B结点值相等的结点pa,pb指向B的首结点然后比较值是否相等 相等则同步后移
bool subseq(linknode* A, linknode* B)
{
	linknode* pa = A->next;
	
	while (pa != nullptr)
	{
		linknode* pb = B->next;//每次循环开始pb都是指向B的首结点
		while(pa->next != nullptr && pa->data != pb->data)//只用来求出与B第一个结点相等的A中结点pa 
			
		{
			pa = pa->next;
			
		}
		linknode* q = pa;//用q来保存pa  ,以便pa进行下一轮循环（如果进入下一轮循环仍要匹配A中与B第一个结点相等的其他结点）
		while (q != nullptr && pb != nullptr && q->data == pb->data)
		{
			q = q->next;//如果值相等同步移动
			pb = pb->next;
	}
			if (pb == nullptr)
				return true;
			else if(pa->next != nullptr)//如果A序列没有遍历完 ，则从下一个结点开始重复进行
			{
				pa = pa->next;
			}
		
	}
	return false;
}

#define max(a,b) ( (a) > (b) ? (a) : (b)) //求a b中最大值的宏 

using namespace std;
typedef struct node {
	char data;
	struct node* lchild;
	struct node* rchild;//指向右孩子结点
}btnode;
//求非空二叉树最大距离，即二叉树中相距最远的结点之间的距离
// 注意最大距离并非一定经过根结点
//以b为根结点的二叉树最大距离只有三种情况：b左/右子树中到根结点的最大距离，b的左子树结点中到根结点的最大距离+b的右子树结点中到根结点的最大距离
int maxdistance(btnode* b, int &maxleft, int &maxright )
{
	if(b == NULL)
	{
		maxleft = 0;
		maxright = 0;
		return 0;//二叉树为空 
	}
	int maxll, maxlr, maxRL, maxRR;
	int maxdisleft, maxdisright;//分别表示左右子树中的最大距离 
	if(b -> lchild == NULL)
	{
		maxdisleft = 0;
		maxleft = 0;
	}
	else
	{
		//左子树非空
		maxdisleft = maxdistance( b -> lchild, maxll, maxlr );
		maxleft = max( maxll, maxlr ) + 1; //左子树结点中到根结点的最大距离 注意从根节点到左子树结点之间还有距离1要加上 
	}
	if(b -> rchild != NULL)
	{
		maxdisright = 0;
		maxright = 0;
	}
	else
	{
		maxdisright = maxdistance(b -> rchild,maxRL,maxRR);
		maxright = max(maxRL, maxRR) + 1;
	}
	return max(max(maxdisright, maxdisleft), maxright + maxleft);
	
}

//每个结点储存一个整数，求从根结点到叶结点路径上所有结点之和等于sum的路径 
void disppath(vector path)
{
	vector:: iterator ite;
	for( ite = path.begin(); ite != path.end(); ite++)
	{
		cout path)
{
	if(b == NULL) return;
	path.push_back(b->data);
	if(b -> lchild == NULL && b -> rchild == NULL)
	{
		if(b -> data == sum)
		disppath(path);
	}
	//如果左子树右子树并非都空
	allpathsum(b->lchild,sum - b->data, path);//左右子树中查找 
	allpathsum(b->rchild, sum- b->data, path) ;
	
	
}

//每个结点储存一个整数，对于一个给定的的结点值x,输出所有从x到根结点的逆路径 
//逆路径用栈保存
void display(stackpath)//输出一条逆路径 
{
	while(!path.empty())
	{
		coutpath)
 {
 	if(b == NULL) return;
 	path.push(b->data);//注意要先将b的值推入栈中再进行判断 因为值为x的结点也要输出 
 	if(b->data == x)//当找到一个为x的结点，逆向输出 
 	display(path);
 	allpath(b->lchild,x,path);
 	allpath(b->rchild,x,path);//在左右子树中查找 
 }

//给定二叉树求其中最大的路径和（即该路径上所有结点值之和）可以以任意结点作为起点和终点
//用ans表示二叉树b中最大路径和，考虑以任何一个结点b为根的子树，求出其左子树的最大路径和l，右子树最大路径和r，1 若b为空，对应最大路径和为0
//若ldata) 以b为根的子树的最大路径和为max(0,max(l,r))+b->data

#define max(a,b) ((a) > (b) ? (a) : (b))
#define inf 32767
int maxpathnum(btnode *b,int &ans)
{
	if(b == NULL) return 0;
	int l = maxpathnum(b->lchild, ans);
	int r = maxpathnum(b->rchild, ans);
	ans = max(ans, max(0,l) + max(0, r) + b->data);
	return max(max(l, r) ,0) + b->data;//该返回值用于递归调用 求解左右子树最大路径和 

}

int solve(btnode* b)
{
	int ans = -inf;//初始为负无穷
	maxpathnum(b, ans);
	return ans; 
}
	btnode *pa, *pb, *pc, *pd, *pe, *pg, *pf, *ph;
		btnode* creat()
		{
			pa = new btnode;pa->data = 2;
			pb = new btnode;pb->data = 3;
			pc = new btnode;pc->data = 1;
			pd = new btnode;pd->data = -1;
			pe = new btnode;pe->data = 4;
			pg = new btnode;pg->data = -6;
			pf = new btnode;pf->data = 6;
			ph = new btnode;ph->data = 20;
			pa->lchild = pb; pa->rchild = pc;
			pb->lchild = pd; pb->rchild = pe;
			pc->lchild = pg; pc->rchild = pf;
			pd->lchild = NULL; pd->rchild = NULL;
			pe->lchild = NULL; pe->rchild = NULL;
			pf->lchild = NULL; pf->rchild = NULL;
			pg->lchild = NULL; pg->rchild = ph;
			ph->lchild = NULL;ph->rchild = NULL;//这句话一定要写 经过调试如果这句话没有则无输出 所以一定要设置ph左右子树为空 
			return pa;			
		}
	void clear()
		{
			//销毁二叉树
			delete pa;
			delete pb;
			delete pc;
		 		delete pe;
	 		delete pd;
			 			 			delete pf;
			 				delete pg;
		}
int main()
{
	
btnode*m = creat();
cout 

//给定二叉树 二叉树中寻找路径和为某一个值的所有路径 路径从根结点出发 temsum存放临时和（初始为0） 
vectorpath;
void display(vector path)
{
	for(int i = 0;i datapath)
{
	if(b == NULL) return;
	path.push_back( b );
	if(temsum + b->data == sum) display(path);
	findpath(b->lchild,sum , temsum + b->data,path);
	findpath(b->rchild,sum, temsum + b->data, path);
	
}
	btnode *pa, *pb, *pc, *pd, *pe, *pg, *pf, *ph;
		btnode* creat()
		{
			pa = new btnode;pa->data = 2;
			pb = new btnode;pb->data = 3;
			pc = new btnode;pc->data = 1;
			pd = new btnode;pd->data = -1;
			pe = new btnode;pe->data = 4;
			pg = new btnode;pg->data = -6;
			pf = new btnode;pf->data = 6;
			ph = new btnode;ph->data = 20;
			pa->lchild = pb; pa->rchild = pc;
			pb->lchild = pd; pb->rchild = pe;
			pc->lchild = pg; pc->rchild = pf;
			pd->lchild = NULL; pd->rchild = NULL;
			pe->lchild = NULL; pe->rchild = NULL;
			pf->lchild = NULL; pf->rchild = NULL;
			pg->lchild = NULL; pg->rchild = ph;
			ph->lchild = NULL;ph->rchild = NULL;//这句话一定要写 经过调试如果这句话没有则无输出 所以一定要设置ph左右子树为空 
			return pa;			
		}
	void clear()
		{
			//销毁二叉树
			delete pa;
			delete pb;
			delete pc;
		 		delete pe;
	 		delete pd;
			 			 			delete pf;
			 				delete pg;
		}
int main()
{
	
btnode*m = creat();
int tmp = 0;
findpath(m, 9, tmp, path);
 }

//先序和层次遍历两种方法
#include
using namespace std;
#define maxn 100
typedef struct node {
	char data;
	struct node* lchild;
	struct node* rchild;
	node* next;
}btnode;
//假设一颗二叉树 在每个结点中增加一个next指针，用于指向同一层的右兄弟或者堂兄弟，如图所示，设计一个算法实现这种 转化
void trans(btnode* b, btnode* sibling)
{
	//先序遍历，用sibling指向当前结点b的兄弟 若b不空，修改其next指针指向sibling
	if (b == nullptr) return;
	else
		b->next = sibling;//如果b不空，修改b的next 
	trans(b->lchild, b->rchild);//递归处理左子树，b左子树的兄弟为b右子树
	if (sibling != nullptr)
	{
		trans(b->rchild, sibling);//当前结点b的兄弟不为空时 右孩子的next改为兄弟的左孩子
	}
	else
		trans(b->rchild, nullptr);//如果当前结点b的兄弟为空，右孩子的next为空
}
//层次遍历方式，按照h = 1,2,3...处理，将每一层的k个结点放到lnode数组中，当一层遍历完毕后，将lnode数组中的结点用next指针链接
typedef struct
{
	int lno;//结点的层次
	btnode* p;//结点指针
}qytype;//队列元素类型
void process(btnode* lnode[], int k)
{
	for (int i = 0; i next = lnode[i + 1];
	lnode[k - 1]->next = NULL;
}
void trans2(btnode* b)
{
	btnode* lnode[maxn];//用于存放一层的所有结点 其中下标表示的是层 lnode[i]是第i层的结点个数
	queuequ;
	btnode* tem;
	int k=0;//k记录lnode中结点个数
	if (b == nullptr) return;
		qytype m;
		m.p = b;
		m.lno = 1;
		qu.push(m);
		int h = 1;//从第一层开始
	while (!qu.empty())
	{
		qytype tt = qu.front();
		qu.pop();
		tem = tt.p;
		if (tt.lno == h)
		{
			lnode[k] = tem;//如果该结点是第h层，则将该结点存入lnode中
			k++;//结点个数加一

		}
		else
		{
			//如果该结点不属于第h层 则输出上一层的所有结点
			process(lnode, k);
			k = 0; h++;//结点个数清空 层数加一
			lnode[k] = tem;//该层第一个结点是tem
			k++;//结点个数加一
		}
		if (tt.p->lchild != nullptr)//p结点有左孩子 将其进队
		{
			tem = tt.p->lchild;
			tt.lno = tt.lno + 1;
			qu.push(tt);
		}
		if (tt.p->rchild != nullptr)//有右孩子 进队
		{
			tem = tt.p->rchild;
			tt.lno = tt.lno + 1;
			qu.push(tt);
		}
	}
	process(lnode, k);;//处理最后一层的所有结点的next指针 注意实在while循环的外面

}

//给定一个二叉树及其两其中的两个node(地址均非空） 给出这两个node的一个公共父节点，使得这个父节点
//与两个结点的路径之和最小
 struct treenode
{
	 treenode* left;//指向左右子树
	 treenode* right;
	 treenode* father;//指向父节点
};//二叉树采用三叉链存储结构，根结点的father为NULL,求两个非空结点first second的层次，比较两个层次大小
 //通过Father指针将它们的指针移到相同层次，然后查找公共祖先结点
#define max(x,y) ((x) > (y)?(x):(y))
 int level(treenode* p)
 {
	 int l = 1;
	 if (p->father != nullptr)
	 {
		 p = p->father;
		 l++;
	 }
	 return l;
 }
 treenode* lowestcommom(treenode* first, treenode* second)
 {
	 int i;
	 if (first == nullptr || second == nullptr) return nullptr;
	 int l1 = level(first);
	 int l2 = level(second);
	 if (l1 father;//如果Second层次更大 则second在first下面部分
	 }
	 else if (l1 > l2)
	 {
		 for (int i = 0; i father;
	 }
	 while (first != second)
	 {
		 first = first->father;
		 second = second->father;
	 }
	 return first;
 }

//编写函数 树中每一个结点放一个整数 函数返回这棵二叉树中相差最大的两个结点间差的绝对值
 //通过一次先序遍历求出最大结点指max和最小结点指min 返回abs(max - min)
 void maxmin(btnode* p, int& max, int& min)
 {
	 //求最大最小值的函数
	 if (p == nullptr) return;
	 if (p->data > max)
		 max = p->data;
	 if (p->data data;
	 maxmin(p->lchild, max, min);
	 maxmin(p->rchild, max, min);//递归处理左右子树
 }
 int fun(btnode* b)
 {
	 if (b == nullptr) return 0;
	 int max, min;
	 max = min = b->data;//初始化最大最小值
	 maxmin(b, max, min);
	 return abs(max - min);
 }

//以二叉链存储的二叉树 设计算法用递归实现输出二叉树的层次遍历
//采用一个全局两层向量result存放先序遍历结果 只是按结点b的层次h将其存放在result[h-1]向量元素中，然后
//一层一层输出result即构成层次遍历序列

vector>result;
void travel(btnode* b, int h)
{
	if (b == NULL) return;
	if (h > result.size())
	{
		result.push_back(vector());
	}
	result[h - 1].push_back(b->data);
	travel(b->lchild, h + 1);
	travel(b->rchild, h + 1);
 
}
void levelorder(btnode* b)
{
	travel(b, 1);
	for (int i = 0; i 

//设计算法释放二叉树
//只能用后序遍历，不能前序或者中序，因为只有将子树空间释放后才能释放根结点的空间，否则会丢失子树
void deletetree(btnode* b)
{
	if (b != nullptr)
	{
		deletetree(b->lchild);
		deletetree(b->rchild);
		delete b;
	}
}

int main()
{
	int i, j;
	int n, m, k[50];
	cin >> n >> m;
	bool nn = false;
	for (i = 0; i > k[i];
	for (int a = 0; a 

void solve() {
//计算最短时间
int minT = 0；
for (int i = 0； i