> first child, next sibling structure

¿don't you think that perhaps it would be helpful to explain what does that mean? we are not in your class.

> How would you find the number of nullpointers?

count them. they don't appear magically, they are related to the nodes of the tree (inner nodes or leaves)

¿when would a node have a nullpointer? (¿and why?)

¿don't you think that perhaps it would be helpful to explain what does that mean? we are not in your class.

> How would you find the number of nullpointers?

count them. they don't appear magically, they are related to the nodes of the tree (inner nodes or leaves)

¿when would a node have a nullpointer? (¿and why?)

¿don't you think that perhaps it would be helpful to explain what does that mean? we are not in your class. |

https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

then it's easy, each node have two linked list.

¿how many nullpointers have a linked list? none, because the implementation makes it circular.

¿how many nullpointers have a linked list? none, because the implementation makes it circular.

For the the first child, next sibling tree

a. every node contains a value and two pointers: a pointer to the first child, and a pointer to the next sibling. In a tree containing**n** nodes, total number of pointers == **n*2**

b. every node (except the root) has exactly one pointer pointing to it: it is either a first child or a next sibling. In a tree containing**n** nodes, the total number of non-null pointers == **n-1**

From a. and b. the total number of null pointers == n*2 - (n-1) ==**n+1**

a. every node contains a value and two pointers: a pointer to the first child, and a pointer to the next sibling. In a tree containing

b. every node (except the root) has exactly one pointer pointing to it: it is either a first child or a next sibling. In a tree containing

From a. and b. the total number of null pointers == n*2 - (n-1) ==

Last edited on

@JLBorges

In your 3rd step I don't get how you could make that arithmetic to get n. Plus why wouldn't it be 2^n pointers, but n*2?

When you mean by n*2, is that the same thing as 2 times n or n to the power of 2?

In your 3rd step I don't get how you could make that arithmetic to get n. Plus why wouldn't it be 2^n pointers, but n*2?

When you mean by n*2, is that the same thing as 2 times n or n to the power of 2?

Last edited on

Perhaps a picture would help.

See the picture at he bottom of this page under '2. Left Child - Right Sibling Representation'

http://btechsmartclass.com/DS/U3_T2.html

Picture: http://btechsmartclass.com/DS/images/Left%20Child%20Right%20Sibling.png

In the diagram, each node has three fields: a value (at the top) and and two pointers (in the bottom two cells)

In the left cell at the bottom is the pointer to the first (left) child; and the right cell has the pointer to the next (right) sibling.

A non-null pointer is indicated by an arrow pointing away from the cell, and a null-pointer is marked as NULL.

There are eleven nodes in the tree: A, B, C, D, E, F, G, H, I, J, K**n == 11**

a. Total number of pointers == total number of cells at the bottom ==**n*2** == **11*2** == **22**

b. Number of non-null pointers ==**n-1** == **11-1** == **10**

(There is one pointer pointing to every node except for the root node.)

c. The total number of null pointers ==**total number of pointers - number of non-null pointers**

==**(n*2) - (n-1)** == **(n+n) - (n-1)** == **n+n-n+1** == **n+1** == **11+1** == **12** == **22-10**

See the picture at he bottom of this page under '2. Left Child - Right Sibling Representation'

http://btechsmartclass.com/DS/U3_T2.html

Picture: http://btechsmartclass.com/DS/images/Left%20Child%20Right%20Sibling.png

In the diagram, each node has three fields: a value (at the top) and and two pointers (in the bottom two cells)

In the left cell at the bottom is the pointer to the first (left) child; and the right cell has the pointer to the next (right) sibling.

A non-null pointer is indicated by an arrow pointing away from the cell, and a null-pointer is marked as NULL.

There are eleven nodes in the tree: A, B, C, D, E, F, G, H, I, J, K

a. Total number of pointers == total number of cells at the bottom ==

b. Number of non-null pointers ==

(There is one pointer pointing to every node except for the root node.)

c. The total number of null pointers ==

==

Last edited on

Topic archived. No new replies allowed.