用c语言链表实现给定一棵二叉树,按照从顶部到底部的顺序,返回从右侧所能看到的节点值
时间: 2024-04-15 10:29:26 浏览: 118
要使用链表实现给定二叉树从右侧可见的节点值,可以使用广度优先搜索(BFS)遍历二叉树,并记录每一层的最右侧节点值。以下是使用C语言实现的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 链表节点结构
struct ListNode {
int val;
struct ListNode* next;
};
// 创建链表节点
struct ListNode* createListNode(int val) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 将节点值插入链表尾部
void insertListNode(struct ListNode** head, int val) {
if (*head == NULL) {
*head = createListNode(val);
} else {
struct ListNode* curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = createListNode(val);
}
}
// 广度优先搜索遍历二叉树并返回从右侧可见的节点值
struct ListNode* rightSideView(struct TreeNode* root) {
struct ListNode* result = NULL;
struct ListNode* currLevel = NULL;
if (root == NULL) {
return result; // 空树,返回空链表
}
struct TreeNode* queue[1000]; // 使用队列存储每一层的节点
int front = 0, rear = 0;
int currLevelSize = 1, nextLevelSize = 0;
queue[rear++] = root;
while (front < rear) {
struct TreeNode* node = queue[front++];
// 更新当前层的最右侧节点值
insertListNode(&currLevel, node->val);
if (node->left != NULL) {
queue[rear++] = node->left;
nextLevelSize++;
}
if (node->right != NULL) {
queue[rear++] = node->right;
nextLevelSize++;
}
// 当前层遍历完毕
if (--currLevelSize == 0) {
// 将当前层的最右侧节点值插入结果链表
insertListNode(&result, currLevel->val);
// 重置下一层的节点数量和当前层链表
currLevelSize = nextLevelSize;
nextLevelSize = 0;
currLevel = NULL;
}
}
return result;
}
// 创建二叉树节点
struct TreeNode* createTreeNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
// 创建二叉树节点
struct TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->right = createTreeNode(5);
root->right->right = createTreeNode(4);
// 获取从右侧可见的节点值链表
struct ListNode* result = rightSideView(root);
// 打印链表的值
struct ListNode* curr = result;
while (curr != NULL) {
printf("%d ", curr->val);
curr = curr->next;
}
return 0;
}
```
以上示例代码创建了一个二叉树,并使用广度优先搜索(BFS)遍历二叉树,将每一层的最右侧节点值插入链表中。最后打印出链表中的节点值,即为从右侧可见的节点值。您可以根据自己的需求进行修改和使用。希望对您有帮助!如有任何疑问,请随时追问。
阅读全文