对一棵完全3叉树，按照广度优先遍历顺序给结点从左向右依次连续编号，第 个结点编号为0。则编号为100的结点的父结点编号是_

编号为100的结点的父结点编号是33。

在一棵完全3叉树中，每个结点都有3个子结点。因此，对于结点编号为n的结点，它的子结点的编号分别为3n+1、3n+2和3n+3。反过来，对于结点编号为n的结点，它的父结点的编号为(n-1)/3。

因此，对于编号为100的结点，它的父结点的编号为(100-1)/3=33。

相关问题

（1）创建图和实现图的深度优先遍历和广度优先遍历 a.所输入的数据要为整形数据 b.输出的形式为：每按一次回车，遍历一个结点。 c.实现对无向图的两种遍历：深度优先遍历和广度优先遍历。 程序流程： main()visited()DFS()visited()BFS()

以下是一个基于邻接矩阵的实现示例：

#include <iostream>
#include <queue>
using namespace;

const int MAXN = 100;
int graph[MAXN][MAXN];  // 邻接矩阵
bool visited[MAXN];     // 记录结点是否被访问过

// 深度优先遍历
void DFS(int cur) {
    cout << cur << endl;
    visited[cur] = true;
    for (int i = 0; i < MAXN; i++) {
        if (graph[cur][i] && !visited[i]) {
            DFS(i);
        }
    }
}

// 广度优先遍历
void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << endl;
        for (int i = 0; i < MAXN; i++) {
            if (graph[cur][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    // 初始化邻接矩阵
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // 添加边
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[1][4] = graph[4][1] = 1;
    graph[2][4] = graph[4][2] = 1;
    graph[3][4] = graph[4][3] = 1;

    cout << "DFS:" << endl;
    DFS(0);

    for (int i = 0; i < MAXN; i++) {
        visited[i] = false;
    }

    cout << "BFS:" << endl;
    BFS(0);

    return 0;
}

其中，我们使用一个 `visited` 数组来记录结点是否被访问过，以避免重复访问。在深度优先遍历中，我们先访问当前结点，然后对于每个未访问的相邻结点，递归调用 `DFS` 函数进行遍历。在广度优先遍历中，我们使用一个队列来记录待访问的结点，从起始结点开始，先访问当前结点，然后将其相邻的未访问结点全部加入队列中。重复这个过程，直到队列为空。

c语言实现（1）图的基本操作 [问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求] 1.以邻接矩阵为存储结构，实现强连通图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 2.以邻接表为存储结构，实现连通图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

[解题思路]

图的基本操作有两种存储结构：邻接矩阵和邻接表。其中，邻接矩阵使用二维数组存储图的边，邻接表则使用链表存储每个顶点的相邻顶点。

深度优先遍历和广度优先遍历都是基于搜索算法实现的。深度优先遍历（DFS）是一种先访问深度较深的节点，再逐步回溯访问其他节点的算法，而广度优先遍历（BFS）则是一种逐层遍历的算法。

对于邻接矩阵存储结构，我们可以使用递归实现深度优先遍历，使用队列实现广度优先遍历。而对于邻接表存储结构，我们同样可以使用递归实现深度优先遍历，使用队列实现广度优先遍历。

[参考代码]

以下是基于邻接矩阵和邻接表的深度优先遍历和广度优先遍历的代码实现。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接矩阵存储结构
typedef struct {
    char vexs[MAX_VERTEX_NUM]; // 顶点集合
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵，可看作边表
    int vexnum, arcnum; // 图的当前点数和边数
} MatrixGraph;

// 邻接表存储结构
typedef struct ArcNode {
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    char data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 图的当前点数和边数
} ListGraph;

bool visited[MAX_VERTEX_NUM]; // 记录各个顶点是否被访问过

// 初始化邻接矩阵
void InitMatrixGraph(MatrixGraph *G) {
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    
    printf("请输入图的顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vexs[i]);
    }
    
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arc[i][j] = 0;
        }
    }
    
    printf("请输入图的边信息（格式：vi vj）：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        scanf(" %c %c", &v1, &v2);
        int i, j;
        for (i = 0; i < G->vexnum; i++) {
            if (G->vexs[i] == v1) break;
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vexs[j] == v2) break;
        }
        G->arc[i][j] = 1;
        G->arc[j][i] = 1;
    }
}

// 深度优先遍历邻接矩阵
void DFSMatrix(MatrixGraph G, int v) {
    visited[v] = true;
    printf("%c ", G.vexs[v]);
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arc[v][i] == 1 && !visited[i]) {
            DFSMatrix(G, i);
        }
    }
}

// 广度优先遍历邻接矩阵
void BFSMatrix(MatrixGraph G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = true;
    printf("%c ", G.vexs[v]);
    queue[rear++] = v;
    while (front < rear) {
        int i = queue[front++];
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arc[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                printf("%c ", G.vexs[j]);
                queue[rear++] = j;
            }
        }
    }
}

// 初始化邻接表
void InitListGraph(ListGraph *G) {
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    
    printf("请输入图的顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    
    printf("请输入图的边信息（格式：vi vj）：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        scanf(" %c %c", &v1, &v2);
        int i, j;
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) break;
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) break;
        }
        ArcNode *e1 = (ArcNode *)malloc(sizeof(ArcNode));
        e1->adjvex = j;
        e1->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = e1;
        
        ArcNode *e2 = (ArcNode *)malloc(sizeof(ArcNode));
        e2->adjvex = i;
        e2->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = e2;
    }
}

// 深度优先遍历邻接表
void DFSList(ListGraph G, int v) {
    visited[v] = true;
    printf("%c ", G.vertices[v].data);
    ArcNode *p = G.vertices[v].firstarc;
    while (p != NULL) {
        int j = p->adjvex;
        if (!visited[j]) {
            DFSList(G, j);
        }
        p = p->nextarc;
    }
}

// 广度优先遍历邻接表
void BFSList(ListGraph G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = true;
    printf("%c ", G.vertices[v].data);
    queue[rear++] = v;
    while (front < rear) {
        int i = queue[front++];
        ArcNode *p = G.vertices[i].firstarc;
        while (p != NULL) {
            int j = p->adjvex;
            if (!visited[j]) {
                visited[j] = true;
                printf("%c ", G.vertices[j].data);
                queue[rear++] = j;
            }
            p = p->nextarc;
        }
    }
}

int main() {
    MatrixGraph G1;
    InitMatrixGraph(&G1);
    printf("请输入起点（邻接矩阵）：");
    char start1;
    scanf(" %c", &start1);
    int i;
    for (i = 0; i < G1.vexnum; i++) {
        if (G1.vexs[i] == start1) break;
    }
    printf("深度优先遍历结果（邻接矩阵）：");
    DFSMatrix(G1, i);
    printf("\n");
    for (int j = 0; j < G1.vexnum; j++) {
        visited[j] = false;
    }
    printf("广度优先遍历结果（邻接矩阵）：");
    BFSMatrix(G1, i);
    printf("\n");
    
    ListGraph G2;
    InitListGraph(&G2);
    printf("请输入起点（邻接表）：");
    char start2;
    scanf(" %c", &start2);
    for (i = 0; i < G2.vexnum; i++) {
        if (G2.vertices[i].data == start2) break;
    }
    printf("深度优先遍历结果（邻接表）：");
    DFSList(G2, i);
    printf("\n");
    for (int j = 0; j < G2.vexnum; j++) {
        visited[j] = false;
    }
    printf("广度优先遍历结果（邻接表）：");
    BFSList(G2, i);
    printf("\n");
    
    return 0;
}