كيفية إدراج/حذف في شجرة البحث الثنائية في C ؟
https://stackoverflow.com/questions/676048
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
نوعا ما يجب أن أضع السابق ج الأسئلة على قضية عقد هذا واحد هو أكثر أهمية الآن...
لقد سبق مشفرة إدراج وحذف وظائف على شجرة البحث الثنائية ولكن حذف وظيفة غير مكتملة.وهناك زوجين من الأشياء التي كنت بحاجة إلى مساعدة في...
1) هو إدراج وظيفة جيدة أو يمكن تحسين بطريقة أو بأخرى ؟
2) بلدي حذف وظيفة يفتقر إلى حذف عقدة مع كل من اليسار واليمين الطفل.لقد بحثت كثيرا في الساعات القليلة الماضية لكن لم أجد الطريقة المناسبة للقيام بذلك.
2.أ) كيف يمكنني حذف عقدة مع 2 العقد الأطفال?
2.ب) كما في السؤال الأول ، هو حذف وظيفة جيدة أو يمكن تحسينها ؟ هذا واحد وأنا أعلم أنه يمكن أن لأني تكرار الكثير من التعليمات البرمجية في تلك المحاذير ولكن أنا لا أرى كيف يمكن تحسين ذلك, أنا بحاجة إلى مساعدة على ذلك أيضا.
typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;
typedef struct sClientProfile {
char *clientName;
int clientAge;
int clientNIF;
} nClientProfile;
typedef struct sClientTree {
ClientProfile clientProfile;
char *clientName;
ClientTree leftTree;
ClientTree rightTree;
} nClientTree;
void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
if(!*cTree) {
ClientTree new = (ClientTree)malloc(sizeof(nClientTree));
if(!new) {
perror("malloc");
}
new->clientName = strdup(cProfile->clientName);
new->clientProfile = cProfile;
new->leftTree = NULL;
new->rightTree = NULL;
*cTree = new;
} else {
if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
addClientToTree(&(*cTree)->leftTree, cProfile);
} else {
addClientToTree(&(*cTree)->rightTree, cProfile);
}
}
}
void deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return;
int nCompare = strcmp((*cTree)->clientName, cName);
if(nCompare > 0) {
deleteClientFromTree(&(*cTree)->leftTree, cName);
} else if(nCompare < 0) {
deleteClientFromTree(&(*cTree)->rightTree, cName);
} else {
if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
cliPtr = NULL;
*cTree = NULL;
} else if(!(*cTree)->leftTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->rightTree;
} else if(!(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->leftTree;
} else {
// MISSING DELETE CASE
}
}
}
ستلاحظ على الأرجح ولكن اسمحوا لي أن مجرد 2 ملاحظات:
- هذه الشجرة يستخدم سلاسل بدلا من العادي الباحث التمثيل.هذا هو السبب في أنني استخدام strcmp() على طول الطريق, أعتقد أنني في استخدام ذلك الحق.
- أنا لا استخدام العودية ، أنا بدلا من تمرير المؤشر (هيكل المؤشر في هذه الحالة) و العمل مع ذلك.يبدو أكثر, ولكن في المستقبل أريد أن أعود النجاح القيمة إذا كانت العقدة تم حذفها.
التحديث أدناه:
لقد عملت نسخة تكرارية حذف وظيفة ولكن أنا لا أحب بعض الأشياء عن ذلك ، ربما يمكن تحسين (أو لا) ولكن لا أستطيع أن أرى كيف.لقد حاولت أيضا رمز الحالة كان في عداد المفقودين ، حذف عقدة مع 2 تشايلدز, لكنه لا يعمل كما ينبغي...
لقد علق رمز كله حيث أعتقد رمز يمكن تحسين أين المشكلة.لقد المسمى أيضا تلك المشاكل كما أ ، ب (لا يوجد ب بعد الآن) ، C و D حتى نتمكن من الرجوع إليها بسهولة.
bool deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return FALSE;
ClientTree currPtr = *cTree;
ClientTree prevPtr = NULL;
int nCompare;
while(currPtr) {
nCompare = strcmp(currPtr->clientName, cName);
if(nCompare > 0) {
prevPtr = currPtr;
currPtr = currPtr->leftTree;
} else if(nCompare < 0) {
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
/*
* A)
*
* The following cases have 3 lines in common, the free()
* calls and return statement. Is there anyway to improve
* this code and make it more compact?
*
* Of course, the printf's are to be removed...
*/
if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
printf("CASE #1\n");
*cTree = NULL;
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else if(!currPtr->leftTree || !currPtr->rightTree) {
printf("CASE #2\n");
if(prevPtr->leftTree == currPtr) {
prevPtr->leftTree = currPtr->rightTree;
} else {
prevPtr->rightTree = currPtr->leftTree;
}
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else {
printf("CASE #3\n");
ClientTree tempPtr = currPtr->rightTree;
while(tempPtr->leftTree) {
tempPtr = tempPtr->leftTree;
}
/*
* C)
*
* This has a big problem...
*
* If you take a look at the ClientProfile structure,
* in the first post, you'll see two ints
* (clientNIF/clientAge) and one char* (clientName).
*
* The problem is that the following code line is only
* copying the integer data, not the string. For some
* reason, the string remains the old one.
*
* I tried to use strdup() directly on clientName like:
* currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
* but it still doesn't work.
*
* Why everything is being copied but the strings?
*/
currPtr->clientProfile = tempPtr->clientProfile;
/*
* D)
*
* Is there anyway to not call the function itself
* and make the while loop once again and delete the
* corresponding leaf?
*/
return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
}
}
}
return FALSE;
}
المحلول
عند حذف عقدة عليك أن تفعل شيئا حيال الأطفال.
إذا كان هناك أي الأطفال - لا توجد مشكلة.يمكنك فقط إزالة العقدة.
إذا كان هناك ترك الطفل أيضا لا توجد مشكلة ؛ إزالة عقدة نقل تركت الطفل في مكانه.
نفسه على حق الطفل ؛ مجرد نقل الطفل إلى مكان حذف عقدة.
المشكلة تأتي عندما تريد حذف العقدة التي لديها كل من اليسار واليمين الأطفال.هل يمكن أن تتحرك إلى اليسار أو اليمين الطفل في مكان حذف عقدة ، ولكن ماذا بعد ذلك هل عن الطفل و الشجرة?
الحل هو هذا ؛ يمكنك تحديد موقع الوريث المنطقي عقدة يتم حذفها.من المنطقي خليفة ، أعني هذا ؛ نقول لديك شجرة مصنوعة من الاعداد الصحيحه و حذف عقدة مع قيمة 35, الوريث المنطقي هو ثاني أكبر عدد.أليس كذلك ؟ إذا كنت تفعل في النظام الأقدام ، سيكون عنصر تأتي بعد العنصر أنك تحذف.
الآن هناك قاعدة بسيطة للعثور على منطقية خليفة ، تذهب حق واحد (لديك دائما الحق في ذلك لأن هذا هو الحال حيث لديك طفلين) ثم تذهب أقصى اليسار كما يمكنك.
هذا العنصر يمكنك في نهاية المطاف في الخلف المنطقي.إنه أكبر من حذف عنصر (ذهبت في البداية ، هل تتذكر؟) لكنه أصغر القادم أكبر عنصر.
الآن, هذا العنصر دائما واحد فقط أو لا أطفال - لأنك ذهبت اليسار بقدر ما تستطيع, أتذكر ؟ لذا لا يمكنك أن تترك أي أكثر من ذلك - لأنه لا يوجد اليسار بحيث أن العنصر لديه أطفال أو مجرد حق الطفل وهذا يعني أنه يقع في واحدة من السهل ربط فئات (بدون أطفال أو طفل واحد فقط).لذلك الربط هذا عنصر من السهل.
الآن يأتي الجزء الممتع - النظر في ذلك ؛ إذا كان هذا القادم أكبر عنصر في نفس المكان في شجرة العنصر الذي تريد حذفه ، الشجرة ستظل سارية المفعول وصحيحة - لأن كل شيء إلى اليسار من كل عنصر هو أصغر شيء إلى اليمين هو أكبر.
لذلك ما عليك القيام به هو هذا ؛ نسخ بيانات المستخدم في ثاني أكبر عقدة إلى عقدة يتم حذفها و حذف أن ثاني أكبر عقدة (فإنه لا يوجد لديه أطفال أو مجرد حق الطفل ، لذلك فإنه من السهل ربط وحذف).
وهذا كل شيء!
لذا أساسا - البحث المنطقي خليفة ربط له من شجرة ثم ضعى بيانات المستخدم إلى عنصر أنت في الواقع أصلا حذف (الذي لم يكن ثم حذف, بالطبع, لأنه ما زال جسديا جزء من شجرة).
نصائح أخرى
أولا: ذكرت أنك لا تستخدم العودية ولكن كل وظيفة لديها المسار المنطقي أن تطلق على نفسها.
على أن الأسئلة:
1) إزالة العودية.هذا يمكن أن تحصل في الكثير من المتاعب إذا شجرة الخاص بك كبيرة بما فيه الكفاية ضربة الخاص بك كومة.دول مجلس التعاون الخليجي لديها دعم محدود ذيل العودية, ولكن أنا لا أعتمد على ذلك.
2) عادة عند حذف الطفل مع عقدتين ، وتعزيز اليسار أو اليمين عقدة إلى موقف حذف عقدة في.(هذا هو غاية في التبسيط الحالة ، أفترض شجرة الخاص بك ليست متوازنة)
2.ب) الخاص بك حذف رمز لديه بعض المشاكل.أنصح المشي من خلال ذلك مع عدد قليل من الحالات الافتراضية.على الفور واضحة بالنسبة لي كانت حرة التعرف على مؤشر ثم deferencing ذلك:
free(cliPtr);
cliPtr->clientProfile = NULL;
بالطبع يمكنك دائما تقلق بشأن أسلوب بمجرد الحصول على صحة الشيء بعيدا مربع.
من الناحية المثالية أن هناك ثلاث حالات حذف عقدة في BST:
حالة 1:
X has no children: remove X
الحالة 2:
X has one children : Splice out X
الحالة 3:
X has two children : swap X with its successor and follow case #1 or #2
لذا المفقودين حذف الحالة:
عندما X (عقدة حذف) واثنين من الأطفال استبدال X مع خليفة X و متابعة حالة رقم 1 أو رقم 2.يمكنك أيضا استبدال مع سابقتها ، قد يكون بديلا جيدا.
if ( X->left && X->right)
{
NODE *Successor = FindSuccessor(X);
X->data = Successor->data;
free(Successor);
}
هذه الثنائية رموز إدراج, حذف,بحث, و الإقلاع عن التدخين.أمثلة:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Binary Tree {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList ll = new LinkedList();
ll.add("\n"+"mai 0020");
ll.add("\n"+"king 0019");
ll.add("\n"+"maan 0002");
ll.add("\n"+"dimple 0024");
ll.add("\n"+"eman 0004");
ll.add("\n"+"lara 0005");
ll.add("\n"+"cute 0008");
ll.add("\n"+"irene 0011");
ll.add("\n"+"sheena 0030");
ll.add("\n"+"aisy 0003");
System.out.println("display: " + ll);
System.out.println("\n\n");
for(int c=0; c<=10; c++) {
System.out.println("select from: 1-insert, 2-delete," +
" 3-display, 4-search, 5-quit");
String x = br.readLine();
int y = Integer.parseInt(x);
switch (y) {
case 1: //inserting
System.out.println("input name");
String n= br.readLine();
System.out.println("input a list number");
String o = br.readLine();
int z = Integer.parseInt(o);
ll.add("\n"+n+" "+z);
break;
case 2: // delete
ll.removeFirst();
break;
case 3: //Display
System.out.println("\n\n"+"List of employee: " + ll);
System.out.println("\n\n");
break;
case 4: //search
System.out.println("\n");
System.out.println("Search");
System.out.println("first element of the Linkedlist is: "
+ ll.getFirst());
System.out.println("\n\n");
System.out.println("last element of linkedlist:"
+ ll.getLast());
break;
case 5: //quit
System.out.println("\n\n\n\n\n"
+ " Thank You Very Much!!!!!!!\n\n\n");
System.exit(0);
break;
}
}
}
}
int delete_value(Tree*&root,Tree*&find,Tree*&ptr,int numb){
if(find->value==number){
//the number exist in the root,so we should find the highest value inside the right brache and replace it with the root.
Tree*ptr2=NULL;
Tree*ptr3=NULL;//pointer pointing to the parent of the last element of ptr2.
ptr2=root->right;
while(ptr2!=NULL){
ptr3=ptr2;
ptr2=ptr2->left;
}
if(ptr2->right!=NULL){
ptr3->left=ptr2->right;
}
swap(ptr2->value,root->value);
delete ptr2;
ptr2=ptr3=NULL;
}
else{
while(find->value!=numb){
if(find->value!=numb){
ptr=find;
}
if(find->value < numb){
find=find->right;
return delete_value(root,find,ptr,numb);
}
else{
find=find->left;
return delete_value(root,find,ptr,numb);
}
}//end of while
}//end of else
//the pointer find is pointing at the element we want to delete.
//the pointer ptr is pointing at the element before the one's we want to delete.
//case 1:the element to delete don't have any children
if(find->right==NULL && find->left==NULL){
if(ptr->left=find){
ptr->left=NULl;
delete find;
}
else{
ptr->right=NULL;
delete find;
}
}//end of the first case.
//case 2:the element has one child it could be to the left or to the right.
//a-child to the right.
if( find->right!=NULL && find->left==NULL ){
Tree*ptr2=find->right;
while(ptr2!=NULL){
ptr2=ptr2->left;//find the highest value in the right branche and replace it with the delete element
}
swap(find->value,ptr2->value);
delete ptr2;
ptr2=NULL;
}
//b-child to the left.
if(find->right==NULL && find->left!=NULL){
Tree*ptr2=find->left;
//check wether the find element is to the right or to the left of ptr.
if(ptr->left==find){
ptr->left=ptr2;
delete find;
}
else{
ptr->right=ptr2;
delete find;
}
}//end of the second case.
//case3: the element has to children.
if(find->right!=NULL&&find->left!=NULL){
Tree*ptr2=find->left;
while(ptr2->right!=NULL){
ptr2=ptr2->right;
}
swap(ptr2->value,find->value);
delete ptr2;
ptr2=NULL;
}//end of case 3.
}//end of the function.
