Python programming; pleasee help! In his exercise, you need to design and implem

Question

Python programming; pleasee help!

In his exercise, you need to design and implement the following classes:   

Abstract Binary Tree (BT) class, with two subclasses:

Concrete Binary Search Tree (BST) class – Implement all functions as described below.

Concrete Max-Heap class – List all functions but do not implement them.

For simplicity’s sake, you can assume every item stored in a tree consists of an integer key and other attributes (at least one). Note that you must decide, for each function specified below, in which of the three classes it should be defined, whether it should be abstract or not, what it should be called, what data it should use and return, and (for BT and BST) how to code it.

Required functions:

A default constructor that creates an empty tree.

A constructor that creates a new tree containing all items provided as arguments.

A setter function that inserts a given item into the tree.

A retrieval function that searches for a given item (by key) and returns it if found.

A membership function that searches for a given item (by key) and returns true if found and false if not. It must allow the in() function to work (e.g., if item in tree: …)

A delete function that searches for a given item (by key) and removes it from the tree.

A function that counts and returns the number of items in the tree. It must allow the standard len() function to work (i.e., len(tree) returns the number of nodes).

A height function that calculates and returns the (max) depth of the tree.

Four functions that implement pre-order, in-order, post-order and breadth-first traversals, generating items one by one only. (Note that Breadth-first traversal is the one used when converting a binary tree of nodes into an array. The other traversals apply to BST only.)

A function that will allow the standard print() function to output all items in order.

A function that draws the tree, in a format similar to the examples shown below. For simplicity’s sake, you can assume all item keys are in the range 0-99.

Explanation / Answer

To implement the binary search tree, we will use the nodes and references approach similar to the one we used to implement the linked list, and the expression tree. However, because we must be able create and work with a binary search tree that is empty, our implementation will use two classes. The first class we will call BinarySearchTree, and the second class we will call TreeNode. The BinarySearchTree class has a reference to the TreeNode that is the root of the binary search tree. In most cases the external methods defined in the outer class simply check to see if the tree is empty. If there are nodes in the tree, the request is just passed on to a private method defined in the BinarySearchTree class that takes the root as a parameter. In the case where the tree is empty or we want to delete the key at the root of the tree, we must take special action.

Constructor:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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