• پایان فعالیت بخشهای انجمن: امکان ایجاد موضوع یا نوشته جدید برای عموم کاربران غیرفعال شده است

اشکال این برنامه چیه؟ run نمی شه

sahar_karimi

کاربر تازه وارد
تاریخ عضویت
9 جولای 2006
نوشته‌ها
10
لایک‌ها
0
کد:
[CODE]// *****************************************************
// * ThreadedTree.h                                    *
// * Header file for Threaded Binary Search Tree       *
// * Contains ThreadedTree, ThreadedNode, iterator,    *
// *  and const_iterators                              *
// *                                                   *
// *****************************************************

#ifndef THREADED_TREE
#define THREADED_TREE

#include <iostream>
#include <cstdlib>
using std::cout;
using std::endl;

template <typename Etype>
class ThreadedTree {
private:
   /********************************
    * ThreadedTree<>::ThreadedNode *
    * Nested class for tree nodes  *
    * node class                   *
   ********************************/
   class ThreadedNode {
      public:
	 // ThreadedNode - Basic constructor
	 // Initializes node to default values.
         ThreadedNode() : element(), left(NULL), right(NULL) { leftFlag = 0; rightFlag = 0; }

         // ThreadedNode - Constructor that can set a few values
         // Parameters -- elem == initialization element.
         //              leftPtr == initialization left pointer.
         //              rightPtr == initialization right pointer.
         // Initializes node to parameter values.
         ThreadedNode(Etype elem, ThreadedNode* leftPtr, ThreadedNode* rightPtr) : 
            element(elem), left(leftPtr), right(rightPtr) { leftFlag = 0; rightFlag = 0; }

      Etype element;
      ThreadedNode* left;
      ThreadedNode* right;
      int leftFlag;
      int rightFlag;
   };

   /********************/
   /* MEMBER VARIABLES */
   /********************/
   typename ThreadedTree<Etype>::ThreadedNode* root; // points to the root node.
   typename ThreadedTree<Etype>::ThreadedNode* nil; // points to a node outside of tree.
   int treeSize; // # of nodes in the tree.

   /************/
   /* TYPEDEFS */
   /************/
   
   typedef Etype value_type;
   typedef Etype * pointer;
   typedef Etype & reference;
   typedef Etype const * const_pointer;
   typedef Etype const & const_reference;
   
   /*****************************/
   /*  ThreadedTree<>::iterator */
   /*  iterator class           */
   /*****************************/
public:   
   class iterator {
   public:
      // same typedefs as for vector, only now they are in the
      //  iterator class, so (for example), if you want the type
      //  an iterator points to, not only would vector<...>::value_type
      //  work, but so would vector<...>::iterator::value_type.
      //  This is especially helpful once you pass iterator objects
      //  as arguments to generic functions.
      typedef Etype value_type;
      typedef Etype * pointer;
      typedef Etype & reference;
      // iterator
      //    - constructor
      //    - initializes this iterator to point to NULL
      iterator();
      // operator*
      //    - return type : a reference to the element type
      //    - returns by reference the cell storing the element
      //         to which this iterator points.  There is no
      //          error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      Etype & operator*();
      // operator->
      //    - return type : a pointer to the element type
      //    - returns a pointer to the cell storing the element
      //         to which this iterator points.  There is no
      //          error checking done to ensure that this is 
      //          a legal cell on which to perform this operation. 
      Etype * operator->();
      // operator++ (prefix version)
      //    - return type : reference to an iterator
      //    - moves this iterator one position forward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.  
      typename ThreadedTree<Etype>::iterator & operator++();
      // operator-- (prefix version)
      //    - return type: reference to an iterator     
      //    - moves this iterator one position backward in the
      //          collection it points to, and then returns
      //          this iterator after moving it. There is no
      //          error checking done to ensure that this is 
      //          a legal position at which to perform this 
      //          operation.
      typename ThreadedTree<Etype>::iterator & operator--();
      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : an iterator
      //    - moves this iterator one position forward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename ThreadedTree<Etype>::iterator operator++(int ignore);
      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : an iterator
      //    - moves this iterator one position backward in the 
      //          collection it points to, and then returns an
      //          iterator to the position this iterator pointed
      //          to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename ThreadedTree<Etype>::iterator operator--(int ignore); 
      // operator==
      //    - parameters : origVal - previously created iterator
      //    - return value : boolean with true indicating equality
      //    - returns true if this iterator and the parameter 
      //         iterator point to the same location; else returns false
      bool operator==(typename ThreadedTree<Etype>::iterator const & origVal) const;
      // operator!=
      //    - parameters : origVal - previously created iterator
      //    - return value : boolean with true indicating inequality
      //    - returns true if this iterator and the parameter 
      //         iterator point different locations; else returns false
      bool operator!=(typename ThreadedTree<Etype>::iterator const & origVal) const;
   private:
      typename ThreadedTree<Etype>::ThreadedNode * ptr;   // pointer to whatever type of value this
                     // iterator is meant to point to; the entire 
                     // iterator object is basically a wrapper for 
		     // this pointer.
      // iterator
      //    - constructor
      //    - parameters : assignPtr - a pointer to the same type
      //           that this iterator points to
      //    - initializes iterator to point to the same place as
      //         the parameter pointer points to
      iterator(typename ThreadedTree<Etype>::ThreadedNode * assignPtr);

      // these lines give the ThreadedTree class and the const_iterator class
      //   access to the above private members of iterator
      friend class ThreadedTree<Etype>;
      friend class ThreadedTree<Etype>::const_iterator;
   };
   /**********************************/
   /* ThreadedTree<>::const_iterator */
   /* const_iterator class           */ 
   /**********************************/
   class const_iterator {
   public:
      // Same typedefs as for vector, only now they are in the
      // const_iterator class, so (for example), if you want the 
      // type an const_iterator points to, not only would 
      // vector<...>::value_type work, but so would 
      // vector<...>::const_iterator::value_type. This is especially 
      // helpful once you pass iterator objects as arguments to generic 
      // functions.
      typedef Etype value_type;
      typedef Etype const * const_pointer;
      typedef Etype const & const_reference;
      // const_iterator
      //    - constructor
      //    - initializes this const_iterator to point to NULL
      const_iterator();
      // const_iterator
      //    - constructor
      //    - parameters : theIter - an iterator
      //    - initializes this const_iterator to point to the same
      //           location as the parameter iterator
      const_iterator(typename ThreadedTree<Etype>::iterator const & theIter);
      // operator*
      //    - return type : a reference to a value of the element type,
      //        a value that cannot be altered through this reference
      //    - returns by reference the element to which this
      //         const_iterator points; it will not be possible to change
      //         that value through the returned reference. There is no 
      //         error checking done to ensure that this is a legal position
      //         at which to perform this operation.
      Etype const & operator*() const;
      // operator->
      //    - return type : a pointer to a value of the element type,
      //        a value that cannot be altered through this pointer
      //    - returns a pointer to the element to which this 
      //        const_iterator points; it will not be possible to change
      //        that value through the returned pointer. There is no error
      //        checking done to ensure that this is a legal position
      //        at which to perform this operation.
      Etype const * operator->() const;
      // operator++ (prefix version)
      //    - return type : reference to a const_iterator
      //    - moves this const_iterator one position forward in the
      //          collection it points to, and then returns this
      //          const_iterator after moving it. There is no error
      //          checking done to ensure that this is a legal 
      //          position at which to perform this operation.
      typename ThreadedTree<Etype>::const_iterator & operator++();
      // operator-- (prefix version)
      //    - return type: reference to a const_iterator     
      //    - moves this const_iterator one position backward in the
      //          collection it points to, and then returns this
      //          const_iterator after moving it. There is no error
      //          checking done to ensure that this is a legal 
      //          position at which to perform this operation.
      typename ThreadedTree<Etype>::const_iterator & operator--();
      // operator++ (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_iterator
      //    - moves this const_iterator one position forward in the 
      //          collection it points to, and then returns a
      //          const_iterator to the position this const_iterator 
      //          pointed to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename ThreadedTree<Etype>::const_iterator operator++(int ignore);
      // operator-- (postfix version)
      //    - parameters : ignore - argument always the integer 1, to 
      //                       distinguish this from prefix version
      //    - return type : a const_iterator
      //    - moves this const_iterator one position backward in the 
      //          collection it points to, and then returns a
      //          const_iterator to the position this const_iterator 
      //          pointed to before this function was run. There is no
      //          error checking done to ensure that this is a
      //          legal position at which to perform this operation. 
      typename ThreadedTree<Etype>::const_iterator operator--(int ignore);
      // operator==
      //    - parameters : origVal - previously created const_iterator
      //    - return value : boolean with true indicating equality
      //    - returns true if this const_iterator and the parameter 
      //         const_iterator point to the same location; else returns 
      //         false
      bool operator==(
              typename ThreadedTree<Etype>::const_iterator const & origVal) const;
      // operator!=
      //    - parameters : origVal - previously created const_iterator
      //    - return value : boolean with true indicating inequality 
      //    - returns true if this const_iterator and the parameter 
      //         const_iterator point different locations; else returns 
      //         false
      bool operator!=(
              typename ThreadedTree<Etype>::const_iterator const & origVal) const;
     private:
     typename ThreadedTree<Etype>::ThreadedNode * ptr;   // pointer to whatever type of value this
                     // const_iterator is meant to point to; the entire 
                     // const_iterator object is basically a wrapper for 
                     // this pointer.
      // these lines give the threaded tree class access to the above
      // private members of iterator
      friend class ThreadedTree<Etype>;
   };
   /*******************************************/
   /* USER INTERFACE: public member functions */
   /*******************************************/
public:
   // ThreadedTree - Basic constructor
   // Initializes tree to be empty.
   ThreadedTree();
   // ThreadedTree
   // Copy constructor.
   // Parameters -- origVal == previously allocated ThreadedTree object.
   // Initializes object to be a copy of origVal.
   ThreadedTree(ThreadedTree const & origVal);
   // ~ThreadedTree
   //  Destructor.
   //  Deletes dynamically allocated memory!
   ~ThreadedTree(); 
   // operator=
   // Parameters -- origVal == previously allocated ThreadedTree object.
   // Return value -- const reference to this object.  
   // Sets object to be a copy of origVal.
   ThreadedTree const & operator=(ThreadedTree const & origVal);
   // begin
   // Returns an interator pointing to the tree's minimum element.
   typename ThreadedTree<Etype>::iterator & begin();
   // begin
   // Same as non const begin, except it returns a const_iterator instead.
   typename ThreadedTree<Etype>::const_iterator & begin() const;
   // end
   // Returns an iterator to the end of the tree. (One node past maximum element).
   typename ThreadedTree<Etype>::iterator & end();
   // end_const
   // Same as non const end, except it returns a const_iterator instead.
   typename ThreadedTree<Etype>::const_iterator & end() const;
   // find
   // Parameters -- key == element of type Etype.
   // Return value -- an integer.
   // Checks to see if the tree has a node with element value key. If so, 1 is returned. 0 is returned if otherwise.
   int find(Etype const & key) const;
   // insert
   // Parameters -- item == element of type Etype to be inserted into our tree.
   // Inserts param into the tree.
   void insert(Etype const & item);
   // remove
   // Parameters -- item == element of type Etype to be removed from our tree.
   // Removes param from tree.
   void remove(Etype const & item);
   // preorder
   // Prints out values stored by tree in preorder format.
   void preorder() const;	   
   // size
   // Return value -- an integer.
   // Returns the number of nodes in the tree.
   int size() const;
   /********************************************/
   /* IMPLEMENTATION: private member functions */
   /********************************************/
private:
   // copy
   // Parameters -- ptr == a ThreadedNode pointer.
   // Return value -- a ThreadedNode pointer.
   // Makes a new ThreadedNode which is a copy of the
   //        parameter node, and returns it.
   typename ThreadedTree<Etype>::ThreadedNode* copy(typename ThreadedTree<Etype>::ThreadedNode const * ptr);
   // clear
   // Parameters -- ptr == reference to a tree node pointer.
   // Recursively clears the tree. 
   void clear(typename ThreadedTree<Etype>::ThreadedNode * & ptr);
   // find
   // Parameters -- key == element of type Etype.
   //               ptr == a ThreadedNode pointer.
   // Return value -- a boolean value.
   // Recursive helper method for public find function.
   typename ThreadedTree<Etype>::ThreadedNode* find(Etype key, ThreadedTree<Etype>::ThreadedNode * ptr) const;
   // print
   // Parameters -- ptr == a ThreadedNode pointer.
   // Recursive helper method for public preorder function.
   void print(ThreadedTree<Etype>::ThreadedNode const * ptr) const;
   // insert
   // Parameters -- item == item of type Etype to be inserted into our tree
   // Recursive helper method for public insert function.
   void insert(Etype item, typename ThreadedTree<Etype>::ThreadedNode * & ptr);
   // remove
   // Parameters -- item == item to be removed from the tree
   // Recursive helper method for the public insert function.
   void remove(Etype const & item, typename ThreadedTree<Etype>::ThreadedNode * & ptr);
   // getParent
   // Parameters -- item == item of type Etype
   //            -- root == pointer to the root of the tree
   // Searches the tree for a node containing item. If it is found a pointer
   // to the node's parent is returned. Otherwise nil is returned.
   //typename ThreadedTree<Etype>::ThreadedNode * & getParent(Etype item, typename ThreadedTree<Etype>::ThreadedNode * & ptr);
};
#endif


// *****************************************************
// * ThreadedTree.h                                    *
// * Source file for Threaded Binary Search Tree       *
// * Contains ThreadedTree, ThreadedNode, iterator,    *
// *  and const_iterators                              *
// *                                                   *
// *****************************************************

#include "ThreadedTree.h"
#include "String.h"
#include "Asserts.h"
#include <cstddef>
#include <iostream>
using std::cout;
using std::endl;


/*************************** PUBLIC INTERFACE **********************/


template <typename Etype>
ThreadedTree<Etype>::ThreadedTree() : root(NULL), nil(NULL), treeSize(0) {
}

template <typename Etype>
ThreadedTree<Etype>::ThreadedTree(ThreadedTree<Etype> const & origVal) {
	root = copy(origVal.root);
	nil  = nil = new typename ThreadedTree<Etype>::ThreadedNode();
	treeSize = origVal.treeSize;
	typename ThreadedTree<Etype>::ThreadedNode * trav = root;	   
	while (trav->rightFlag == 1)
		trav = trav->right;
	trav->right = nil;
	trav->right->left = trav;
}

template <typename Etype>
ThreadedTree<Etype>::~ThreadedTree() {
	clear(root);
	delete nil;
}

template <typename Etype>
ThreadedTree<Etype> const & ThreadedTree<Etype>::operator=(ThreadedTree<Etype> const & origVal) {
	if (this != &origVal) {
		clear(root);
		delete nil;
		root = copy(origVal.root);
		nil = new typename ThreadedTree<Etype>::ThreadedNode();
		treeSize = origVal.treeSize;
	}
	return *this;
}

template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::begin() {
	typename ThreadedTree<Etype>::ThreadedNode* min;
	if (root->leftFlag == 0)
		min = root;
	else {
		typename ThreadedTree<Etype>::ThreadedNode * trav = root;	   
		while (trav->leftFlag == 1)
			trav = trav->left;
		min = trav;
	}
	return *(new typename ThreadedTree<Etype>::iterator(min));
}

template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::begin() const {
	typename ThreadedTree<Etype>::ThreadedNode* min;
	if (root->leftFlag == 0)
		min = root;
	else {
		typename ThreadedTree<Etype>::ThreadedNode * trav = root;	   
		while (trav->leftFlag == 1)
			trav = trav->left;
		min = trav;
	}
	return *(new typename ThreadedTree<Etype>::const_iterator(min));
}

template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::end() {
	typename ThreadedTree<Etype>::ThreadedNode* max;
	max = root;
	while (max->rightFlag == 1)
		max = max->right;
	max = max->right;
	return *(new typename ThreadedTree<Etype>::iterator(max));
}

template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::end() const{
	typename ThreadedTree<Etype>::ThreadedNode* max;
	max = root;
	while (max->rightFlag == 1)
		max = max->right;
	max = max->right;
	return *(new typename ThreadedTree<Etype>::const_iterator(max));
}

template <typename Etype>
int ThreadedTree<Etype>::find(Etype const & key) const {
	if (root != NULL)
		if (find(key, root)!=NULL)
			return 1;

	return 0;
}

template <typename Etype>
void ThreadedTree<Etype>::insert(Etype const & item) {
	if (root != NULL)
		insert(item, root);
	else {  // insert at root
		root = new typename ThreadedTree<Etype>::ThreadedNode(item, nil, nil);
		nil  = new typename ThreadedTree<Etype>::ThreadedNode(item, root, root);
		root->left = nil;
		root->right = nil;
	}
	treeSize++;
	typename ThreadedTree<Etype>::ThreadedNode * trav = root;	   
	while (trav->rightFlag == 1)
		trav = trav->right;
	trav->right->left = trav;
}

template <typename Etype>
void ThreadedTree<Etype>::remove(Etype const & item) {
	typename ThreadedTree<Etype>::ThreadedNode* temp = find(item, root);
	remove(item, temp);
	typename ThreadedTree<Etype>::ThreadedNode * trav = root;	   
	while (trav->rightFlag == 1)
		trav = trav->right;
	trav->right->left = trav;
}

template <typename Etype>
void ThreadedTree<Etype>::preorder() const {
	print(root);
}

template <typename Etype>
int ThreadedTree<Etype>::size() const {
	return treeSize;
}

/********************** PRIVATE HELPER FUNCTIONS *******************/


template <typename Etype>
typename ThreadedTree<Etype>::ThreadedNode* ThreadedTree<Etype>::copy(typename ThreadedTree<Etype>::ThreadedNode const * ptr) {
	typename ThreadedTree<Etype>::ThreadedNode* returnPtr;
	if (ptr == nil)
		returnPtr = nil;
	if ((ptr->leftFlag == 1)&&(ptr->rightFlag == 1)) {
		returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
		returnPtr->right = copy(ptr->right);
		returnPtr->left = copy(ptr->left);
		returnPtr->rightFlag = 1;
		returnPtr->leftFlag = 1;
	}
	else if (ptr->rightFlag == 1) {
		returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
		returnPtr->right = copy(ptr->right);
		returnPtr->left = nil;
		returnPtr->rightFlag = 1;
		returnPtr->leftFlag = 0;
	}
	else if (ptr->leftFlag == 1) {
		returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
		returnPtr->right = nil;
		returnPtr->left = copy(ptr->left);
		returnPtr->rightFlag = 0;
		returnPtr->leftFlag = 1;
	}
	else {
		returnPtr = new typename ThreadedTree<Etype>::ThreadedNode(ptr->element, NULL, NULL);
		returnPtr->right = nil;
		returnPtr->left = nil;
		returnPtr->rightFlag = 0;
		returnPtr->leftFlag = 0;
	}

	typename ThreadedTree<Etype>::ThreadedNode* trav = returnPtr;
	if (trav->rightFlag == 1) {
		trav = trav->right;
		while (trav->leftFlag == 1)
			trav = trav->left;
		trav->left = returnPtr;
	}
	trav = returnPtr;
	if (trav->leftFlag == 1) {
		trav = trav->left;
		while (trav->rightFlag == 1)
			trav = trav->right;
		trav->right = returnPtr;
	}
	return returnPtr;
}

template <typename Etype>
void ThreadedTree<Etype>::clear(typename ThreadedTree<Etype>::ThreadedNode * & ptr) {
	if (ptr == NULL) {// empty tree
            return;
        }
	if ((ptr->leftFlag == 1) && (ptr->rightFlag == 1)) {
		clear(ptr->left);
		clear(ptr->right);
		delete ptr;

	}
	else if (ptr->leftFlag == 1) {
		clear(ptr->left);
		delete ptr;

	}
	else if (ptr->rightFlag == 1) {
		clear(ptr->right);
		delete ptr;

	}
	else {
                delete ptr;
        }
}

template <typename Etype>
typename ThreadedTree<Etype>::ThreadedNode* ThreadedTree<Etype>::find(Etype key, ThreadedTree<Etype>::ThreadedNode  * ptr) const { 

	if (ptr->element == key)
		return ptr;
	else {
		if( (ptr->element > key) && (ptr->leftFlag == 1) )
			return find(key, ptr->left);
		else if(ptr->element > key)
			return NULL;
		if ( (ptr->element < key) && (ptr->rightFlag == 1) )
			return find(key, ptr->right);
		else if(ptr->element < key)
			return NULL;
	}
}

template <typename Etype>
void ThreadedTree<Etype>::print(ThreadedTree<Etype>::ThreadedNode const * ptr) const {
	if (ptr != NULL)	
		cout << ptr->element << endl;
	if ( (ptr->leftFlag == 1) && (ptr->rightFlag ==1) ) {
		print(ptr->left);
		print(ptr->right);
	}
	else if(ptr->leftFlag == 1)
		print(ptr->left);
	else if (ptr->rightFlag == 1)
		print(ptr->right);

}

template <typename Etype>
void ThreadedTree<Etype>::insert(Etype item, typename ThreadedTree<Etype>::ThreadedNode * & ptr) {
	if ((ptr->element < item)&&(ptr->rightFlag == 0)) {
		typename ThreadedTree<Etype>::ThreadedNode* temp = ptr->right;
		ptr->right = new typename ThreadedTree<Etype>::ThreadedNode(item, NULL, NULL);
		ptr->rightFlag = 1;
		ptr->right->right = temp;
		ptr->right->left = ptr;
	}
	else if (ptr->element < item)
		insert(item, ptr->right);
	else if ( (ptr->element > item) && (ptr->leftFlag == 0) ) {
		typename ThreadedTree<Etype>::ThreadedNode* temp = ptr->left;
		ptr->left = new typename ThreadedTree<Etype>::ThreadedNode(item, NULL, NULL);
		ptr->leftFlag = 1;
		ptr->left->right = ptr;
		ptr->left->left = temp;
	}
	else
		insert(item, ptr->left);
}

template <typename Etype>
void ThreadedTree<Etype>::remove(Etype const & item, typename ThreadedTree<Etype>::ThreadedNode * & ptr) {

	if ((ptr->leftFlag == 1)&&(ptr->rightFlag == 0)) {
		typename ThreadedTree<Etype>::ThreadedNode* trav = root;
		typename ThreadedTree<Etype>::ThreadedNode* parent;
		cout << "case 1\n";
		cout << "val: " << ptr->element << endl;
		cout << "lval: " << ptr->left->element << endl;
		cout << "rval: " << ptr->right->element << endl;
		while ((trav->left != ptr)&&(trav->right != ptr)){
			if (root == ptr){
				trav == NULL;
				break;
			}
			if (ptr->element < trav->element)
				trav = trav->left;
			else
				trav = trav->right;
		}
		parent = trav;
		if (parent == NULL){
			root == root->left;
			root->right = nil;
			nil->left = root;
			delete ptr;
			return;}
		if ((parent->leftFlag == 1)&&(parent->left == ptr))
			parent->left = ptr->left;
		else
			parent->right = ptr->left;

		trav = ptr;
		if (trav->leftFlag == 1) {
			trav = trav->left;
			while (trav->rightFlag == 1)
				trav = trav->right;
			trav->right = ptr->right;
		}

		delete ptr;
	}
		if ((ptr->leftFlag == 0)&&(ptr->rightFlag == 1)) {
		typename ThreadedTree<Etype>::ThreadedNode* trav = root;
		typename ThreadedTree<Etype>::ThreadedNode* parent;
		cout << "case 2\n";
		cout << "val: " << ptr->element << endl;
		cout << "lval: " << ptr->left->element << endl;
		cout << "rval: " << ptr->right->element << endl;
		while ((trav->left != ptr)&&(trav->right != ptr)){
			if (root == ptr){
				trav == NULL;
				break;
			}
			if (ptr->element < trav->element)
				trav = trav->left;
			else
				trav = trav->right;
		}
		parent = trav;
		if (parent == NULL){
			root == root->right;
			delete ptr;
			return;}
		if ((parent->leftFlag == 1)&&(parent->left == ptr)) // ptr is the left child
			parent->left = ptr->right;
		else
			parent->right = ptr->right;
			trav = ptr;
		if (trav->leftFlag == 1) {
			trav = trav->right;
			while (trav->leftFlag == 1)
				trav = trav->left;
			trav->left = ptr->left;
		}
			delete ptr;
	}
	if ((ptr->leftFlag == 0)&&(ptr->rightFlag == 0)) {
		cout << "case 3\n";
		cout << "val: " << ptr->element << endl;
		cout << "lval: " << ptr->left->element << endl;
		cout << "rval: " << ptr->right->element << endl;

		if ((ptr->right->left == ptr)&&(ptr->right != nil)) {
			cout << "3l\n";
			ptr->right->left = ptr->left;
			ptr->right->leftFlag = 0;
		}
		if ((ptr->left->right == ptr)&&(ptr->left !=nil)) {
			cout << "3r\n";
			ptr->left->right = ptr->right;
			ptr->left->rightFlag = 0;
		}
			delete ptr;
	}
	if ((ptr->leftFlag == 1)&&(ptr->rightFlag == 1)) {

		cout << "case 4\n";
		cout << "val: " << ptr->element << endl;
		cout << "lval: " << ptr->left->element << endl;
		cout << "rval: " << ptr->right->element << endl;
		typename ThreadedTree<Etype>::ThreadedNode* IOS = ptr->right;
		while (IOS->leftFlag == 1)
			IOS = IOS->left;
			ptr->element = IOS->element;

		remove(IOS->element, IOS);
	}
}
// getParent

/************************* ITERATOR FUNCTIONS ***********************/


template <typename Etype>
ThreadedTree<Etype>::iterator::iterator() : ptr(NULL) {
	}

template <typename Etype>
Etype & ThreadedTree<Etype>::iterator::operator*() {
	return ptr->element;
}

template <typename Etype>
Etype * ThreadedTree<Etype>::iterator::operator->() {
	return &(ptr->element);
}

template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::iterator::operator++() {
	if (ptr->rightFlag == 0){
		ptr = ptr->right;
		return *this;
		}
	ptr = ptr->right;
	while (ptr->leftFlag == 1)
		ptr = ptr->left;
	return *this;
}

template <typename Etype>
typename ThreadedTree<Etype>::iterator & ThreadedTree<Etype>::iterator::operator--() {
	if (ptr->leftFlag == 0){
		ptr = ptr->left;
		return *this;
		}
	ptr = ptr->left;
	while (ptr->rightFlag == 1)
		ptr = ptr->right;
	return *this;
}

template <typename Etype>
typename ThreadedTree<Etype>::iterator ThreadedTree<Etype>::iterator::operator++(int ignore) {
	typename ThreadedTree<Etype>::iterator temp = *this;
	if (ptr->rightFlag == 0){
		ptr = ptr->right;
		return temp;
		}
	ptr = ptr->right;
	while (ptr->leftFlag == 1)
		ptr = ptr->left;
	return temp;
}

template <typename Etype>
typename ThreadedTree<Etype>::iterator ThreadedTree<Etype>::iterator::operator--(int ignore) {
	typename ThreadedTree<Etype>::iterator temp = *this;
	if (ptr->leftFlag == 0){
		ptr = ptr->left;
		return temp;
	}
	ptr = ptr->left;
	while (ptr->rightFlag == 1){
		ptr = ptr->right;
	}
	return temp;
}

template <typename Etype>
bool ThreadedTree<Etype>::iterator::operator==(typename ThreadedTree<Etype>::iterator const & origVal) const {
	return (ptr == origVal.ptr);
}

template <typename Etype>
bool ThreadedTree<Etype>::iterator::operator!=(typename ThreadedTree<Etype>::iterator const & origVal) const {
	return (ptr != origVal.ptr);
}

template <typename Etype>
ThreadedTree<Etype>::iterator::iterator(ThreadedTree<Etype>::ThreadedNode* assignPtr) : ptr(assignPtr) {
}

/****************** CONST_ITERATOR FUNCTIONS **********************/


template <typename Etype>
ThreadedTree<Etype>::const_iterator::const_iterator() : ptr(NULL) {

}

template <typename Etype>
ThreadedTree<Etype>::const_iterator::const_iterator(typename ThreadedTree<Etype>::iterator const & theIter) {
	ptr = theIter.ptr;
}

template <typename Etype>
Etype const & ThreadedTree<Etype>::const_iterator::operator*() const {
	return ptr->element;
}

template <typename Etype>
Etype const * ThreadedTree<Etype>::const_iterator::operator->() const {
	return &(ptr->element);
}

template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::const_iterator::operator++() {
	if (ptr->rightFlag == 0){
		ptr = ptr->right;
		return *this;
		}
	ptr = ptr->right;
	while (ptr->leftFlag == 1)
		ptr = ptr->left;
	return *this;
}

template <typename Etype>
typename ThreadedTree<Etype>::const_iterator & ThreadedTree<Etype>::const_iterator::operator--() {
	if (ptr->leftFlag == 0){
		ptr = ptr->left;
		return *this;
		}
	ptr = ptr->left;
	while (ptr->rightFlag == 1)
		ptr = ptr->right;
	return *this;
}

template <typename Etype>
typename ThreadedTree<Etype>::const_iterator ThreadedTree<Etype>::const_iterator::operator++(int ignore) {
	typename ThreadedTree<Etype>::const_iterator temp = *this;
	if (ptr->rightFlag == 0){
		ptr = ptr->right;
		return temp;
		}
	ptr = ptr->right;
	while (ptr->leftFlag == 1)
		ptr = ptr->left;
	return temp;
}

template <typename Etype>
typename ThreadedTree<Etype>::const_iterator ThreadedTree<Etype>::const_iterator::operator--(int ignore) {
	typename ThreadedTree<Etype>::const_iterator temp = *this;
	if (ptr->leftFlag == 0){
		ptr = ptr->left;
		return temp;
	}
	ptr = ptr->left;
	while (ptr->rightFlag == 1){
		ptr = ptr->right;
	}
	return temp;
}

template <typename Etype>
bool ThreadedTree<Etype>::const_iterator::operator==(typename ThreadedTree<Etype>::const_iterator const & origVal) const {
	return (ptr == origVal.ptr);
}

template <typename Etype>
bool ThreadedTree<Etype>::const_iterator::operator!=(typename ThreadedTree<Etype>::const_iterator const & origVal) const {
	return (ptr != origVal.ptr);
}
template class ThreadedTree<int>;
template class ThreadedTree<String>;
[/CODE]
 
بالا