用深度搜索遍历树,原题如下:
我的代码如下:
为了让各路大沈们能更好的理解我的问题,我举一个例子表达我的问题所在:
在这个例子中,我第一条路探索的自然是1->2->6->5->7->9->NULL,然后7->9被标记探索过了,但是最短路径是1->4->7->9->NULL,所以不可能得到正确答案
而且我在洛谷评测结果是RE,而不是WA,这就让我更不能理解了!快帮帮我,我快受不了了!(┬_┬)(ಥ_ಥ)(。ŏ_ŏ)
用深度搜索遍历树,原题如下:
【以下回答由 GPT 生成】
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_SIZE 100
typedef struct TreeNode {
int value;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct Stack {
TreeNode* data[MAX_TREE_SIZE];
int top;
} Stack;
// 初始化栈
void init(Stack* s) {
s->top = -1;
}
// 入栈
void push(Stack* s, TreeNode* node) {
if (s->top == MAX_TREE_SIZE - 1) {
printf("Stack overflow\n");
exit(1);
}
s->data[++(s->top)] = node;
}
// 出栈
TreeNode* pop(Stack* s) {
if (s->top == -1) {
printf("Stack underflow\n");
exit(1);
}
return s->data[(s->top)--];
}
// 深度搜索遍历树
void dfsTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
Stack s;
init(&s);
push(&s, root);
while (s.top != -1) {
TreeNode* node = pop(&s);
printf("%d ", node->value);
if (node->right) {
push(&s, node->right);
}
if (node->left) {
push(&s, node->left);
}
}
}
// 示例
int main() {
// 构建示例树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->value = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->value = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->value = 3;
root->right->left = NULL;
root->right->right = NULL;
// 深度搜索遍历树
printf("深度搜索遍历结果:");
dfsTraversal(root);
return 0;
}
希望这段代码能帮助你解决遍历树的问题。如果还有其他问题,欢迎继续询问!