Let T be a binary tree with n positions that is realized with an array represent

ID: 3826426 • Letter: L

Question

Let T be a binary tree with n positions that is realized with an array representation A, and let f () be the level numbering function of the positions of T, as given in Section 8.3.2. Give pseudocode descriptions of each of the methods root, parent, left, right, isExternal, and isRoot.

Must be in pseudocode. Java.

8.3. Implementing Trees 331 8.3.2 Array-Based Representation of a Binary Tree An alternative representation of a binary tree Tis based on a way of numbering the positions of T. For every position p of T, let f(p) be the integer defined as follows. If p is the root of T, then f 0. If p is the right child of position q, then f(p) 2f(q)+2. The numbering function f is known as a level numbering of the positions in a binary tree T, for it numbers the positions on each level of T in increasing order from left to right. (See Figure 8.10. Note well that the level numbering is based on potential positions within a tree, not the actual shape of a specific tree, so they are not necessarily consecutive. For example, in Figure 8.100b, there are no nodes with level numbering 13 or 14, because the node with level numbering 6 has no children. (a) 10 11 12 13 14 (b) 10 12 11 16 19 25 15 3 1 7 4 Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example.

Explanation / Answer

See below the code snippet written in java for different operation to be done on tree.

this code will consider the positions of the nodes in tree. and will calculate related nodes positions.

please do give me a feedback for this ans. to help you solving the problems

code:

//this is a tree represented as a array.

   String[] treeArray={"/","*","+","+","4","-","2","3","1","","","9","5"};

   //this method will find the root of the tree, which i offcource will be the 0th element in the array.
   public String root()
   {
       //this will return the first element in array which is the root.
       return treeArray[0];
   }

   //this method to return the parent element of the given position.
   //position will be the index of specific node in array.
   public String parent(int position)
   {
       int location=(position-1)/2;
       return treeArray[location];
   }

   //this method will return the left child of given position.
   public String left(int position)
   {
       int location=2*position+1;

       return treeArray[location];
   }
   //this method will return the left child of given position.
   public String right(int position)
   {
       int location=2*position+2;
       return treeArray[location];
   }
   //it will identify the given position is root position or not.
   public boolean isRoot(int position)
   {
       if(position==0)
           return true;
       return false;
   }

Navigate

Let T be a binary tree with n nodes. Define a Roman node to be a node v in T, su

Let T be a binary tree. Write a O(n) -time algorithm that receives as input a no

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let T be a binary tree with n positions that is realized with an array represent

Question

Explanation / Answer

Related Questions

Navigate