none
从二叉查找树中删除带有一个子节点的节点算法? RRS feed

答案

  • Hi wavetekgroup,

    欢迎来到C#论坛。

    根据我的搜索,你可以按以下步骤来实现。

    首先,查看右子节点是否为空(null)。如果是,就接着查看是否在根节点上。如果在,就把左子节点移动到根节点上。否则,如果当前节点是左子节点,那么把新的父节点的左子节点设置为当前的左子节点。或者,如果在右子节点上,那么把父节点的右子节点设置为当前的右子节点。

    祝你愉快!


    Bob Shen [MSFT]
    MSDN Community Support | Feedback to us

    2012年3月26日 5:57
    版主
  • 是这样嘛?

            public bool DeleteOne(int key)
            {
                Node current = root;
                Node parent = root;
                bool isLeftChild = true;
                while (current.Data != key)
                {
                    parent = current;
                    if (key < current.Data)
                    {
                        isLeftChild = true;
                        current = current.Left;
                    }
                    else
                    {
                        isLeftChild = false;
                        current = current.Right;
                    }
                    if (current == null)
                        return false;
                }
                if (current.Right == null)
                    if (current == root)
                        root = current.Left;
                    else if (isLeftChild)
                        parent.Left = current.Left;
                    else
                        parent.Right = current.Right;
                if (current.Left == null)
                    if (current == root)
                        root = current.Right;
                    else if (isLeftChild)
                        parent.Left = current.Right;
                    else
                        parent.Right = current.Right;
                return true;
            }


    万物皆变,规则永恒。

    2012年3月28日 0:44

全部回复

  • 直接在上一级节点中删除就好了,遍历的时候就找不到这个节点以及这个节点下面的子节点了。 不过这里不涉及内存回收。


    family as water

    2012年3月21日 5:33
  • 没你说的这么简单吧,首先要检查这个节点是否有一个子节点,如果是,还要判断是左还是右,还要判断父节点是否为根节点。。。。


    万物皆变,规则永恒。

    2012年3月21日 6:21
  • Hi wavetekgroup,

    欢迎来到C#论坛。

    根据我的搜索,你可以按以下步骤来实现。

    首先,查看右子节点是否为空(null)。如果是,就接着查看是否在根节点上。如果在,就把左子节点移动到根节点上。否则,如果当前节点是左子节点,那么把新的父节点的左子节点设置为当前的左子节点。或者,如果在右子节点上,那么把父节点的右子节点设置为当前的右子节点。

    祝你愉快!


    Bob Shen [MSFT]
    MSDN Community Support | Feedback to us

    2012年3月26日 5:57
    版主
  • 是这样嘛?

            public bool DeleteOne(int key)
            {
                Node current = root;
                Node parent = root;
                bool isLeftChild = true;
                while (current.Data != key)
                {
                    parent = current;
                    if (key < current.Data)
                    {
                        isLeftChild = true;
                        current = current.Left;
                    }
                    else
                    {
                        isLeftChild = false;
                        current = current.Right;
                    }
                    if (current == null)
                        return false;
                }
                if (current.Right == null)
                    if (current == root)
                        root = current.Left;
                    else if (isLeftChild)
                        parent.Left = current.Left;
                    else
                        parent.Right = current.Right;
                if (current.Left == null)
                    if (current == root)
                        root = current.Right;
                    else if (isLeftChild)
                        parent.Left = current.Right;
                    else
                        parent.Right = current.Right;
                return true;
            }


    万物皆变,规则永恒。

    2012年3月28日 0:44
  • Hi wavetekgroup,

    怎么样?它符合你的要求吗?如果还有其它疑问,你可以提出来,谢谢。


    Bob Shen [MSFT]
    MSDN Community Support | Feedback to us

    2012年3月28日 3:00
    版主