二叉树中的删除

Question

我一直在尝试在二叉树中实现删除。我知道这三个步骤是：

确定要删除的节点和最深的节点。
用最深节点的数据替换它的数据。
正在删除最深的节点。

我必须遍历整棵树才能找到最深的节点。为了删除该节点，我需要找到它的父节点。有没有其他方法可以不用遍历整棵树来找到它的父节点？

这是我的代码。

tnode* searchNode(Tree &T, int data) {
    tnode* temp = nullptr;
    Queue Q;

    if(!T.root)
        return nullptr;

    enqueue(Q, T.root);
    while(!isEmptyQueue(Q)) {
        temp = dequeue(Q);

        if(temp->data == data) {
            return temp;
        }
        if(temp->left) {
            enqueue(Q, temp->left);
        }
        if(temp->right) {
            enqueue(Q, temp->right);
        }
    }
    return nullptr;
}

tnode* findDeepestNode(Tree &T) {
    tnode *temp = nullptr;
    Queue Q;

    if(!T.root)
        return nullptr;

    enqueue(Q, T.root);
    while(!isEmptyQueue(Q)) {
        temp = dequeue(Q);

        if(temp->left)
            enqueue(Q, temp->left);

        if(temp->right)
            enqueue(Q, temp->right);
    }
    return temp;
}

void removeNode(Tree &T, tnode *search) {
    tnode *temp = nullptr;
    tnode *del = nullptr;
    Queue Q;

    if(!T.root || T.root == search)
        return;

    enqueue(Q, T.root);
    while (!isEmptyQueue(Q)) {
        temp = dequeue(Q);

        if(temp->left) {
            if(temp->left == search) {
                del = temp->left;
                temp->left = nullptr;
                delete del;
                return;
            }
            else
                enqueue(Q, temp->left);
        }

        if(temp->right) {
            if(temp->right == search) {
                del = temp->right;
                temp->right = nullptr;
                delete del;
                return;
            }
            else
                enqueue(Q, temp->right);
        } 
    }
    return;
}

void deleteNode(Tree &T, int data) {
    tnode *search = searchNode(T, data);
    tnode *deepestnode = findDeepestNode(T);

    if(search) {
        search->data = deepestnode->data;
        removeNode(T, deepestnode);
    }
}

我刚开始学习数据结构。我写的代码似乎太长了。我怎样才能缩短这段代码？如果我遵循任何错误的编码习惯，也请纠正我。

Answer 1

仅在该函数中，您可以通过将双指针传递给最深节点及其父节点来找到最深节点及其父节点：

tnode* searchNode(Tree &T, int data, tnode** deepest, tnode **parent) {
    tnode* temp = nullptr;
    tnode* searchNode = nullptr;
    Queue Q,parentQ;

    if(!T.root)
        return nullptr;

    enqueue(Q, T.root);
    enqueue(parentQ, nullptr);
    while(!isEmptyQueue(Q)) {
        temp = dequeue(Q);
        *parent = dequeue(parentQ);
        if(temp->data == data) {
            searchNode = temp;
        }
        if(temp->left) {
            enqueue(Q, temp->left);
            enqueue(parentQ, temp);
        }
        if(temp->right) {
            enqueue(Q, temp->right);
            enqueue(parentQ, temp);
        }
    }
    *deepest = temp;
    return searchNode;
}

修改deleteNode()函数为：

void deleteNode(Tree &T, int data) {
    tnode *deepestnode,*parent;
    tnode *search = searchNode(T, data, &deepestnode, &parent);

    if(search) {
        search->data = deepestnode->data;
        removeNode(T, deepestnode);
    }

}

这样，您可以在一次遍历中获取父节点，现在您可以相应地修改您的删除功能。

二叉树中的删除

Deletion in a Binary Tree

c++

algorithm

binary-tree

data-structures