Question

Make an Array implementation of a binary tree given the below

class ArrayBinaryTree(BinaryTree):
    """Linked representation of a binary tree structure."""

    # -------------------------- nested _Node class --------------------------
    class _Node:

        def __init__(self, element, parent=None, left=None, right=None):

    # -------------------------- nested Position class --------------------------
    class Position(BinaryTree.Position):
        """An abstraction representing the location of a single element."""

        def __init__(self, container, node):

        def element(self):

        def __eq__(self, other):

    # ------------------------------- utility methods -------------------------------
    def _validate(self, p):
        """Return associated node, if position is valid."""

    def _make_position(self, node):
        """Return Position instance for given node (or None if no node)."""

    # -------------------------- binary tree constructor --------------------------
    def __init__(self):
        """Create an initially empty binary tree."""

    # -------------------------- public accessors --------------------------
    def __len__(self):
        """Return the total number of elements in the tree."""

    def root(self):
        """Return the root Position of the tree (or None if tree is empty)."""

    def parent(self, p):
        """Return the Position of p's parent (or None if p is root)."""

    def left(self, p):
        """Return the Position of p's left child (or None if no left child)."""

    def right(self, p):
        """Return the Position of p's right child (or None if no right child)."""

    def num_children(self, p):
        """Return the number of children of Position p."""

    # -------------------------- nonpublic mutators --------------------------
    def _add_root(self, e):
        """Place element e at the root of an empty tree and return new Position."""

    def _add_left(self, p, e):
        """Create anew left child for Position p, storing element e."""

    def _add_right(self, p, e):
        """Create a new right child for Position p, storing element e. Return the Position of new node. Raise ValueError if Position p is invalid or p already has a right child.
        """

    def _replace(self, p, e):
        """Replace the element at position p with e, and return old element."""

    def _delete(self, p):
        """Delete the node at Position p, and replace it with its child, if any.  Return the element that had been stored at Position p.Raise ValueError if Position p is invalid or p has two children.
        """

    def _attach(self, p, t1, t2):
        """Attach trees t1 and t2, respectively, as the left and right subtrees of the external Position p. As a side effect, set t1 and t2 to empty.
        Raise TypeError if trees t1 and t2 do not match type of this tree. Raise ValueError if Position p is invalid or not external.
        """

Answer 1

#include<iostream.h>

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

int binarysearch(int arr[],int k,int r,int x)

{

while(k<=r)

{

int m=k+(r-k)/2;

if(arr[m]==x)

{

return m;

}

if(arr[m]<x)

{

k=m+1;

}

else

{

r=m-1;

}

}

return -1;

}

int main(void)

{

clrscr();

int arr[20],n,x,i;

cout<<"enter the number of elements in the array: ";

cin>>n;

cout<<"enter the elements one by one:\n" ;

for(i=0;i<n;i++)

{

cin>>arr[i];

}

cout<<"enter the value you want to check : ";

cin>>x;

int result=binarysearch(arr,0,n-1,x);

if(result==-1)

{

cout<<"element is not present in the array";

}

else

{

result++;

cout<<"Element is present at "<<result<<" position";

}

getch();

return 0;

}

#include<conio.h>

#include<stdio.h>

int binarysearch(int arr[],int k,int r,int x)

{

while(k<=r)

{

int m=k+(r-k)/2;

if(arr[m]==x)

{

return m;

}

if(arr[m]<x)

{

k=m+1;

}

else

{

r=m-1;

}

}

return -1;

}

int main(void)

{

clrscr();

int arr[20],n,x,i;

cout<<"enter the number of elements in the array: ";

cin>>n;

cout<<"enter the elements one by one:\n" ;

for(i=0;i<n;i++)

{

cin>>arr[i];

}

cout<<"enter the value you want to check : ";

cin>>x;

int result=binarysearch(arr,0,n-1,x);

if(result==-1)

{

cout<<"element is not present in the array";

}

else

{

result++;

cout<<"Element is present at "<<result<<" position";

}

getch();

return 0;

}