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 2 years agoRelated Solutions
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...
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:
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 i) {
// implement
}
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;...
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).
Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has...
Binary Search Trees with Lazy Deletion
Implement binary search tree class with lazy deletion that has
TreeNode as nested class in Java.
Design the class, TreeNode to have following class
variables:
int key; // All Keys are in the range 1 to 99
TreeNode leftChild;
TreeNode rightChild;
boolean deleted;
Your program method must have routines to do the following
operations.
1. insert
//Should insert a new element to a leaf node. If new element is
aduplicatethen do nothing. If the...
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,...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- Mobile and wireless devices are being increasingly used in the Business Administration and Management Industry. write...
- What are the options that might be considered in relation to introducing flexible work practices? What...
- Question 2 : Aggregate Scores: Write a program that opens 2 files, quiz.txt, and hw.txt. The...
- Define the term symbiosis specifically as it applies in a biological context. Compare and contrast parasitism,...
- A research team conducted a study showing that approximately 20% of all businessmen who wear ties...
- Research the internet for companies that have executed data science projects. Pick one company and describe...
- Explain two theories or frameworks for understanding how Western Europe emerged out of 1,000 years of...
ADVERTISEMENT