这是一个二叉树队列问题
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define NUM 10
typedef struct _node
{
int value;
struct _node *left;
struct _node *right;
}TNode,*Tree;
在q_node中添加*next是我的目的 否则,我们需要添加树节点结构 所以,为了不修改树的结构 我设计了一个 q_node 结构来包含它 我们可以使用define命令将其作为模板。
typedef struct _q_node
{
TNode *t_node;
int length;
struct _q_node *next;
}QNode;
typedef struct _Queue
{
QNode *head;
QNode *tail;
}Queue;
Queue* init_queue()
{
Queue *queue=(Queue*)malloc(sizeof(Queue));
queue->head = queue->tail = NULL;
return queue;
}
int enQueue(Queue *pQueue,TNode *pTNode)
{
QNode *pQNode = (QNode *)malloc(sizeof(QNode));
pQNode->t_node = pTNode;
if(pQueue->head == NULL)
{//when it's empty
pQueue->head = pQNode;
pQueue->tail = pQNode;
}
else
{
pQueue->tail->next = pQNode;
pQueue->tail = pQNode;
}
}
QNode* deQueue(Queue *pQueue)
{
if(pQueue->head == NULL)
{
return NULL;
}
QNode *deNode= pQueue->head;
pQueue->head = pQueue->head->next;
return deNode;
}
TNode* init_TNode(int value)
{
TNode *new_node = (TNode*)malloc(sizeof(TNode));
new_node->value=value;
new_node->left = new_node->right = NULL;
return new_node;
}
//0:empty
int ifEmpty(Queue *pQueue)
{
if(pQueue->head == NULL)
{
//printf("empty tree\n");
return 0;
}
//printf("queue is not empty\n");
return 1;
}
int insert_tree(Tree pTree,int pValue)
{
//found NULL sub tree, then add to his father->left
if(!pTree)
{
return 0;
}
TNode *tNode = init_TNode(pValue);
if(tNode==NULL)
{
printf("create TNode error!\n");
return 0;
}
if(pValue < pTree->value)
if(insert_tree(pTree->left,pValue)==0)
{
//no left child any more,set a new left child to pTree
pTree->left = tNode;
printf("insert :%d\n",pValue);
}
if(pValue > pTree->value)
if(insert_tree(pTree->right,pValue)==0)
{
pTree->right = tNode;
printf("insert :%d\n",pValue);
}
}
Tree creatTree()
{
srand(time(NULL));
Tree root = init_TNode(rand()%100);
printf("root is %d\n",root->value);
int i ;
for(i=1;i<NUM;i++)
{
insert_tree(root,rand()%100);
}
printf("creat tree succuess!Tree heigh is:%d\n",get_tree_height(root));
return root ;
}
int get_tree_height(Tree pRoot)
{
if(!pRoot)
{
return 0;
}
int lh=0,rh=0;
lh = get_tree_height(pRoot->left);
rh = get_tree_height(pRoot->right);
return (lh<rh)?(rh+1):(lh+1);
}
int breath_travel(Tree pRoot,Queue *pQueue)
{
if(!pRoot)
{
return 0;
}
enQueue(pQueue,pRoot);
printf("_______________________\n");
printf("breath begin,enter root:\n");
while(ifEmpty(pQueue)!=0)
{
QNode *qNode = deQueue(pQueue);
//make suer every enQueue Node is not NULL
if(qNode->t_node->left!=NULL)
{enQueue(pQueue,qNode->t_node->left);}
if(qNode->t_node->right!=NULL)
{
enQueue(pQueue,qNode->t_node->right);
}
//print the tree node value
printf("%d ",qNode->t_node->value);
}
printf("\n-----------\nbreath end!\n-----------\n");
return 1;
}
int main()
{
Queue *queue=init_queue();
int i;
ifEmpty(queue);
printf("insert node to queue\n");
Tree root = creatTree();
if(!root)
{
printf("create Tree failed!\n");
return 0;
}
breath_travel(root,queue);
// free(queue);
return 0;
}
如果这个版本可以在我的计算机上正常运行,我必须添加一个未使用的 int “int length”在开始的“_q_node”结构中,如果我不添加它,ifEmpty函数无法找到正确的位置,如“pQueue->head == NULL”
为什么会发生这种情况?
最佳答案
您的程序在 insert_tree
函数中存在错误。我在您的代码中添加了一些注释:
int insert_tree(Tree pTree,int pValue)
{
//found NULL sub tree, then add to his father->left
if(!pTree)
{
return 0;
}
TNode *tNode = init_TNode(pValue);
if(tNode==NULL)
{
printf("create TNode error!\n");
return 0;
}
if(pValue < pTree->value)
if(insert_tree(pTree->left,pValue)==0) // Here the return value is used
{
//no left child any more,set a new left child to pTree
pTree->left = tNode;
printf("insert :%d\n",pValue);
}
if(pValue > pTree->value)
if(insert_tree(pTree->right,pValue)==0) // Here the return value is used
{
pTree->right = tNode;
printf("insert :%d\n",pValue);
}
// No return value here !!
}
正如您从我的评论中看到的,您错过了函数末尾的返回值。由于您在其他地方使用该返回值,因此您的程序使用了一些未初始化的返回值。这可能会使您的程序失败。
顺便说一句:enQueue
也错过了返回值。
建议:始终以高警告级别编译代码,并将所有警告视为错误。换句话说 - 如果有警告,则应在运行代码之前修复它们。
如果使用 gcc
进行编译,请使用 -Wall
获取所有警告
除此之外我认为这个函数的逻辑有问题。它使用递归来查找插入新值的位置。在每次递归调用中,您都使用 TNode *tNode = init_TNode(pValue);
创建一个新节点,但仅在递归结束时使用它。换句话说,您似乎存在内存泄漏。
此外,还不清楚如何/在哪里处理 pValue
等于 pTree->value
的情况
顺便说一句:pValue
对于整数来说是一个非常糟糕的名字,因为 p
让你认为它是一个指针。
关于c - 为什么我的 C 结构必须添加一个奇怪的 int 并且它会影响指针?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51718803/