Implement a Binary tree using an array using class.

Implement a Binary tree using an array using class.

Expert Solution

#define MAX_ELEMS 100

struct bst
{
        int data;
        int lindex;
        int rindex;
};

void MakeNode(struct bst * tree, int data)
{
        tree->data = data;
        tree->lindex = tree->rindex = -1;
}

void Insertleft( struct bst *tree, int data)
{
        MakeNode(tree, data);
}

void Insertright( struct bst * tree, int data)
{
        MakeNode(tree, data);
}

void Insert(struct bst * tree, int treeIndex, int data)
{
        int baseIndex = 0;
        
        while(baseIndex <= treeIndex)
        {
                if(data <= tree[baseIndex].data)
                {
                        if(tree[baseIndex].lindex == -1)
                        {
                                tree[baseIndex].lindex = treeIndex;
                                Insertleft(&tree[treeIndex], data);
                                return;
                        }
                        else
                        {
                                baseIndex = tree[baseIndex].lindex;
                                continue;
                        }

                }
                else // data is > tree[baseIndex].data
                {
                        if(tree[baseIndex].rindex == -1)
                        {
                                tree[baseIndex].rindex = treeIndex;
                                Insertright(&tree[treeIndex], data);
                                return;
                        }
                        else
                        {
                                baseIndex = tree[baseIndex].rindex;
                                continue;
                        }
                }
        }
}

void Intrav(struct bst * tree, int index)
{
        if(tree[index].lindex != -1)
                Intrav( tree, tree[index].lindex );
        cout<<"DataIn ="<<tree[index].data<<endl;
        if(tree[index].rindex != -1)
                Intrav( tree, tree[index].rindex );
}

void Pretrav(struct bst * tree, int index)
{
        cout<<"DataPre ="<<tree[index].data<<endl;
        if(tree[index].lindex != -1)
                Pretrav( tree, tree[index].lindex );
        if(tree[index].rindex != -1)
                Pretrav( tree, tree[index].rindex );
}

void Posttrav(struct bst * tree, int index)
{
        if(tree[index].lindex != -1)
                Posttrav( tree, tree[index].lindex );
        if(tree[index].rindex != -1)
                Posttrav( tree, tree[index].rindex );
        cout<<"DataPost ="<<tree[index].data<<endl;
}

int main()
{
        struct bst tree[MAX_ELEMS];
        memset(tree, 0, sizeof(tree));
        int treeIndex = 0;

        MakeNode(&tree [treeIndex], 50);
        treeIndex++;
        Insert(tree, treeIndex, 10);
        treeIndex++;
        Insert(tree, treeIndex, 60);
        treeIndex++;
        Insert(tree, treeIndex, 25);
        treeIndex++;
        Insert(tree, treeIndex, 30);
        treeIndex++;
        Insert(tree, treeIndex, 92);
        treeIndex++;
        Insert(tree, treeIndex, 15);
        treeIndex++;
        Insert(tree, treeIndex, 67);
        
        Intrav(tree, 0);
        Pretrav(tree,0);
        Posttrav(tree, 0);

        return 0;
}

venereology answered 1 year ago

C++ Build a binary tree using a binary tree class member function from the following array...

C++ Build a binary tree using a binary tree class member function from the following array of preorder traversal 3,9,20,15,7 and inorder traversal 9,3,15,20,7. Implement the constructor, destructor and all member functions including print postorder traversal of the binary tree.

Implement a function to find a node in a binary search tree. Using the following class...

Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() { root = new...

I was trying to implement a simple binary search tree using this given class of bst...

I was trying to implement a simple binary search tree using this given class of bst in c++ public: BST(); ~BST(); void insertKey(int newKey); bool hasKey(int searchKey); std::vector<int> inOrder(); int getHeight(); however; i am still required to use another class for the nodes as a pointer and i need to manage memory leak. in main we should ask for the numbers we need to insert in the binary search tree and also let the user end it with a letter...

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...

In C++, Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a...

In C++, Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a funcntion that takes in a binary tree and heapafies it. Meaning it takes in a pointer to a binary tree and converts it into a heap. (You may choose max or min heap).

C++ Write the code to implement a complete binary heap using an array ( Not a...

C++ Write the code to implement a complete binary heap using an array ( Not a vector ). Code for Max heap. Implement: AddElement, GetMax, HeapSort, ShuffleUp, ShuffleDown, etc Set array size to 31 possible integers. Add 15 elements 1,3,27,22,18,4,11,26,42,19,6,2,15,16,13 Have a default constructor that initializes the array to zeros.. The data in the heap will be double datatype. PART 2 Convert to the program to a template, test with integers, double and char please provide screenshots thank you so...

Make an Array implementation of a binary tree given the below class ArrayBinaryTree(BinaryTree): """Linked representation of...

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...

Implement a function to remove a leaf node from a binary search tree. Using the following...

Implement a function to remove a leaf node from a binary search tree. Using the following class and function definition: class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode * remove_leaf(int item, bool &removed) { // implement } The remove function will return the node with the item if it's present in the tree. If the node is a leaf node and is removed by the function,...

C++ Implement the array based Binary Heap data structure as discussed in class. This structure should...

C++ Implement the array based Binary Heap data structure as discussed in class. This structure should have a couple of constructures (default constructor, and a constructor that takes an array pointer and a size), a method for inserting items into the heap, a method for removing items from the heap, and a method that returns the number of items currently stored in the heap. This implementation should be templated so that it can store any type of data (you may...

C++(screenshot output please) Part 2 - Tree programs Program 1 Implement a tree using an array...

C++(screenshot output please) Part 2 - Tree programs Program 1 Implement a tree using an array Program 2 Implement a tree using linked list - pointer Binary Tree Program 3 - Convert program 1 to a template

Question