我试图用一个队列(队列是用链接列表实现的)在二进制树中实现一个级别顺序遍历的算法。它应该打印树中的所有节点,但是,由于某些原因,我无法理解,输出的只是根数据。如果你能帮助我,我将非常感激! 下面是我的代码:`
#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