我一直在尝试用 C 语言实现带队列的二叉树,我对这种语言还很陌生。我一直在尝试调试我用 C 编写的代码,从头开始编写代码但没有结果。我看不出我做错了什么。
我检查了我用整数数据编写的队列代码,它运行良好。
- 入队函数将一个元素压入队列
- dequeue 函数从队列中弹出一个元素
- 检查队列是否为空的空函数
然后我实现了二叉搜索树并打印了节点中的元素
root -> left -> left -> left -> data; //worked fine, was able to reach the extreme left leaf node
和
root -> right -> right -> right -> data;//工作正常,以防万一
还有一些像这样的遍历,看起来树形成得很好。我在 level_order()
函数中打印了队列,我能理解的是队列构建不正确。不知何故,整个事情进入了无限循环。我已经没有想法了。这是代码,谢谢。
#include <stdio.h>
#include <stdlib.h>
struct BstNode{
int data;
struct BstNode *left;
struct BstNode *right;
};
struct Queue{
struct BstNode *address;
struct Queue *next;
};
struct Queue *front = NULL;
struct Queue *back = NULL;
struct Queue* create_queue(BstNode **address){
struct Queue *temp = (Queue*)malloc(sizeof(struct Queue));
temp -> next = NULL;
temp -> address = *address;
return temp;
}
void enqueue(BstNode **address){
struct Queue *temp = create_queue(address);
if(front == NULL && back == NULL){
front = back = temp;
}
else{
temp -> next = back;
back = temp;
}
}
void dequeue(){
if(front == NULL){
return;
}
struct Queue* temp;
temp = back;
if(front == back){
front = back = NULL;
}
else{
back = back -> next;
}
free(temp);
}
bool empty(){
if(front == NULL){
return true;
}
return false;
}
void print_queue(){
struct Queue *temp = back;
while(temp != NULL){
printf("%d", temp->address->data);
temp = temp -> next;
}
printf("\n");
}
struct BstNode *root;
struct BstNode *create_node(int data){
struct BstNode *temp = (BstNode *)malloc(sizeof(struct BstNode));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
}
void insert_bst_cell(BstNode **node, int data){
if((*node) == NULL){
struct BstNode* temp = create_node(data);
*node = temp;
}
else if(data > (*node)->data){
insert_bst_cell(&(*node)->right, data);
}
else if(data < (*node)->data){
insert_bst_cell(&(*node)->left, data);
}
}
BstNode *first_element(){
return front->address;
}
void level_order(){
if(root == NULL) return;
enqueue(&root);
while(!(empty())){
struct BstNode *current = first_element();
dequeue();
printf("%d\n", current->data);
if(current->right != NULL){
enqueue(&(current->left));
}
if(current->left != NULL){
enqueue(&(current->right));
}
}
}
int main(int argc, char **argv)
{
front = NULL;
back = NULL;
root = NULL;
insert_bst_cell(&root, 15);
insert_bst_cell(&root, 10);
insert_bst_cell(&root, 20);
insert_bst_cell(&root, 5);
insert_bst_cell(&root, 11);
insert_bst_cell(&root, 17);
insert_bst_cell(&root, 25);
insert_bst_cell(&root, 4);
insert_bst_cell(&root, 6);
insert_bst_cell(&root, 9);
insert_bst_cell(&root, 12);
insert_bst_cell(&root, 16);
insert_bst_cell(&root, 19);
insert_bst_cell(&root, 21);
insert_bst_cell(&root, 35);
level_order();
return 0;
}
最佳答案
感谢Paul Georg Podlech指出我已经实现了一个堆栈而不是队列。另一个错误是
if(current->right != NULL){
enqueue(&(current->left));
}
if(current->left != NULL){
enqueue(&(current->right));
}
在此特定代码中。应该是
if(current->left != NULL){ //current -> right in previous snippet
enqueue(&(current->left));
}
if(current->right != NULL){ //current -> left in previous snippet
enqueue(&(current->right));
}
以防万一我会发布工作代码
#include <stdio.h>
#include <stdlib.h>
struct BstNode{
int data;
struct BstNode *left;
struct BstNode *right;
};
struct Queue{
struct BstNode *address;
struct Queue *next;
};
struct Queue *front = NULL;
struct Queue *back = NULL;
struct Queue* create_queue(BstNode **address){
struct Queue *temp = (Queue*)malloc(sizeof(struct Queue));
temp -> next = NULL;
temp -> address = *address;
return temp;
}
void enqueue(BstNode **address){
struct Queue *temp = create_queue(address);
if(front == NULL && back == NULL){
front = back = temp;
}
else{
// temp -> next = back;
back -> next = temp;
back = temp;
}
}
void dequeue(){
if(front == NULL){
return;
}
struct Queue* temp;
temp = front;
if(front == back){
front = back = NULL;
}
else{
front = front -> next;
}
free(temp);
}
bool empty(){
if(front == NULL){
return true;
}
return false;
}
void print_queue(){
struct Queue *temp = back;
while(temp != NULL){
printf("%d", temp->address->data);
temp = temp -> next;
}
printf("\n");
}
struct BstNode *root;
struct BstNode *create_node(int data){
struct BstNode *temp = (BstNode *)malloc(sizeof(struct BstNode));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
}
void insert_bst_cell(BstNode **node, int data){
if((*node) == NULL){
struct BstNode* temp = create_node(data);
*node = temp;
}
else if(data > (*node)->data){
insert_bst_cell(&(*node)->right, data);
}
else if(data < (*node)->data){
insert_bst_cell(&(*node)->left, data);
}
}
BstNode *first_element(){
return front->address;
}
void level_order(){
if(root == NULL) return;
enqueue(&root);
while(!(empty())){
struct BstNode *current = first_element();
dequeue();
printf("%d\n", current->data);
if(current->left != NULL){
enqueue(&(current->left));
}
if(current->right != NULL){
enqueue(&(current->right));
}
}
}
int main(int argc, char **argv)
{
front = NULL;
back = NULL;
root = NULL;
insert_bst_cell(&root, 15);
insert_bst_cell(&root, 10);
insert_bst_cell(&root, 20);
insert_bst_cell(&root, 5);
insert_bst_cell(&root, 11);
insert_bst_cell(&root, 17);
insert_bst_cell(&root, 25);
insert_bst_cell(&root, 4);
insert_bst_cell(&root, 6);
insert_bst_cell(&root, 9);
insert_bst_cell(&root, 12);
insert_bst_cell(&root, 16);
insert_bst_cell(&root, 19);
insert_bst_cell(&root, 21);
insert_bst_cell(&root, 35);
level_order();
return 0;
}
感谢大家的宝贵时间和意见。
关于c - 队列陷入无限循环的二叉树级顺序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48525423/