0 
#include <iostream> typedef struct Node { int key; int ltag, rtag; struct Node* lchild, * rchild; }Node; Node* getNewNode(int key) { Node *p =(Node *)malloc(sizeof(Node)); } int main() { std::cout << "Hello World!\n"; }

When defining a binary tree, I found a problem. For example, in this code, the int variable takes up 4 bytes, and there are 3 int variables. Plus the Node* lchild and Node* rchild, shouldn't it be 36 bytes?

My own idea is that lchild is regarded as the same node structure, so there are also 12 bytes in lchild, that is, three int variables. But the compiler told me that it only has 20 bytes:

A screenshot of a line of code reading Node *p = (Node *)malloc(sizeof(Node)); There is an IDE tooltip displayed below it showing the value of sizeof(Node) to be (size_t)20U

Why is this so? It should also be 36 bytes if aligned naturally.

Improve this question
10
  • 2
    sizeof(Node) /*20 in your case*/ = 3 * sizeof (int) /*4 in your case*/+ 2 * sizeof (Node*) /*4 in your case*/ /*+ padding, 0 in your case*/ Commented Jun 17, 2022 at 9:29
  • 4
    Please don't include unrelated tags and don't post images of code. Thank you. Commented Jun 17, 2022 at 9:29
  • 2
    sizeof(Node*) is unrelated to sizeof(Node). Commented Jun 17, 2022 at 9:30
  • 6
    lchild and rchild are pointers - thus also occupying 4 bytes (on most systems) - therefore your compiler is right, 3x 4 bytes (int) + 2x 4 bytes(ptr)= 20 bytes for the structure (not regarding any padding) Commented Jun 17, 2022 at 9:30
  • 8
    You code is a very weird mix of C and C++. In C you can't use <iostream> and you wouldn't cast the result of malloc explicitly. In C++ you wouldn't use the typedef struct Node { /*...*/ } Node; syntax but simply struct Node { /*...*/ }; instead. Also, wouldn't put struct before Node when declaring the members. Also, you wouldn't use malloc to create new Node objects. You would use new instead, or even better, use std::unique_ptr instead of raw pointers. Technically it is still valid C++ in this specific case, but especially the malloc will be wrong for non-trivial types. Commented Jun 17, 2022 at 9:39

1 Answer 1

Reset to default
1

Reducing the code and examining the sizeof() the member types of Node:

#include <iostream> struct Node { int key; int ltag, rtag; Node* lchild, * rchild; }; int main() { // size of individual types making up the struct: std::cout << "sizeof(int) = " << sizeof(int) << std::endl; std::cout << "sizeof(Node*) = " << sizeof(Node*) << std::endl; // we might expect sizeof(Node) to equal whatever this line prints out: std::cout << "sizeof(int) * 3 + sizeof(Node*) * 2 = " << sizeof(int) * 3 + sizeof(Node*) * 2 << std::endl; // but only this line will tell us for sure std::cout << "sizeof(Node) = " << sizeof(Node) << std::endl; }

As pointed out in the comments, your Node* members, lchild and rchild only get stored as pointers to type Node, they don't store an entire additional Node object each, as you suggested.

Note that the actual size of your objects as returned by sizeof() will vary from platform to platform and possibly even within the same platform. Observe sample output of the above program, running on 64-bit Linux:

sizeof(int) = 4 sizeof(Node*) = 8 sizeof(int) * 3 + sizeof(Node*) * 2 = 28 sizeof(Node) = 32

Note that in this case, even our estimate of the size by summing the size of all the members is incorrect
—the compiler does not have to align data as compactly as possible, and it didn't seem to do so in this case, hence why sizeof(Node) is larger than our estimate of it.

This is different to the size you get reported in your IDE, but neither is incorrect —the compilers are just choosing to arrange the struct data differently in either case.

Another factor that can affect this is if sizeof(int) or sizeof(void*) varies across platforms, which is not unheard of. int is only required to be at least 4 bytes wide, but can be wider, and pointer could be 4 or 8 bytes, depending on the data model used by the system. It looks like your pointers are 4 bytes wide...

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.