我试图从我的BST删除根节点,然后打印树 inorder . 根删除似乎是一个问题,所有其他节点都被成功删除 .
Root是20 .
inOrderPrint 5 6 7 8 9 10 17 18 20 23 24 25 29 55 56 57 58 59
提供要删除的节点
20
删除后
5 6 7 8 9 10 17 18 20 5 6 7 8 9 10 17 18 23 24 25 29 55 56 57 58 59
正如你在删除后看到的那样,bintree并不像预期的那样 . 粗体键是不需要的 . 以下是我的代码
void treeDeleteNode (binTreeT **tree, binTreeT *node)
{
binTreeT *succs;
binTreeT *parent;
binTreeT *root = *tree;
if (node->rchild == NULL) {
transplantTree (&root, node, node->lchild);
}
else if (node->lchild == NULL) {
transplantTree (&root, node, node->rchild);
}
else {
succs = treeMin (node->rchild);
parent = getParentNode (root, succs);
if (parent != node) {
transplantTree (&root, succs, succs->rchild);
succs->rchild = node->rchild;
}
transplantTree (&root, node, succs);
succs->lchild = node->lchild;
}
}
void transplantTree (binTreeT **root, binTreeT *old, binTreeT *new)
{
binTreeT *rootRef = *root;
binTreeT *parent;
parent = getParentNode(rootRef, old);
if (NULL == parent) {
*root = new;
}
else {
if (parent->lchild == old) {
parent->lchild = new;
}
else {
parent->rchild = new;
}
}
}
binTreeT* treeMin (binTreeT *tree)
{
while (tree->lchild != NULL) {
tree = tree->lchild;
}
return tree;
}
binTreeT* getParentNode(binTreeT *root, binTreeT* node)
{
binTreeT *parent = NULL;
while (root->data != node->data) {
parent = root;
if (node->data < root->data) {
root = root->lchild;
}
else if(node->data > root->data) {
root = root->rchild;
}
}
return parent;
}
void inOrderPrint (binTreeT *tree)
{
if (NULL != tree) {
inOrderPrint (tree->lchild);
printf("%d \t", tree->data);
inOrderPrint (tree->rchild);
}
}
.....任何帮助赞赏.....
3 回答
在函数
treeDeleteNode
中,每次调用transplantTree
函数时,都应将tree
作为第一个参数而不是&root
传递 . 这是因为可以在此函数中修改根节点,并且应该对tree
变量本身进行这些更改 .更改
至