Question
In: Computer Science
Implement a Binary tree using an array using class.
Implement a Binary tree using an array using class.
Solutions
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 agoRelated Solutions
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++(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
Write an implementation of the set class, with associated iterators using a binary search tree. Add...
Write an implementation of the set class, with associated
iterators using a binary search tree. Add to each node a link to
the parent node. (C++)
Write a C++ class that implement two stacks using a single C++ array. That is, it...
Write a C++ class that implement two stacks using a single C++
array. That is, it should have functions pop_first(), pop_second(),
push_first(…), push_second(…), size_first(), size_second(), …. When
out of space, double the size of the array (similarly to what
vector is doing).
Notes:
Complete all the functions in exercise_2.cpp, then
submit this cpp file.
pop_first() and pop_second() should throw
std::out_of_range exception when stack is empty.
CODE:
#include <cstdio>
#include <stdexcept>
template <class T>
class TwoStacks {
public:
// Constructor, initialize...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- 1. The economy's income and expenditure The following diagram presents a circular-flow model of a simple...
- Due to the covid-19 pandemic, the US economy entered a downturn that would eventually lead to...
- According to one survey taken a few years ago, 32% of American households have attempted to...
- You attach a 1.50 kg block to a horizontal spring that is fixed at one end....
- Organizations are currently open systems. Why are organizations considered open systems as opposed to closed systems?...
- In 2010, Ticketmaster found out the hard way that the entertainment industry is not, in fact,...
- Add to this arduino sketch such that you can add three externally-connected LEDs to your circuit...
ADVERTISEMENT