Informatics2-2021/Lab12

A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „ =Exercises= You will need the Tree class from lecture! ==New tree methods== * Write a <tt>count(self)</tt> method to the Tree class which counts the number of nodes i…”)
 
(Exercises)
8. sor: 8. sor:
 
* Write a <tt>height(self)</tt> method which returns the height (depth) of the tree!
 
* Write a <tt>height(self)</tt> method which returns the height (depth) of the tree!
 
* Write an <tt>is_list(self)</tt> method which returns True if the tree is a long path without a junction. False otherwise. The tree is a list if all of the nodes have at most one branches.
 
* Write an <tt>is_list(self)</tt> method which returns True if the tree is a long path without a junction. False otherwise. The tree is a list if all of the nodes have at most one branches.
 +
 +
==Balanced Tree==
 +
Write a Python program to create a Balanced Binary Search Tree (BST) using an array (given) elements where array elements are sorted in ascending order.
 +
==Target Value==
 +
Write a Python program to find the closest value of a given target value in a given non-empty Binary Search Tree (BST) of unique values.
  
 
==Calculator==
 
==Calculator==

A lap 2021. május 4., 13:37-kori változata

Tartalomjegyzék

Exercises

You will need the Tree class from lecture!

New tree methods

  • Write a count(self) method to the Tree class which counts the number of nodes in the tree!
  • Write a sum(self) method which returns the sum of elements in the tree!
  • Write a height(self) method which returns the height (depth) of the tree!
  • Write an is_list(self) method which returns True if the tree is a long path without a junction. False otherwise. The tree is a list if all of the nodes have at most one branches.

Balanced Tree

Write a Python program to create a Balanced Binary Search Tree (BST) using an array (given) elements where array elements are sorted in ascending order.

Target Value

Write a Python program to find the closest value of a given target value in a given non-empty Binary Search Tree (BST) of unique values.

Calculator

We will improve the expression tree from the lecture. Make an empty Node class first!

  • Write its constructor with one parameter: a string containing the mathematical expression to calculate. Let's suppose for now that there are only two operations: + and * and there are no parenthesis, neither negative numbers.
    • If the string is a number, then store that number in self.data as a float number.
    • If not then search for an operation in it. Cut the string at a + character (if found any) and store the operator in self.data Also set self.left to the recursive result on the first part of the string (before the operation) and set the self.right to the recursive reult on the second part (after the operation).
    • Make the same with * operation if there was no +
  • Write a calculate method for this class
  • Implement other operations such as - / and power: ^
  • Write a __str__ method which prints the expression
    • This was already implemented in the lecture just make it a method.
    • Implement a so called polish normal form

You can even handle parenthesis. First remember the parenthesis function from the previous lab!

  • If the input string is entirely inside a parenthesis then erase the outermost parenthesis
  • Find the lowest precedence operation outside a parenthesis
  • Use recursion!
Személyes eszközök