סדנא תרגיל 8 שאלה 1

benny++C, נכתב ע"י Benny, סדנא ב++C, תרגילים, תרגילים בסדנא ב++CLeave a Comment

פעולות על עצים בינאריים,

  • פונקציה המחזירה את המספר העלים בעץ
  • פונקציה המחזירה את גובה העץ
  • פונקציה המחליפה בין הבנים של כל קודקוד בעץ ויוצרת עץ חדש שהוא תמונת מראה של העץ המקורי
  • פונקציה המחזירה את מספר הבנים השמאליים בעץ שהם יחידים

 

 

תכנית ראשית ומימושים של המחלקות


  /******************************
 targil: 8/1 2 3
 lecturer: david Cohen
 discription: opration on trees
 
 *******************************/
#include <iostream>
#include <string>
using namespace std;
#include "SearchTree.h"
#include "Tree.h"
int main()
{


	SearchTree<int> T1;
	cout << "enter 10 numbers\n";
	int x, y;
	for (int i = 0; i<10; i++)
	{
		cin >> x;
		T1.add(x);
	}
	cout << "inorder: ";
	T1.inOrder();
	
	cout << "\nenter 0-6:\n";
	cin >> x;
	while (x != 0)
	{
		switch (x)
		{
		case 1: cout << "# of leaves: " << T1.leaves() << endl;
			break;
		case 2: cout << "height of tree: " << T1.height() << endl;
			break;
		case 3:T1.reflect();
			cout << "reflected tree: ";
			T1.inOrder();
			T1.reflect();
			cout << endl;
			break;
		case 4: cout << "# left sons only: " << T1.onlyLeftSon() << endl;
			break;
		case 5: cout << "enter a number ";
			cin >> y;
			cout << "level of " << y << " on tree: " << T1.level(y) << endl;
			break;
		case 6: cout << "enter a number ";
			cin >> y;
			T1.remove(y);
			cout << "after removing " << y << ": ";
			T1.inOrder();
			cout << endl;
		}
		cout << "enter 0-6:\n";
		cin >> x;
	}
	return 0;
}
  /******************************
enter 10 numbers
1 2 5 2 3 6 5 2 1 4
inorder: 1 1 2 2 2 3 4 5 5 6
enter 0-6:
2
height of tree: 6
enter 0-6:
1
# of leaves: 4
enter 0-6:
2
height of tree: 6
enter 0-6:
5
enter a number 1
level of 1 on tree: 0
enter 0-6:
2
height of tree: 6
enter 0-6:
5
enter a number 4
level of 4 on tree: 5
enter 0-6:

 *******************************/

המחלקה Tree

#include <utility>
#pragma	once
#include <iostream>
#include <string>

	//--------------------------------------------------------
	//  Inner class Node
	//      a single Node from a binary tree
	//--------------------------------------------------------
	template <class T>
	class Node
	{
	public:
		Node* left;
		Node* right;
		T value;
		Node(T val) : value(val), left(NULL), right(NULL){}
		Node(T val, Node<T>* l, Node<T>* r)
			: value(val), left(l), right(r){}
	}; //end of Node class
//-----------------------------------
//  class Tree (Binary Trees)
//  process nodes in Pre/In/Post  order
//-----------------------------------
template <class T>
class Tree
{
protected:


	Node<T>* root;

public:
	Tree() { root = NULL; }	 // initialize tree
	~Tree();
	int isEmpty() const;
	void clear() { clear(root); root = NULL; }
	void preOrder() { preOrder(root); }
	void inOrder() { inOrder(root); }
	void postOrder() { postOrder(root); }

	virtual void process(T val) { cout << val << " "; }
	virtual void add(T val) = 0;
	virtual bool search(T val) = 0;
	virtual void remove(T val) = 0;
	int leaves(){ return leaves(root); }
	int height(){ return height(root); }
	void reflect(){  reflect(root); }
	int onlyLeftSon(){ return onlyLeftSon(root); }
	int sumEvens(int);

private:
	int   sum(Node<int>* root, int level, int max);
	void  clear(Node<T>* current);
	void  preOrder(Node<T>* current);
	void  inOrder(Node<T>* current);
	void  postOrder(Node<T>* current);
	int leaves(Node<T> * current); //
	int height(Node<T> * current); //
	void reflect(Node<T> * current); //
	int onlyLeftSon(Node<T> * current);

	void swap(Node<T> *& current_left, Node<T> *& current_right)
{

	Node<T> * tmp = current_left; //swap
	current_left = current_right;
	current_right = tmp;

}



};


template <class T>
int Tree<T>::sumEvens(int max)
{
	return sum(root, 0, max);
}

template <class T>
int Tree<T>::sum(Node<int>* root, int level, int max)
{
	int x = 0;
	if (root)
	{
		level++;  // increment level
		if (level <= max)
		{
			int even = (root->value % 2) ? 0 : root->value;
			x = even + sum(root->left, level, max)
				+ sum(root->right, level, max);
			cout << "level = " << level << ". value = " << root->value
				<< ". sum = " << x << endl;
			return x;
		}
		else
			return 0;
	}
	else
		return 0;
}

template <class T>
Tree<T>::~Tree() // deallocate tree
{
	if (root != NULL)
		clear(root);
}

template <class T>
void Tree<T>::clear(Node<T>* current)
{
	if (current)
	{    // Release memory associated with children
		if (current->left)
			clear(current->left);
		if (current->right)
			clear(current->right);
		delete current;
	}
}

template <class T>
int Tree<T>::isEmpty() const
{
	return  root == NULL;
}

// PreOrder processing of tree rooted at current
template <class T>
void Tree<T>::preOrder(Node<T>* current)
{    // visit Node, left child, right child
	if (current)
	{   // process current Node
		process(current->value);
		// then visit children
		preOrder(current->left);
		preOrder(current->right);
	}
}

// InOrder processing of tree rooted at current
template <class T>
void Tree<T>::inOrder(Node<T>* current)
{    // visit left child, Node, right child
	if (current)
	{
		inOrder(current->left);
		process(current->value);
		inOrder(current->right);
	}
}


// PostOrder processing of tree rooted at current
template <class T>
void Tree<T>::postOrder(Node<T> * current)
{    // visit left child, right child, node
	if (current)
	{
		postOrder(current->left);
		postOrder(current->right);
		process(current->value);
	}
}

template <class T>
int Tree<T>::leaves(Node<T> * current)
{
	if (current==NULL) // if the tree is empty 
	{
		return 0;
	}
	if (current->left==NULL&&current->right==NULL)  //its maen: is the last node--> no sons return 1 
		return 1;
	return leaves(current->left)+leaves(current->right);
}
template <class T>
int Tree<T>::height(Node<T> * current)
{

	if (!current)
	{
		return 0;
	}
	return 1 + max(height(current->left),height(current->right));
	
 
}


template <class T>
void Tree<T>::reflect(Node<T> * current) //added function
{
	if (!current) // empty tree
		return; 
	reflect(current->left); 
	reflect(current->right); 
swap(current->left,current->right);
}


template <class T>
int Tree<T>::onlyLeftSon(Node<T> * current)
{
	if (!current)
		return 0;
			if (!current->right&&current->left)
		return onlyLeftSon(current->left) + 1;
			if (current->right&&!current->left)
			return onlyLeftSon(current->right);
	else
{return onlyLeftSon(current->right);
		return onlyLeftSon(current->left);
}
}

המחלקה SearchTree

#pragma once
#include "Tree.h"
#include <utility>


template <class T>
class SearchTree : public Tree<T>
{
public:
	// protocol for search trees
	void add(T value);
	bool search(T value)
	{
		return search(this->root, value);
	}
	void remove(T value){ return remove(this->root, value); }
	int level(T val){ if(level(this->root, val)==-1)return -1;
	else return level(this->root, val); }

private:
	void add(Node<T>* current, T val);
	bool search(Node<T>* current, T val);
	void remove(Node<T>*& current, T value);
	int level(Node<T>* current, T val);
		Node<T>*  succ(Node<T>* current){
		Node<T>* succ1 = NULL;
		if (current->right)
			succ1=min(current->right);
	
	return succ1;
	}

	Node<T>*  min(Node<T>* current){if (current->left)return min(current->left);
	return current;}
};

template <class T>
void SearchTree<T>::add(T val)
{
	// add value to binary search tree 
	if (!this->root)
	{
		this->root = new Node<T>(val);
		return;
	}
	add(this->root, val);
}

template <class T>
bool SearchTree<T>::search(Node<T>* current, T val)
{
	// see if argument value occurs in tree
	if (!current)
		return false;	// not found
	if (current->value == val)
		return true;
	if (current->value < val)
		return search(current->right, val);
	else
		return search(current->left, val);
}

template <class T>
void SearchTree<T>::add(Node<T>* current, T val)
{
	if (current->value < val)
	{  // add to right subtree
		if (!current->right)
		{
			current->right = new Node<T>(val);
			return;
		}
		else
			add(current->right, val);
	}
	else
	{	// add to left subtree
		if (!current->left)
		{
			current->left = new Node<T>(val);
			return;
		}
		else
			add(current->left, val);
	}
}

template <class T>
void SearchTree<T>::remove(Node<T>*& current, T val)
{
	// see if argument value occurs in tree
	if (!current)
		return;	// not found
	if (current->value == val)
	{
		if (!current->left &&!current->right){
			delete current;
			current = NULL;
			return;}
		if (current->left &&current->right){
			Node<T>* tmp =succ(current);
			current->value = tmp->value;
			return remove(current->right, current->value);
			
		}
		if (!current->right){
			Node<T>* tmp = current->left;
			delete current;
			current = tmp;
			return;}
		if (!current->left){
			Node<T>* tmp = current->right;
			delete current;
			current = tmp; return;
		}}

	if (current->value < val)
		return remove(current->right, val);
	else
		return remove(current->left, val);
}
template <class T>
int SearchTree<T>::level(Node<T>* current, T val)
{// see if argument value occurs in tree
	if (!search(current,val))
		return -1;	// not found

	if (current->value == val)
		return 0;

	if (current->value < val)
		return 1 + level(current->right, val);
	else
		return 1 + level(current->left, val);




}


כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *