void Qsort(int A[], int L, int R) {
    if(L > R) return; //递归终止
    int M = huafen(A, L, R);
    Qsort(A, L, M-1); //左半部分快排
    Qsort(A, M+1, R); //右半部分快排
}

int hualen(int A[], int L, int R) {
    int mid = A[L];
    while(L < R) {
        while(A[R] >= mid && L < R) R--;//等于号能保证其相对位置不变，稳定性这一块
        A[L] = A[R];
        while(A[L] <= mid && L < R) L++;
        A[R] = A[L];
    }
    A[L] = mid;
    return L;
}

int func(int A[], int n, int k) {
    int L = 0, R = n - 1, M = 0;
    while(1) {
        M = huafor(A, L, R);
        if(M == k - 1) break;
        else if(M > k - 1) R = M - 1;
        else if(M < k - 1) L = M + 1;
    }
    return A[k-1];
}

int Merge(int A[], int N, int B[], int M, int C[]) {
    int i = 0, j = 0, k = 0;
    while (i < N && j < M) {
        if (A[i] <= B[j])
            C[k++] = A[i++];
        else
            C[k++] = B[j++];
    }
    while (i < N)
        C[k++] = A[i++];
    while (j < M)
        C[k++] = B[j++];
    return 1;
}

//删除值为 x 的结点
void deletX(LinkList L, int x) {
    LNode *pre = L; //pre指向p的前驱结点
    LNode *p = pre->next; //p指向下一个要处理的结点
    while (p != NULL) {
        //对当前结点p进行处理
        if (p->data == x) {
            LNode *q = p; //删除并释放值为x的结点
            p = p->next; //p指向后一个结点
            pre->next = p; //修改前驱结点的next指针
            free(q);
        } else {
            pre = p; // pre、p 后移
            p = p->next;
        }
    }
}

//在递增有序链表中插入值为 x 的信息
void InsertX(LinkList L, int x) {
    LNode *pre = L; //pre指向p的前驱结点
    LNode *p = pre->next; //p指向下一个要处理的结点
    while (p != NULL) {
        //对当前结点p进行处理
        if (p->data > x) {
            break; //应插入到p的前面
        } else {
            pre = p; // pre, p 后移
            p = p->next;
        }
    }
    LNode *q = (LNode *)malloc(sizeof(LNode));
    q->data = x;
    q->next = p;
    pre->next = q;
}

void ListReserve(LinkList L){
    //分配一个辅助头结点
    LinkList head = (LNode *) malloc(sizeof(LNode));
    head->next = NULL;

    while (L->next != NULL){
        LNode *p = L->next;
        L->next = L->next->next;
        p->next = head->next;
        head->next = p;
    }
    L->next = head->next;
    free(head); //释放辅助头结点
}

void ListPart(LinkList C){
    LinkList A=(LNode*)malloc(sizeof(LNode))//A和B的头结点来也
    LinkList B=(LNode*)malloc(sizeof(LNode))
    A->next=NULL;
    B->next=NULL;
    int count=1;//计数器：判断奇偶结点
    LNode *q=A;//A的尾指针
    while(C->next != NULL){
        if(count%2 == 1)//若为奇数，尾插法
        {
            LNode*p=C->next;//记录目前要拆掉的结点
            C->next=C->next->next;//断开该结点
            q->next=p;//插入尾结点之后
            p->next=NULL;//断掉和原表最后的联系
            q=p;//更新尾指针
            count++;//更新计数值
        }
        if(count%2 == 0)//若为偶数，头插法
        {
        	LNode *p = C->next;//记录目前要拆掉的结点
      	    L->next = C->next->next;//断开该结点
     	    p->next = B->next;//将最新的结点插到最头边，保证逆序
        	B->next = p;//作为头结点的下一个结点
            count++;//更新计数值
        }
    }
    free(C);//正式消灭C表
}

//二叉树的结点定义（链式存储）
typedef struct BiTNode{
    int data;    //数据域
    struct BiTNode *lchild,*rchild;    //左、右孩子指针
}BiTNode,*BiTree;

//先序遍历二叉树
void PreOrder (BiTree root){
    if (root==NULL)
        return;
    visit(root);  //访问根节点
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}

//中序遍历二叉树
void InOrder (BiTree root){
    if (root==NULL)
        return;
    InOrder(root->lchild);
    visit(root);  //访问根节点
    InOrder(root->rchild);
}

//后序遍历二叉树
void PostOrder (BiTree root){
    if (root==NULL)
        return;
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    visit(root);  //访问根节点
}

//初始化队列
void InitQueue(Queue &Q) 
//判断队列是否为空
bool IsEmpty(Queue Q) 
//新元素x入队
void EnQueue(Queue &Q, BiTNode * x) 
//队头元素出队，并使用x 返回队头元素 
void DeQueue(Queue &Q, BiTNode * &x)//&x 表示引用参数，函数内部对x的修改会影响外部的x

//层序遍历
void LevelOrder(BiTree T){
    Queue Q;
    InitQueue(Q);    //初始化辅助队列
    BiTree p;
    EnQueue(Q, T);    //将根结点入队
	while(!IsEmpty(Q)){
    	DeQueue(Q, p);
    	visit(p);
    	if(p->lchild != NULL)
        	EnQueue(Q, p->lchild); //左孩子入队
    	if(p->rchild != NULL)
        	EnQueue(Q, p->rchild); //右孩子入队
	}
}

/*求树的高度（方法一）*/
int height = 0;    //用全局变量记录树的高度
void PreOrder(BiTree T, int n) {
    if (T == NULL)
        return;
    if (n > height)
        height = n;    //更新树的高度
    PreOrder(T->lchild, n + 1);    //遍历左子树
    PreOrder(T->rchild, n + 1);    //遍历右子树
}

int PostOrder(BiTree T){
    if (T == NULL)
        return 0;
    int left = PostOrder(T->lchild);
    int right = PostOrder(T->rchild);
    if (left > right) 
        return left + 1;
    else 
        return right + 1;
}

int width[MAX];  //用于统计各层的结点总数

//先序遍历，同时统计各层结点总数
void PreOrder(BiTree T, int level) {
    if (T == NULL) return;
    width[level]++;  //累加该层结点总数
    PreOrder(T->lchild, level + 1);  //遍历左子树
    PreOrder(T->rchild, level + 1);  //遍历右子树
}

void treeWidth(BiTree T) {
    // 初始化宽度数组
    for (int i = 0; i < MAX; i++)
        width[i] = 0;
    PreOrder(T, 0);  // 从第0层开始遍历
    
    // 找出最大宽度（某一层最多的节点数）
    int maxWidth = 0;
    for (int i = 0; i < MAX; i++) {
        if (width[i] > maxWidth)
            maxWidth = width[i];
    }
    printf("树的宽度是%d", maxWidth);
}

void PreOrder (BiTree T, int level){
    if (T == NULL) return;
    if(T->lchild==NULL && T->rchild==NULL)
    WPL += level*T->weight; //累加叶结点带权路径长度
    PreOrder(T->lchild, level + 1); //遍历左子树
    PreOrder(T->rchild, level + 1); 
}

int temp=MIN_INT; //记录当前遍历到的最小值
bool isBST=true;    //是否为二叉排序树？

void InOrder(BiTree T){
    if (T == NULL) return;
    InOrder(T->lchild);
    if (T->data >= temp)    temp=T->data;
    else    isBST=false;
    InOrder(T->rchild);
}

bool isBalance=true;    //二叉树是否平衡
int PostOrder(BiTree T){
    if (T == NULL)
    return 0;
    int left = PostOder(T->lchild);
    int right = PostOder(T->rchild);

    if (left-right>1)    isBalance=false;
    if (left-right<-1)    isBalance=false;

    //树的深度=Max(左子树深度，右子树深度)+1
    if (left>right)   return left+1;
    else    return right+1;
}

// 特殊树形判定：完全二叉树？

bool isComplete = true;    // 是否为完全二叉树
bool flag = false;         // flag=true，表示层序遍历时出现过叶子或只有左孩子的分支节点

void visit(BiTNode * p) {
    if (p->lchild == NULL && p->rchild == NULL) {
        // 当前节点为叶子节点
        if (flag) {
            isComplete = false;  // 不是完全二叉树
        }
        flag = true;
    } else if (p->lchild != NULL && p->rchild == NULL) {
        // 只有左孩子，没有右孩子
        if (flag) {
            isComplete = false;  // 不是完全二叉树
        }
        flag = true;
    } else if (p->lchild == NULL && p->rchild != NULL) {
        // 只有右孩子，没有左孩子 - 肯定不是完全二叉树
        isComplete = false;
    } else {
        // 有两个孩子
        if (flag) {
            isComplete = false;  // 不是完全二叉树
        }
    }
}

//邻接矩阵实现深度优先搜索
void DFS(MGraph G,int i){
    visit(i);
    //访问初始顶点
    visited[i]=true;//对做已访问标记
    for(int j=0;j<G.G.numVertices;j++)
    if(visited[j]==false&&G.edge[i][j]==1){
    DFS(G,j);//为的尚未访问的邻接点，递归访问
    }
}

//邻接表实现深度优先搜索
void DFS(ALGraph G,int i){
    visit(i);
    //访问初始顶点
    visited[i]=true;//对做已访问标记
    for(EdgeNode* p=G.VertexList[i].first ; p!=NULL; p=p->next){
    //检测的所有邻接点
    int j=p->index;
    if(visited[j]==false){
    DFS(G,j);//为的尚未访问的邻接点，递归访问
    }
    }
}

//邻接矩阵实现广度优先搜索
void BFS(MGraph G, int v){
    visit(v); //访问初始顶点
    visited[v]=true; //对v做已访问标记
    EnQueue(Q, v); //顶点v入队
    while(!isEmpty(Q)){
        DeQueue(Q, v); //从队首取出顶点v
        for(int w=0; w<G.numVertices; w++){
            //检测v的所有邻接顶点
            if(visited[w]==false && G.edge[v][w]==1){
                visit(w); //w为v的尚未访问的邻接点，访问w
                visited[w]=true; //标记w为已访问
                EnQueue(Q, w); //顶点w入队
            }
        }
    }
}

//邻接表实现广度优先搜索
void BFS(ALGraph G, int v){
    visit(v); //访问初始顶点
    visited[v]=true; //对v做已访问标记
    EnQueue(Q, v); //顶点v入队
    while(!isEmpty(Q)){
        DeQueue(Q, v); //从队首取出顶点v
        for(EdgeNode *p=G.VertexList[v].first; p!=NULL; p=p->next){
            //检测v的所有邻接顶点
            int w = p->index;
            if(visited[w]==false){
                visit(w); //w为v的尚未访问的邻接点，访问w
                visited[w]=true; //标记w为已访问
                EnQueue(Q, w); //顶点w入队
            }
        }
    }
}

//邻接表实现
int uniquely1(MGraph G){
    int inDegree[MAXV] = {0}; // 存储每个顶点的入度
	int queue[MAXV];    // 用于存储入度为0的顶点
	int front = 0, rear = 0;    // 队列的前后指针
	int count = 0;    // 拓扑序列中的顶点计数

// 计算每个顶点的入度
	for (int i = 0; i < G.vexnum; i++)
	{
    	ArcNode *p = G.AdjList[i].firstarc;//从i的第一条边开始找
    	while (p != NULL)
    	{
        	inDegree[p->adjvex]++;
        	p = p->nextarc;
    	}
	}

// 将所有入度为0的顶点入队
	for (int i = 0; i < G.vexnum; i++)
	{
    	if (inDegree[i] == 0)
        	queue[rear++] = i;
	}

// 进行拓扑排序
	while (front < rear)//非空队列
	{
    	// 如果队列中有多个顶点，说明图的拓扑序列不唯一
    	if (rear - front > 1)
        return 0;
    	int v = queue[front++]; // 取出队首顶点
    	count++;
    	// 更新该顶点的所有邻接顶点的入度
    	ArcNode *p = G.AdjList[v].firstarc;
    	while (p != NULL)
    	{
        	inDegree[p->adjvex]--;
        	// 如果入度变为0，则加入队列
        	if (inDegree[p->adjvex] == 0)
            	queue[rear++] = p->adjvex;
        	p = p->nextarc;
    	}
	}

	if (count == G.vexnum)
    	return 1; // 当前拓扑序列包含所有顶点，则图的拓扑序列唯一
	else
    	return 0; // 当前拓扑序列不包含所有顶点，则图的拓扑序列不存在
}
    

//邻接矩阵实现
int uniquely1(MGraph G)
{
    int inDegree[MAXV] = {0}; // 存储每个顶点的入度
    int queue[MAXV]; // 用于存储入度为0的顶点
    int front = 0, rear = 0; // 队列的前后指针
    int count = 0; // 拓扑序列中的顶点计数
    
    // 计算每个顶点的入度
    for (int i = 0; i < G.numVertices; i++)
        for (int j = 0; j < G.numVertices; j++)
            if (G.Edge[i][j] != 0)
                inDegree[j]++;
    
    // 将所有入度为0的顶点入队
    for (int i = 0; i < G.numVertices; i++)
        if (inDegree[i] == 0)
            queue[rear++] = i;

    
    // 进行拓扑排序
    while (front < rear)
    {
        // 如果队列中有多个顶点，说明图的拓扑序列不唯一
        if (rear - front > 1)
            return 0;
        int v = queue[front++]; // 取出队首顶点
        count++;
        // 更新该顶点的所有邻接顶点的入度
        for (int i = 0; i < G.numVertices; i++)
            if (G.Edge[v][i] != 0)
            {
                inDegree[i]--; // 如果入度变为0，则加入队列
                if (inDegree[i] == 0)
                    queue[rear++] = i;
            }
    }
    
    if (count == G.numVertices)
        return 1; // 当前拓扑序列包含所有顶点，则图的拓扑序列唯一
    else
        return 0; // 当前拓扑序列不包含所有顶点，则图的拓扑序列不存在
}

ThreadNode *Nextnode (ThreadNode *p) {
    if(p->rtag==0) return Firstnode(p->rchild); //右子树中最左下结点
    else return p->rchild;          // rtag==1 则直接返回后继线索
}