c - C中使用队列的级别顺序树遍历
问题描述
我正在尝试使用队列在二叉树中实现级别顺序遍历算法(队列是使用链表实现的)。它应该打印树中的所有节点,但是由于某种原因我无法弄清楚,输出只是根数据。如果您能帮助我,我将不胜感激!这是我的代码:`
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode{
int data;
struct BSTNode* left;
struct BSTNode* right;
} bstNode;
/* Queue */
typedef struct queueNode{
bstNode* node;
struct queueNode* next;
} qNode;
typedef struct Queue
{
qNode* head;
qNode* end;
} queue;
bstNode* getNewNode(int data){
bstNode* newNode = (bstNode*)malloc(sizeof(bstNode));
if(!newNode)
return NULL;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void insertBSTNode(bstNode** root, int data){
if(*root == NULL){ // empty tree
*root = getNewNode(data);}
else if((*root)->data >= data)
insertBSTNode(&((*root)->left), data);
else insertBSTNode(&((*root)->right), data);
}
queue* initQ(){
queue* q = (queue*)malloc(sizeof(queue));
if(!q) return NULL;
q->head = NULL;
q->end = NULL;
return q;
}
qNode* allocNewQNode(bstNode* root)
{
qNode* newNode = (qNode*)malloc(sizeof(qNode));
if (!newNode) return NULL;
newNode->node = (bstNode*)malloc(sizeof(bstNode));
if(!newNode->node){
free(newNode);
return NULL;
}
//memcpy(newNode->node, root, sizeof(bstNode));
newNode->node->data = root->data;
newNode->node->left = root->left;
newNode->node->right = root->right;
newNode->next = NULL;
return newNode;
}
void enqueue(queue* q, bstNode* root)
{
qNode* tmp = allocNewQNode(root);
if(q->head == NULL && q->end == NULL){
q->head = tmp;
q->end = tmp;
return;
}
else{
q->end->next = tmp;
q->end = tmp;
return;
}
}
qNode* dequeue(queue* q)
{
if(q->head == NULL) return NULL;
qNode* tmp = allocNewQNode(q->head->node);
qNode* aux = NULL;
q->head->node = NULL;
aux = q->head;
q->head = q->head->next;
free(aux);
return tmp;
}
void levelOrder(bstNode* root)
{
if(root == NULL) return;
else
{
queue* q = initQ();
enqueue(q, root);
while(q->head != NULL){
qNode* tmp = dequeue(q);
printf("%d ", tmp->node->data);
if (tmp->node->right != NULL){
enqueue(q, tmp->node->right);
}
if(tmp->node->left != NULL){
enqueue(q, tmp->node->left);
}
}
}
}
int main(){
bstNode* root = NULL;
insertBSTNode(&root, 2);
insertBSTNode(&root, 7);
insertBSTNode(&root, 5);
insertBSTNode(&root, 6);
insertBSTNode(&root, 9);
insertBSTNode(&root, 128);
insertBSTNode(&root, 223);
insertBSTNode(&root, 357);
levelOrder(root);
return 0;
}
`
解决方案
对于插入的数据,您应该具有以下二叉搜索树
2
\
7
/ \
5 9
\ \
6 128
\
223
\
357
并且树的级别顺序遍历应该;看起来像
2 7 5 9 6 128 223 357
构建队列时,您不应动态分配二叉搜索树节点的副本。
否则,例如该函数dequeue
会在语句中产生大量内存泄漏,例如
q->head->node = NULL;
或者返回并创建了一个类型的节点qNode
在函数中没有被释放levelOrder
。
此外,您没有 在此语句之后将数据成员设置end
为NULL
q->head = q->head->next;
当队列只包含一个节点时
并且不需要动态定义队列本身。
这是一个演示程序,显示了如何使用您的方法定义函数。
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode
{
int data;
struct BSTNode *left;
struct BSTNode *right;
} bstNode;
/* Queue */
typedef struct queueNode
{
bstNode* node;
struct queueNode *next;
} qNode;
typedef struct Queue
{
qNode *head;
qNode *end;
} queue;
bstNode * getNewNode( int data )
{
bstNode* newNode = malloc( sizeof( bstNode ) );
if ( newNode != NULL )
{
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
int insertBSTNode( bstNode **root, int data )
{
return *root == NULL
? ( *root = getNewNode( data ) ) != NULL
: ( data < ( *root )->data
? insertBSTNode( &( *root )->left, data )
: insertBSTNode( &( *root )->right, data ) );
}
void initQ( queue *q )
{
q->head = NULL;
q->end = NULL;
}
qNode * allocNewQNode( bstNode *node )
{
qNode *newNode = malloc( sizeof( qNode ) );
if ( newNode != NULL )
{
newNode->node = node;
newNode->next = NULL;
}
return newNode;
}
void enqueue( queue *q, bstNode *node )
{
qNode *tmp = allocNewQNode( node );
if ( q->head == NULL )
{
q->head = q->end = tmp;
}
else
{
q->end = q->end->next = tmp;
}
}
bstNode * dequeue( queue *q )
{
bstNode *node = q->head == NULL ? NULL : q->head->node;
if ( q->head != NULL )
{
qNode *tmp = q->head;
q->head = q->head->next;
free( tmp );
if ( q->head == NULL ) q->end = NULL;
}
return node;
}
void levelOrder( bstNode *root )
{
if ( root != NULL )
{
queue q;
initQ( &q );
enqueue( &q, root );
while ( q.head != NULL )
{
bstNode *tmp = dequeue( &q );
printf( "%d ", tmp->data );
if ( tmp->left != NULL )
{
enqueue( &q, tmp->left );
}
if ( tmp->right != NULL )
{
enqueue( &q, tmp->right );
}
}
}
}
int main(void)
{
bstNode *root = NULL;
insertBSTNode( &root, 2 );
insertBSTNode( &root, 7 );
insertBSTNode( &root, 5 );
insertBSTNode( &root, 6 );
insertBSTNode( &root, 9 );
insertBSTNode( &root, 128 );
insertBSTNode( &root, 223 );
insertBSTNode( &root, 357 );
levelOrder( root );
putchar( '\n' );
return 0;
}
程序输出为
2 7 5 9 6 128 223 357
推荐阅读
- r - 无法理解为什么 for 循环在 R 中给出这样的结果
- ios - platformView、FlutterPlatformView 和 FlutterPlatformViewFactory 的区别
- python - 使用 pandas 将零替换为另一列的值
- sublimetext3 - Sublime 文本中的 Ctrl+RightArrow
- python - 如何在 Python 中将水平列表转换为垂直列表并计算术语
- python - python 在一个类的所有对象上尝试 if 语句
- c++ - 什么是 C++ 中的内存位置修改?
- pdf - 使用 Ghostscript 将 PDF 重定向到 Windows 打印机
- java - 如何在嵌套对象的 TableView 中显示数据?
- javascript - 通知用户该电子邮件已经存在。?