0

BST からルート ノードを削除してから、ツリーを順番に出力しようとしています。ルートの削除に問題があるようです。他のすべてのノードは正常に削除されています。

ルートは 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

削除後にわかるように、ビンツリーは期待どおりではありません。太字のキーは不要です。以下は私のコードです

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);
    }
}

.....任意の助けをいただければ幸いです.....

4

3 に答える 3

0

関数では、関数treeDeleteNodeを呼び出すたびに、の代わりに最初のパラメーターとしてtransplantTree渡す必要があります。これは、この関数でルート ノードを変更でき、これらの変更を変数自体に行う必要があるためです。tree&roottree

于 2013-07-06T09:11:30.267 に答える
0

変化する

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;
}

に

else {
    succs = treeMin (node->rchild);
    parent = getParentNode (root, succs);
    if (parent != node) {
        //TODO:copy succs'content to node instead
        transplantTree (&root, succs, succs->rchild);
        free(succs);
    }
    else {
        transplantTree (&root, node, succs);
        succs->lchild = node->lchild;
        free(node);
    }
}
于 2013-07-06T09:18:45.237 に答える
0 
void treeDeleteNode (binTreeT **tree, binTreeT *node)
{
    binTreeT *sub;

       //* find the place where node should be */
    while (*tree) {
        if (*tree == node) break;
        if ( node->data <= (*tree)->data) tree = &(*tree)->lchild;
        else tree = &(*tree)->rchild;
        }
        /* not found: nothing to do (except freeing node) */
    if ( !*tree) { free(node); return; }

        /* When we get here, *tree points to the pointer that points to node. 
        ** If any of the {l,r}pointers is NULL, the other
        ** will become the new root of the subtree (replacing node)
        */
    if ( !node->lchild) { *tree = node->rchild; free(node); return; }
    if ( !node->rchild) { *tree = node->lchild; free(node); return; }

        /* cut off left subchain of tree, save it, and set it to NULL */
    sub = node->lchild;
    node->lchild = NULL;


        /* find leftmost subtree of right subtree of 'node' */
    for (*tree = node->rchild; *tree; tree =  &(*tree)->lchild) {;}
        /* and put the remainder there */
    *tree = sub;

    free(node);
}
于 2013-07-06T12:38:25.547 に答える