why my C structure must add a weird int and it affect the pointer?

Question

this is a binary tree queue problem

#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;

add a *next in q_node is my purpose other wise , we need to add in the Tree node struct So, for the sake of doesn't modify the struct of tree I design a q_node struct to include it we can use define command to make it as a template.

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;
}

if this version can function well in my computer i have to add a unused int "int length" in the beginning " _q_node" structure , if i don't add it the ifEmpty function cannot find the right position like "pQueue->head == NULL"

why this happen?

this is all the code that it can directly run in ur computer — yuan sun, Aug 07 '18 at 04:24
Don't hide the Pointer Type `struct _node *` under an _typedef_. It's considered as bad style. (As people tend to not free/malloc it) — Inrin, Aug 07 '18 at 05:03
Read [how to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Basile Starynkevitch, Aug 07 '18 at 07:33
also [don't cast the result of `malloc` in C](https://stackoverflow.com/q/605845/995714) — phuclv, Aug 07 '18 at 07:53

Support Ukraine · Answer 1 · 2018-08-07T07:40:51.180

Your program has a bug in the insert_tree function. I have added a few comments to your code:

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 !!
}

As you can see from my comments you miss a return value at the end of the function. Since you use that return value in other places, you program uses some uninitialized return value. That can make your program fail.

BTW: enQueue miss a return value as well.

An advice: Always compile your code with a high warning level and consider all warnings to be errors. In other words - if there are warnings they shall be fixed before running the code.

If you compile using gcc use -Wall to get all warnings

Besides that I think there is a problem with the logic in this function. It uses recursion to find where to insert the new value. In each recursive call you create a new node using TNode *tNode = init_TNode(pValue); but you only use it at the end of the recursion. In other words it seems you have memory leaks.

Further it's unclear how/where you handle the case where pValue is equal to pTree->value

BTW: pValue is a real bad name for an integer as the p makes you think it's a pointer.

why my C structure must add a weird int and it affect the pointer?

1 Answers1