Написать 2 задания на Python (стек, очередь, дерево поиска)

Здравствуйте!

Мне нужно написать два маленьких задания на Python до 23:59 в Пятницу, 21 Февраля.

1. Имплементация стека и очереди (не используя лист);

2. Имплементация дерева, двоичного и АВЛ дерева.

Всего доброго и удачи!

Lab 1 - Queues and Stacks

Create a file called Lab1-YourStudentNumber.py. Incorrectly named files will receive a mark of zero.

First, create a method called getName() that returns your name. If this does not work, you will receive a mark of zero.

A Node class is given. You are to create Queue and Stack ADTs using a linked implementation. The implementations are linked Nodes.

A class called MyQueue is given. You are to implement the methods enqueue(x), dequeue(), and length(). An item enqueued should be added to the end of the queue, and an item dequeued should be removed and returned from the beginning. The function length() should return the number of items in the queue. This function should be O(1).

A class called MyStack is given. You are to implement the methods push(x), pop(), and length(). An item pushed should be added to the top of the stack, and an item popped should be removed and returned from the top. The function length() should return the number of items in the stack. This function should be O(1).

You cannot use Python's list in your implementation. This includes the methods appends, pop, etc. You must use the Node class given.

Use Lab1Tester.py to test your code
Example command line:

Lab 2 - Trees, BST and AVL

Create a file called Lab2-YourStudentNumber.py. Incorrectly named files will receive a mark of zero.

First, create a method called getName() that returns your name. If this does not work, you will receive a mark of zero.

You are given the class MyTree in the template file. The follow methods getLeft(), getRight(), getData(), are given. Do not change them. The method __init__(x) is also given. You may add to this. You are to implement the insert(x) and getHeight() methods. Each child should itself be a MyTree object.

The insert(x) method should be implemented with a recursive algorithm. The final return is the root node. The getHeight() method should return the height of the node. The height of a leaf node should be zero.

A class called MyBST that extends MyTree is given. Override the method insert(x) to meet the definitions of a Binary Search Tree. Create a method called __contains__(x) that returns true if x is in the tree.

A class called MyAVL that extends MyBST is given. Override the method insert(x) to meet the definitions of an AVL Tree. Create a method called getBalanceFactor() that returns the balance factor of the node. It is suggested that you implement the methods leftRotate() and rightRotate().

Use Lab2Tester.py to test your code