++C עצים בינארים

[Ghosthunter]

מה המבנה של העץ?

[נעמה.]

הרגע אמרו לי שיקבלו גם את התשובה של ההחלפה בין הבן הימני לשמאלי (ולא בין הערכים) ואת זה כבר יש לי.

תודה!!!

אפשר לשאול עוד שאלה או זה כבר חוצפה??

אני אשאל, אשמח אם תענו:

פונקציה למחיקת איבר מעץ חיפוש בינארי: זה נכון??

oid SearchTree<T>::Remove(T val)
{
	Node<T>*current=root,*parent;
	if(current->value==val)
	{
		RemoveTop(current);
		return;
	}
	else
	{	while(current->value!=val)
		{
			parent=current;
			if(val>current->value)
			{					
				current=current->right;
			}
			else
			{
				current=current->left;
			}
		}
	}
	if(current)//אם האיבר אותו רוצים למחוק הוא עלה
	{
		if(current->value<=parent->value)
		{
			delete current;
			parent->left=NULL;
		}
		else
		{
			delete current;
			parent->right=NULL;
		}
		return;
	}
	else
		if((current->left!=NULL)&&(current->right!=NULL))// אם לאיבר אותו רוצים למחוק יש שני בנים
		{
      Node<T>*ezer=current;//מצביע לאבא
			ezer=current->left;
			while(ezer->right!=NULL)
			{
				ezer=ezer->right;
				if(ezer->right->right==NULL)
				{
					break;
				}
			}
			current->value=ezer->value;
			delete ezer;
			ezer=NULL;
		}
		else//אם לאיבר אותו רוצים למחוק יש בן אחד
		{
			if(current->value<=parent->value)
			{
				parent=current->left;
				delete current;
			}
			else
			{
				parent=current->right;
				delete current;
			}

		}
}

יש הפרדה בין מחיקת השורש לכל איבא אחר. :-\

[Ghosthunter]

הרעיון במחיקה:

אם אין בנים - תמחקי את הצומת בלי חשבון לאף אחד.

יש בן אחד - תשימי את המידע של הבן אצל האב.

יש 2 בנים - תמצאי את העוקב לאב, צחליפי ביניהם, ותמחקי את העוקב(לעוקב אין 2 בנים).

[נעמה.]

כן, אני יודעת שזה מה שצריך לעשות, מה שהסתבכתי איתו- זה כאשר יש בן אחד, אני צריכה שהסבא(האבא של האיבר אותו אני רוצה למחוק) יצביע לנכד (לבן של האיבר אותו אני רוצה למחוק) ואני לא יודעת איך לעשות מצביע לסבא. ???

[נעמה.]

ע"מ למצוא את העוקב אני הולכת מהאיבר אותו רוצים למחוק- צעד אחד ימינה, ואז שמאלה עד הסוף.

מה עושים אם יש אני רוצה למחוק את השורש, ויש לו רק בן שמאלי???

[Boomerang]

העוקב של צומת עם בן ימני הוא הצאצא הכי שמאלי בתת העץ הימני.

העוקב של צומת בלי בן ימני הוא האב הקדמון הראשון שהצומת נמצאת במסלול השמאלי שלו.

נראה לי.