数据结构常见算法总结

图的广度遍历

1. 初始化visited[]数组
2. for 对未访问过的顶点调用广度优先遍历算法
3. 广度优先遍历
   1. 先将参数送进来的序号对应的visited[v]置为true，并将v入队
   2. 队列Q不空时循环：遍历Q中元素，并将未访问过的边表结点入队

bool visited[max_vex_num];
void BFSTraverse(Graph G){
    //初始化访问数组
    for(int i = 0; i< G.vexnum; i++)
        visited[i] = false;
    
    //广度遍历每个未访问过的节点
    for(int v = 0; v < G.vexnum; v++)
        if(!visited[v])
            BFS(G,v);
}

void BFS(Graph G, int v){
    int p;
    int Q[G.vexnum];
    int front = 0, rear = 0;
    
    //先访问进来的节点，并入队
    visit(v);
    visited[v] = true;
    Q[rear++] = v;
    
    while(front != rear){
        p = Q[front++];
        for(int w = FirstNeighbor(G,p); w>=0; w = NextNeighbor(G,p,w)){
            //访问未被访问过的边表节点，并入队
            if(!visited[w]){
            	visit(w);
            	visited[w] = true;
            	Q[rear++] = w;
            }
        }
    }
}

深度优先遍历：递归实现

只要是没访问节点都直接进行深度遍历

bool visited[max_vex_num];
void DFSTraverse(Graph G){
    for(int i = 0; i < G.vexnum; i++)
        visited[i] = false;
    for(int v = 0; v < G.vexnum; v++){
        if(!visited[v])
            DFS(G,v);
    }
}

//递归实现
void DFS(Graph G, int v){
    visit(v);
    visited[v] = true;
    //对每个边表结点都进行深度遍历
    for(int w = FirstNeighbor(G,v); w>=0; w = NextNeighbor(G,v,w)){
        if(!visited[w])
            DFS(G,w);
    }
}

深度优先遍历：非队列实现

从顶点v开始进行深度优先搜索，一次遍历一个连通分量，由于是出栈的时候再访问所以得到的遍历顺序是从边表结点的右到左的次序。

1. 根节点入栈，栈不空时循环；
2. 栈顶元素出栈并访问，将栈顶元素所有未入栈的边表结点入栈

bool ispushed[MaxSize]; 		//标记顶点是否入栈过，防止重复入栈
void DFS_Non_RC(Graph G, int v){
    InitStack(S);
    for(int i = 0; i < G.vexnum; i++)
        ispushed[i] = false;
    
    Push(S,v);	//入栈
    ispushed[v] = true;	//标记，防止再次入栈
    
    while(!IsEmpty(S)){
        //出栈并访问
        int k = Pop(S);
        visit(k);
        
        //将k节点的所有未入栈的边表结点入栈
        for(int w = FirstNeighbor(G,k); w>=0; w = NextNeighbor(G,k,w)){
            if(!ispushed[w]){
                Push(S,w);
                ispushed[w]=true;
            }
        }
    }
}

BFS算法求单源最短路径（无权图）

bool visited[MaxSize];	//访问数组
int d[MaxSize];		//保存u到i的路径长度
void BFS_Distance(Graph G, int u){
    int Queue[G.vexnum];
    int front = 0, rear = 0;
    //初始化数组
    for(int i=0; i<G.vexnum; i++){
        visited[i] = false;
        d[i] = -1;
    }
    //初始化根节点
    d[u] = 0;
    visited[u] = true;
    
    Quere[rear++] = u;
    int x;
    while(front != rear){
        x = Queue[front++];
        for(int w = FirstNeighbor(G,x); w>=0; w = NextNeighbor(G,x,w)){
            if(!visited[w]){
                d[w] = d[u] + 1;	//路径长度+1
                visited[w] = true;
                Queue[rear++] = w;
            }
        }
    }
}

树的先序、中序遍历

先序：沿着根节点的左孩子，依次入栈并访问，直到孩子为空；将栈顶元素出栈，并开始遍历右子树

中序：沿着根节点的左孩子，依次入栈，直到孩子为空，将栈顶元素出栈并访问，并开始遍历右子树

void Order(BiTree T){
    BiNode *Stack[MaxSize];		//声明一个栈
    int top = -1;
    BiNode *p = T;
    
    //栈未空或树未遍历完
    while(top != -1 || p != NULL){
        if(p){
            visit(p);		//访问节点，先序遍历
            Stack[++top] = p;	//入栈
            p = p->lchild;
        }
        else{
            p = Stack[top--];
            //visit(p);			//在这里访问就是中序遍历
            p = p->rchild;
        }
    }
}

树的后序遍历

双栈法

1. 将根节点入栈S1；
2. S1栈顶元素p出栈，放入栈S2，并将栈顶元素p的左右子树入栈S1；
3. 重复操作2，直到S1栈空。
4. S2中的元素依次出栈得到的就是后序遍历的结果。

void Post_Order(BiTree T){
    if(!T) return;
    
    BiNode *S1[MaxSize], *S2[MaxSize];
    int top1 = -1, top2 = -1;
    BiNode *p;
    
    S1[++top1] = T;		//根节点入栈S1
    while(top1 != -1){
        p = S1[top1--];
        S2[++top2] = p;		//S1的栈顶元素移入S2
        if(p->lchild)
        	S1[++top1] = p->lchild;		//左孩子入栈S1
        if(p->rchild)
        	S1[++top1] = p->rchild;		//右孩子入栈S2
    }
    
    //S2中的结果出栈
    while(top2 != -1){
        p = S2[top--];
        visit(p);
    }
}

单栈标记法

1. 从根节点开始，左孩子依次入栈，直到左孩子为空；

2. 栈顶元素出栈，并判断栈顶元素是否有未被访问的右孩子

   ①有右孩子，且没有访问过，则将栈顶元素重新入栈，并遍历右子树；

   ②如果没有右孩子，或者右孩子已经被访问过，则直接访问栈顶元素。

void Post_Order(BiTree T){
    BiNode *S[MaxSize];
    int top = -1;
    BiNode *p = T, *r = NULL;	//r指向最近访问的节点
    
    //栈未空 或 树未遍历完
    while(top != -1 || p != NULL){
        if(p){
            S[++top] = p;	//入栈
            p = p->lchild;	//遍历左子树
        }
        else{
            p = S[top--];
            if(p->rchild != NULL && p->rchild != r){
                //有未被访问的有孩子
                S[++top] = p;	//重新入栈
                p = p->rchild;	//遍历右子树
            }
            else{
                visit(p);	//访问节点
                r = p;		//标记节点为最近访问过
                p = NULL;
            }
        }
    }
}

层次遍历

借助队列，先将根节点依次入队，出队并将其左右节点（若存在）依次入队，重复上述操作，直到队空

void Level_order(BiTree T){
    if(T == NULL) return;
    BiNode *Queue[MaxSize];
    int front = 0, rear = 0;
    BiNode *p = NULL;
    Queue[rear++] = T;
    while(front < rear){
        p = Queue[front++];
        visit(p);
        
        if(p->lchild!=NULL)
            Queue[rear++] = p->lchild;
        if(p->rchild!=NULL)
            Queue[rear++] = p->rchild;
    }
}

求二叉树的层数、高度

非递归：层序遍历+记录每层最后一个节点

也可以求节点所在层数

借助队列对二叉树进行层次遍历，当每层的最后一个节点的左右子树（若存在）入队之后，记录队尾结点rear的位置，即为下一层的最后一个节点，并将树的层数+1

int TreeLevel(BiTree T){
    if(T == NULL)
        return 0;
    int level, flag;
    BiNode *Queue[MaxSize];
    int front = 0, rear = 0;
    BiNode *p;
    
    Queue[rear++] = T;
    flag = rear; 	//标记队尾结点
    while(front != rear){
        p = Queue[front++];
        /**
        找到所求节点，直接返回层数
        if(p == x) return leval+1;
        */
        if(p->lchild!=NULL)
            Queue[rear++] = p->lchild;
        if(p->rchild!=NULL)
            Queue[rear++] = p->rchild;
        
        if(front == flag){
            flag = rear;	//标记队尾结点
            level++;
        }
    }
    return level;
}

递归

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

输出最长路径上的节点

对二叉树进行后序遍历，用到辅助栈S1，再用一个栈S2来存放最长路径上的节点，用visited指针标记最近访问的节点

1. 从根节点开始，左孩子依次入栈，直到左孩子为空；

2. 栈顶元素出栈，并判断栈顶元素是否有未被访问的右孩子

   ①有右孩子，且没有访问过，则将栈顶元素重新入栈，并遍历右子树；

   ②没有右孩子，或者右孩子已经被访问过

   ​ a. 是否是叶子节点？

   ​ 若是→比较S1与S2的栈顶指针top1和top2，如果top1>top2，说明S1中的路径长度更长，因此用该路径替换S2的内容；

   ​ b. 访问栈顶元素，visited = p;

3. 继续遍历，直到S1为空，最后S2中的元素出栈，就是从根节点到叶节点的最长路径。

void longestRoute(BiTree T) {
    BiNode *S1[MAXSIZE], *S2[MAXSIZE];
    int top1 = -1, top2 = -1;
    BiNode *p = T, *visited = NULL;
    
    while(top1 != -1 || p != NULL){
        if(p!=NULL){
            S1[++top1] = p;
            p = p->next;	//遍历左子树
        }else{
            p = S1[top1--];
            
            //当p有未被访问过的右孩子
            if(p->rchild != NULL && visited != p->rchild){
                S1[++top1] = p;
                p = p->rchild;	//遍历右子树
            }
            else{
                //当p是叶节点
                if(p->lchild==NULL&&p->rchild==NULL){
                    if(top1 > top2){
                        for(int i = top1; i>=0; i--)
                            S2[i] = S1[i];
                        top2 = top1;
                    }
                }
                visited = p;	//标记最近访问的节点
                p = NULL;
            }
        }
    }
    
    while(top2 != -1){
        p = S2[top2--];
        print(p);
    }
}

求树的宽度

非递归：层次遍历+计算每行宽度

在求二叉树层数的非递归层数的基础上，在遍历每一行最后一个元素的时候，都计算下一行的节点个数：count=rear-front

int TreeWidth(BiTree T){
    if(T == NULL)
        return 0;
    int flag;
    BiNode *Queue[MaxSize];
    int front = 0, rear = 0;
    BiNode *p;
    
    int count = 0, width = 0;	//count表示下一行的节点个数，width表示树的宽度
    
    Queue[rear++] = T;
    flag = rear; 	//标记队尾结点
    while(front != rear){
        p = Queue[front++];
        
        if(p->lchild!=NULL)
            Queue[rear++] = p->lchild;
        if(p->rchild!=NULL)
            Queue[rear++] = p->rchild;
        
        //已经出队到这一行的最后一个元素
        if(front == flag){
            flag = rear;	//更新队尾结点标记
            count = rear - front;	//计算下一行节点个数
            if(count > width)
                width = count;
        }
    }
    return width;
}

交换二叉树左右子树

非递归：层次遍历，将入队次序改为先右后左

递归：

void swap(BiTree T){
    BiNode *q;
    q = T->lchild;
    T->lchild = T->rchild;
    T->rchild = q;
    swap(T->lchild);
    swap(T->rchild);
}

求叶子结点个数

若节点为空，则返回0，若节点为叶子结点则返回1，否则返回左、右子树叶子结点的和，递归调用。

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

找p与q的最近公共祖先，求祖先都用后序遍历

1. 使用单栈标记法的后序遍历，栈S1用于后序遍历；
2. 当遍历到p或q中的任意一个时，将S1中的元素复制到S2中；
3. 继续找另一个，找到后退出循环。
4. 遍历S1与S2，从栈底开始，找到第一个不同的点，返回该点的前驱结点。算法结束

void SearchParents(BiTree T, BiNode *p, BiNode *q){
    BiNode *S1[MaxSize], *S2[MaxSize];
    int top1 = -1, top2 = -1;
    BiNode *r = T, *visited = NULL;
    int flag = 0; 	//标记是否已经找到一个节点
    int i;
    
    while(top1 != -1 && r != NULL){
        if(r){
            if(r == p ||r == q){
                //找到其中一个
                if(flag == 0){
                    for(int i = 1; i<=top1; i++)
                        S2[i] = S1[i];
                    top2 = top1;
                    flag = 1;
                }else{
                    //p和q都找到了退出循环
                    break;
                }
            }
            
            S1[++top1] = r;		//入栈
            r = r->lchild;		//遍历左子树
        }else{
            r = S1[top1--];
            //如果有未被访问过的右子树
            if(r->rchild != NULL && visited != r){
                S1[++top1] = r;
                r = r->rchild;
            }
            else{
                visited = r;
                r = NULL;
            }
        }
    }
    
    //p和q都找到了
    for(i=0; S1[i] == S2[i] && i<=top1 && i <= top2; i++);	//从栈底开始，找到第一个不相等的节点
    return S1[i-1];		//返回该节点的前驱
}