删除的最低值以二进制搜索树

本文介绍了删除的最低值以二进制搜索树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我写了这个，不管怎样它的结束了删除我所有的左侧上树不仅是最左叶。

我找不到我的错误，有人可以帮忙吗？

结构节点* delMin（结构节点**根）{    结构节点*电流= *根;    结构节点* b4Current;    而（（电流 - ＆GT; m_ls）== NULL）{        b4Current =电流;        电流=电流 - ＆GT; m_ls;    }    如果（（电流 - ＆GT; m_rs）== NULL）{        b4Current-＆GT; m_ls = 0;        免费（电流）;    }其他{        b4Current-＆GT; m_ls =电流 - ＆GT; m_rs;        免费（电流）;    }    返回*根;}

解决方案

让我们看看你的函数。

结构节点* delMin（结构节点**根）

您需要一个指向节点指针作为参数，返回新头。这是不必要的。返回头，如果不更新，否则它是唯一有用的。指针到节点的指针方式迎合了那个（恩，应该的，但事实并非如此），从而使返回值是免费的其它信息。

结构节点* b4Current;

在这里，你定义一个未初始化的指针。你应该把它初始化为 NULL 来idicate当前节点，头，没有一个家长。否则指针将是一个垃圾值，可能会导致不确定的行为。

，而（（电流 - ＆GT; m_ls）== NULL）{        b4Current =电流;        电流=电流 - ＆GT; m_ls;    }

在这里，你的情况是错误的：你想只要有一个指针向左走，但你做别的事情：你向左走，如果没有地方去！当头部有一个左孩子，电流将留在头部。否则，这将是 NULL ，这将导致混乱，当您尝试取消对它的引用更高版本。

IF（（电流 - ＆GT; m_rs）== NULL）{        b4Current-＆GT; m_ls = 0;        免费（电流）;    }其他{        b4Current-＆GT; m_ls =电流 - ＆GT; m_rs;        免费（电流）;    }

在的两个分支，如果实际上是一样的，如果你仔细想想。这是一个有点像说：如果（X == 0）Y = 0;否则Y = X;

但你需要一个如果在这里，即是当前的情况下区分是头部或没有。在前一种情况下，你应该更新 *头，后一种情况是你已经写了什么。

您也应该抓住，你不能从空的列表中删除一个节点的情况。

所以：

无效delMin（结构节点**根）{    结构节点*电流= *根;    结构节点* b4Current = NULL;    如果（当前== NULL）返回NULL;    而（电流 - ＆GT;！m_ls = NULL）{        b4Current =电流;        电流=电流 - ＆GT; m_ls;    }    如果（b4Current == NULL）{        *根=电流 - ＆GT; m_rs;    }其他{        b4Current-＆GT; m_ls =电流 - ＆GT; m_rs;    }    免费（电流）;}

不过，因为你是一个指针传递给你的头节点反正，你可以简化功能：

无效delMin（结构节点**根）{    如果（*根== NULL）回报;    而（（*根） - GT;！m_ls = NULL）{        根=及（*根） - GT; m_ls;    }    结构节点*旧= *根;    （*根）=（*根） - GT; m_rs;    免费（旧）;}

您可能有一些难看的（*根）在这儿，但你有很多的辅助变量的废除和如果语句。的想法是，你通过用指针迭代到节点指针加一层间接。 *根会对您的 b4Current 和（*根）的作用 - ＆GT; m_ls 是电流，但 *根开始以一个合理的初始值，即根节点。

I wrote this and somehow it's ending up deleting all my left side on the tree not only the most left leaf.

I can't find my mistake, can someone help?

struct Node *delMin(struct Node **root) { struct Node *current = *root; struct Node *b4Current; while ((current->m_ls) == NULL) { b4Current = current; current = current->m_ls; } if ((current->m_rs) == NULL) { b4Current->m_ls = 0; free(current); } else { b4Current->m_ls = current->m_rs; free(current); } return *root; }

解决方案

Let's look at your function.

struct Node *delMin(struct Node **root)

You take a pointer to node pointer as argument and return the new head. That is unnecessary. Returning the head is only useful if it isn't updated otherwise. Your pointer-to-node-pointer approach caters for that (well, it should, but it doesn't), so that the return value is free for other information.

struct Node *b4Current;

Here, you define an uninitialised pointer. You should initialise it to NULL to idicate that the current node, the head, doesn't have a parent. Otherwise the pointer will be a garbage value that is likely to cause undefined behaviour.

while ((current->m_ls) == NULL) { b4Current = current; current = current->m_ls; }

Here, your condition is wrong: You want to go left as long as there is a pointer, but you do something else: You go left if there isn't anywhere to go! When the head has a left child, current will stay at the head. Otherwise, it will be NULL, which will cause havoc when you try to dereference it later.

if ((current->m_rs) == NULL) { b4Current->m_ls = 0; free(current); } else { b4Current->m_ls = current->m_rs; free(current); }

The two branches of the if are really the same, if you think about. It's a bit like saying: if (x == 0) y = 0; else y = x;.

But you need an if here, namely to distinguish between the case that current is the head or not. In the former case, you should update *head, the latter case is what you have already written.

You should also catch the case that you can't remove a node from an empty list.

So:

void delMin(struct Node **root) { struct Node *current = *root; struct Node *b4Current = NULL; if (current == NULL) return NULL; while (current->m_ls != NULL) { b4Current = current; current = current->m_ls; } if (b4Current == NULL) { *root = current->m_rs; } else { b4Current->m_ls = current->m_rs; } free(current); }

But since you are passing a pointer to your head node anyways, you could simplify the function to:

void delMin(struct Node **root) { if (*root == NULL) return; while ((*root)->m_ls != NULL) { root = &(*root)->m_ls; } struct Node *old = *root; (*root) = (*root)->m_rs; free(old); }

You may have some ugly (*root)s here, but you do away with a lot of auxiliary variables and if statements. The idea is that you add one level of indirection by iterating with a pointer to node pointer. *root takes the role of your b4Current and (*root)->m_ls is your current, except that *root starts with a sensible initial value, namely the root node.