Tree structure question
> 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 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
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 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
Last edited on
Topic archived. No new replies allowed.