二元查找树转变成排序的双向链表之C#算法实现

发布时间：2020-12-15 04:43:18 所属栏目：百科来源：网络整理

导读：此题为July在CSDN发布的微软编程面试100题中的第一题，觉得蛮有趣的，今天也拿过来玩玩，July的代码用的是C++实现，可能因为有指针的原因吧，感觉看起来相对比较容易理解整个的实现过程，而我，试着用C#完成这样的功能。完整的题目如下：把二元查找树转变

此题为July在CSDN发布的微软编程面试100题中的第一题，觉得蛮有趣的，今天也拿过来玩玩，July的代码用的是C++实现，可能因为有指针的原因吧，感觉看起来相对比较容易理解整个的实现过程，而我，试着用C#完成这样的功能。

完整的题目如下：

把二元查找树转变成排序的双向链表，要求不能创建任何新的结点，只调整指针的指向。

? ? ? 10

? ? / ?

??6 ? ?14

?/ ? ?/ 4 8 ?12 16

转换成双链表? 4=6=8=10=12=14=16

动手编码之前，先回顾下二叉查找树的特点：任意节点的左子树都要小于当前节点，右子树都要大于当前节点。查询某个值，需要的时间复杂度为O(lgN)。

现在要求将其由树状结构改造成线性结构的双向链表，重点在于，获得当前节点左子树范围内最右节点（也是左子树最大值节点），以及右子树范围内最左节点（也是右子树最小值节点），然后，调整这两个节点当前节点左右顺序。即调整8、10之间和12、10之间的关系。

算法思路：

树根节点，分左右子树。先将当前节点左子树范围内最右节点leftR找出来，再将右子树范围内最左节点rightL找出来（这两步放在一开始，因为此时左右子树内的关系还没改变，先取出来，时间消耗O(lgN)。只是查找到节点，空间上只用到一个索引，不会产生新的内存分配）。
若左子树为叶子节点，则直接设置其右向索引指向其父节点，左向递归结束；否则，将此节点作为根节点，递归调用第一步。
若右子树为叶子节点，则直接设置其左向索引指向其父节点，右向递归结束，否则，将此节点作为根节点，递归调用第一步。
设置根节点的左向节点为leftR，leftR的右向节点为根节点（其左向节点，在b和c两步的递归过程中已经赋值），设置根节点的右向节点为rightL，rightL的左向节点为根节点（其右向节点，在b和c两步的递归过程中已经赋值）

C#源码部分：

首先定义根节点和左右子树节点：

    public MyLinkedNode(int value)
    {
        this.value = value;
    }

    public MyLinkedNode Left
    {
        get { return this.left; }
        set { this.left = value; }
    }

    public MyLinkedNode Right
    {
        get { return this.right; }
        set { this.right = value; }
    }

以下代码为逻辑递归代码：

        //获取左子树的最右节点
        MyLinkedNode leftR = getMostRightNode(node.Left);

        //获取右子树的最左节点
        MyLinkedNode rightL = getMostLeftNode(node.Right);

        //左子树非空，递归处理左子树
        if (null == node.Left)
        {
            ProcessLeftNode(node.Left,node);
        }

        //若右子树非空，递归处理右子树
        if (null == node.Right)
        {
            ProcessRightNode(node.right,node);
        }

        //若左子树最右节点非空，调整与根节点相邻
        if (null != leftR)
        {
            leftR.Right = node;
            node.Left = leftR;
        }

        //若右子树的最左节点非空，调整与根节点相邻
        if (null != rightL)
        {
            rightL.Left = node;
            node.Right = rightL;
        }
    }

    private static void ProcessRightNode(MyLinkedNode right,MyLinkedNode node)
    {
        //若右子树为叶子节点，直接将其左向索引指向父节点，并返回
        if (isLeafNode(right))
        {
            right.Left = node;
            return;
        }

        ProcessTreeToLinked(right);
    }

    private static void ProcessLeftNode(MyLinkedNode left,MyLinkedNode node)
    {
        //若左子树为叶子节点，直接将其右向索引指向父节点，并返回
        if (isLeafNode(left))
        {
            left.Right = node;
            return;
        }

        //本节点当作根节点，递归调用
        ProcessTreeToLinked(left);
    }

    private static bool isLeafNode(MyLinkedNode node)
    {
        return (null == node.Left) &amp;&amp; (null == node.Right);
    }

    private static MyLinkedNode getMostLeftNode(MyLinkedNode right)
    {
        if (null == right)
        {
            return null;
        }

        if (null == right.Left)
        {
            return right;
        }

        return getMostLeftNode(right.Left);
    }

    private static MyLinkedNode getMostRightNode(MyLinkedNode left)
    {
        if (null==left)
        {
            return null;
        }

        if (null==left.Right)
        {
            return left;
        }

        return getMostRightNode(left.Right);
    }

编写这段代码其实不难，难的是如何理清楚解题思路。权当为接下来的面试做准备了，上次面试被问到要实现String.Replace()方法，却不能调用API，不得不说，作为一名测试人员，这样的编码难度对我来说还是比较大的，但并非不可克服，只是，需要继续努力提升自己~轻轻地，对自己说一声，加油~

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!