C/C++ Beginner's Guide and Post Basic Questions here

quicky008

Technomancer
i remember reading somewhere that in an array representation of a tree,

if node: i

Child: 2*i, 2*i+1

Parent: i/2

Is this a correct way to represent the array elements as nodes of a binary tree?
 

pkkumarcool

Game & anime Lover
i remember reading somewhere that in an array representation of a tree,

if node: i

Child: 2*i, 2*i+1

Parent: i/2

Is this a correct way to represent the array elements as nodes of a binary tree?
so both child will be greater than parent? as far as i reme,
i remember reading somewhere that in an array representation of a tree,

if node: i

Child: 2*i, 2*i+1

Parent: i/2

Is this a correct way to represent the array elements as nodes of a binary tree?
any explanation why i dont get why child is 2*i
 

Nerevarine

Incarnate
Simple reason is that we should have a formula for properly mapping out a root node to 2 different unique child nodes which can be easily tracked and there is no collision.
To be absolutely fair, you can make a binary tree with ANY formula, it is not a given that it should be 2*i, as long as there is a one to one mapping between root -> left child and root -> right child.
What I mean is, there should not be a situation where
root1 index -> leftchild1 index
root1 index -> rightchild1 index

root2 index -> leftchild1 index
root2 index -> rightchild2 index


As you can see from the above example root1 and root2 are both mapped to leftchild1 index, which causes a collision.
To sum up, a binary tree is just a mapping of root to 2 unique and retrievable child nodes without any collision.

We use the 2*i format because it is very simple, and wastes very little space. You could literally use ANY hash function to make a custom tree of your own, as long as there is no collision.


This is wiki's defination
Arrays[edit]
Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices {\displaystyle 2i+1}*wikimedia.org/api/rest_v1/media/math/render/svg/f077f73c2ecdf3c6e29a120f948a7255c0a65da1 (for the left child) and {\displaystyle 2i+2}*wikimedia.org/api/rest_v1/media/math/render/svg/a756deaef520ee23fe2b1232c90957f55ec9d92b (for the right), while its parent (if any) is found at index {\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }*wikimedia.org/api/rest_v1/media/math/render/svg/35dc2d601bbd9aff8f1ed1c4b2323122f2403317 (assuming the root has index zero). This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal. However, it is expensive to grow and wastes space proportional to 2h - n for a tree of depth h with n nodes.

This method of storage is often used for binary heaps. No space is wasted because nodes are added in breadth-first order.

Correct me If I'm wrong.
 

quicky008

Technomancer
How can i create an array of strings in c++?

Whenever i create a string array using "string ar[5]" and then attempt to enter values in it via a for loop,i can only enter 4 values ie one less than the arrays capacity.


Can anyone suggest why this happens?
 

Nerevarine

Incarnate
When you create ar[5], here the 5 refers to size of array.
But programming index starts from 0, not one.
So ar[0], 1,2,3,4 are your entries
 

whitestar_999

Super Moderator
Staff member
But he should still get 5 entries right 0,1,2,3,4


Sent from my iPhone using Tapatalk
My C++ knowledge is quite dusty but from whatever I remember if you assign an array value to wrong index it won't enter & here a 'for' loop is used which I presume starts from i=1 with +1 increment till i=5 which will result in only 4 entries as array[5] entry will be ignored.
 

pkkumarcool

Game & anime Lover
My C++ knowledge is quite dusty but from whatever I remember if you assign an array value to wrong index it won't enter & here a 'for' loop is used which I presume starts from i=1 with +1 increment till i=5 which will result in only 4 entries as array[5] entry will be ignored.

Yeah if you start for loop with i=1 till i<5 then you will get 4 values only.


Sent from my iPhone using Tapatalk
 

Nerevarine

Incarnate
Guys if you are on windows, Visual Studio is definitely the go to choice for C/CPP development. MacOS the obvious best choice is XCode.
Linux its either you use gcc or a proper IDE. I know I suggested to learn and use gcc in the past, but managing a large project completely via gcc and make is a monumental task. So my IDE of choice for Linux is definitely Clion (Its paid unfortunately)
Eclipse CDT is too slow, QT creator is also good (free) choice.
 

quicky008

Technomancer
thanks for all of your valued inputs.

I am aware that in case of arrays and strings,the index starts from 0 and i had coded the for loop correctly keeping that in mind.

The coding was ok,it seems the error was being caused by some bug in Dev-Cpp as when i executed the same program on another machine (having a different version of Dev-CPP installed) it worked just fine and accepted 5 values as input like its supposed to.

Dev-cpp is known to be a somewhat buggy IDE-i think i will switch to code blocks from now on.BTW can regular C/C++ programs be executed in VStudio? Are any free versions of Vstudio available which aren't too resource or memory intensive?
 

Nerevarine

Incarnate
An advice for any new c/cpp developers.
Learn new cpp syntax, especially cpp+14/17. Smart pointers , etc. You don't need to worry about memory allocation and shit.
Learn concept of RAII
Use better ide from the get-go (visual studio)
Learn to use breakpoints instead of print statements (millions of them)
Use scm(git)
 
Top Bottom