经过几个问题，一些不错的答案和友好的帮助在这里。我在二叉树中删除后得到了我的麻烦，我建议，我不能只删除树中最大的数字，因为它可能不是最后一个，或者它的子代数为1,2或全无，所以我做了在下面的代码中，我用了很多注释的希望，希望对您有所帮助。我现在实际上不知道的是，即使我不知道代码是否可以正常运行，我该如何在公共场合调用此RemoveLargest()函数，随后又在main中调用它。
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
template<class T>
class BinaryTree
{
struct Node
{
T data;
Node* lChildptr;
Node* rChildptr;
Node(T dataNew)
{
data = dataNew;
lChildptr = NULL;
rChildptr = NULL;
}
};
private:
Node* root;
void Insert(T newData, Node* &theRoot) //Insert elements into the tree start.
{
if(theRoot == NULL)
{
theRoot = new Node(newData);
return;
}
if(newData < theRoot->data)
Insert(newData, theRoot->lChildptr);
else
Insert(newData, theRoot->rChildptr);
} //end.
void PrintTree(Node* theRoot) //print me the tree /start
{
if(theRoot != NULL)
{
PrintTree(theRoot->lChildptr);
cout<< theRoot->data<<" \n";
PrintTree(theRoot->rChildptr);
}
} //end.
T Largest( Node* theRoot) // show me largest number /start.
{
if ( root == NULL )
{
cout<<"There is no tree";
return -1;
}
if (theRoot->rChildptr != NULL)
{
return Largest(theRoot->rChildptr);
}
T value = theRoot->data;
return value;
} //end.
void RemoveLargest(Node* theRoot) //remove the largest priority number from tree /start.
{
Node* current; //the current tree?
Node* parent; //the parent of the current node?
current=theRoot;
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
//Node with single child.
if((current->lChildptr == NULL && current->rChildptr != NULL)||(current->lChildptr != NULL && current->rChildptr == NULL))
{
if(current->lChildptr == NULL && current->rChildptr != NULL)
{
if(parent->lChildptr==current)
{
parent->lChildptr = current->rChildptr;
delete current;
}
else
{
parent->rChildptr = current->rChildptr;
delete current;
}
}
else //left child ok, no right child
{
if(parent->lChildptr==current)
{
parent->lChildptr = current->lChildptr;
delete current;
}
else
{
parent->rChildptr = current->lChildptr;
delete current;
}
}
return;
}
//We found a leaf(a node with not a single child)
if(current->lChildptr == NULL && current->rChildptr == NULL)
{
if (parent->lChildptr == current)
parent->lChildptr = NULL;
else
parent->rChildptr = NULL;
delete current;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (current->lChildptr != NULL && current->rChildptr != NULL)
{
Node* checkr;
checkr = current->rChildptr;
if((checkr->lChildptr == NULL)&&(checkr->rChildptr == NULL))
{
current=checkr;
delete checkr;
current->rChildptr = NULL;
}
else //right child has children
{
//if the node's right child has a left child
//Move all the way down left to locate smallest element
if ((current->rChildptr)->lChildptr != NULL)
{
Node* lcurr;
Node* lcurrp;
lcurrp = current->rChildptr;
lcurr = (current->rChildptr)->lChildptr;
while(lcurr->lChildptr != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->lChildptr;
}
current->data = lcurr->data;
delete lcurr;
lcurrp->lChildptr = NULL;
}
else
{
Node* temp;
temp = current->rChildptr;
current->data = temp ->data;
current->rChildptr = temp->rChildptr;
delete temp;
}
}
return;
}
};
public:
BinaryTree()
{
root = NULL;
}
void AddItem(T newData)
{
Insert(newData, root);
}
void PrintTree()
{
PrintTree(root);
}
T Largest()
{
return Largest(root);
}
void RemoveLargest()
{
RemoveLargest();
}
};
int main()
{
BinaryTree<int> *myBT = new BinaryTree<int>();
myBT->AddItem(5);
myBT->AddItem(1);
myBT->AddItem(4);
myBT->AddItem(2);
myBT->AddItem(3);
//for(int i = 0; i < 10; i++) //randommal tolti fel/fill with random
//myBT->AddItem(rand() % 100);
cout << "BinaryTree:" << endl; //kilistazaa a fat/ list my tree
myBT->PrintTree();
cout << "Largest element: " << myBT->Largest() << endl; //visszaadja a legnagyobb elemet/shows the largest number
myBT->RemoveLargest(); //suposed to delet the largest number
myBT->PrintTree(); //shows list again
}
编辑了代码，现在它正在运行，它在创建树，显示了最大的代码，但是在我调用remove函数后仍然崩溃了……= /
最佳答案
就像我之前说的，我认为您正在使事情变得过于复杂。在二进制搜索树及其节点中的键之间的关系的背景下，您必须考虑这意味着您的节点是最大的节点。
如果节点是树中最大的节点，则它不可能具有正确的子代指针，因为正确的子代必须具有更大的键。然后，如果您知道它最多具有一个左子节点，则只需将其节点替换为可能为空的左子节点，即可完成。
T ExtractLargest(Node*& n){
if (!n)
return -1;
if (n->rChildptr)
return ExtractLargest(n->rChildptr);
T result = n->data;
Node *d = n;
n = n->lChildptr;
delete d;
return result;
}
关于c++ - 在二叉树解决方案中删除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8194686/