数据结构与算法--二叉查找树转顺序排列双向链表

柔情只为你懂 2023-01-22 15:51 92阅读 0赞

#### 二叉查找树转顺序排列双向链表 ####

*  题目：输入一颗二叉查找树，将二叉查找树转成一个排序的双向链表，要求不能创建任何新节点，只调整树节点中指针的指向。例如下图所示：  
    ![在这里插入图片描述][20210520171704721.png]
 *  本次二叉查找树节点定义使用之前文章 [数据结构与算法–二叉查找树实现原理][Link 1]中节点定义，下文中相关api实现同样使用该文中的方法，文中对二叉查找树相关的api有详细的说明推演，如有问题可到文中查看。节点实例如下：

/** * 二叉树节点对象定义 * * @author liaojiamin * @Date:Created in 15:24 2020/12/11 */
    public class BinaryNode implements Comparable { 
        private Object element;
        private BinaryNode left;
        private BinaryNode right;
        private int count;
    ............

*  理论基础：
    
     *  二叉树中节点与双向链表的节点都存在两个指针，只是指向不同而已。
     *  二叉搜索树中左子节点总是小于主节点，右子节点总是大于主节点，在中序遍历中就是顺序的将每个节点读取
     *  那么我们通过中序遍历的思想将二叉查找树转顺序双向链表，将原先指向左节点的指针调整为链表的指向前一个节点，指向右节点的指针指向后一个节点
     *  如上方式得到我们转换的结果
 *  问题分析：
    
     *  有关树的题型我们必然会想到递归的，有树遍历必有递归，再者递归必然只考虑最简单情况，这样不至于将自己绕进去
     *  考虑三层节点最简单情况，如上图中，分三部分 10 根节点，6 为根节点的左子树，14 为根节点的右子树
     *  根据链表定义，10 节点将和左子树的8 链接，和右子树的12 链接
     *  也就是中序遍历的顺序 （4，6，8）–> 10 -->（12,14，16）
     *  左子树为例，只需要增加两个指针指向，4–>6, 8–>6 两个指针，最后返回8 节点
     *  记录当前节点为current，pLastNodeInList指向需要改变指向的节点，当递归到current = 6，左子树pLastNodeInList指向最小节点4，只需要增加指针指向current.setleft = pLastNodeInList && pLastNodeInList.right=current，其实第一个是已经存在的，但是仅仅是左节点情况存在，我们左右节点统一处理，这样用一个递归解决。接着回到上一节点pLastNodeInList = current = 6，
     *  继续递归右子树，current=8, current.left = pLastNodeInList = 6 && pLastNodeInList .right = current， 此处第二步骤指针已经存在，同样统一处理。
     *  那么我们将每一个左，右子树用同样规则递归处理得到最终的结果，我们最终返回pLastNodeInList ，指向root节点
     *  在递归left方向得到链表头
 *  图解分析：

![在这里插入图片描述][20210521145831914.gif]

*  通过如上分析有如下代码：

/** * 二叉查找树转顺序排列的双向链表 * * @author liaojiamin * @Date:Created in 14:27 2021/5/19 */
    public class ConvertBinaryToList { 
    
        public static void main(String[] args) { 
            BinaryNode node = new BinaryNode(null, null, null);
            BinarySearchTree searchTree = new BinarySearchTree();
            Random random = new Random();
            for (int i = 0; i < 8; i++) { 
                node = searchTree.insert(random.nextInt(100), node);
            }
            printMiddle(node);
            BinaryNode doubleLink = convertBinary(node);
            BinaryNode headNode = doubleLink;
            while (headNode.getLeft() != null) { 
                headNode = headNode.getLeft();
            }
            while (headNode.getRight() != null) { 
                System.out.print("value: " + headNode.getElement());
                System.out.print("left: " + (headNode.getLeft() != null ? headNode.getLeft().getElement() : ""));
                System.out.print("right: " + (headNode.getRight() != null ? headNode.getRight().getElement() : ""));
                System.out.println();
                headNode = headNode.getRight();
                if(headNode.getRight() == null ){ 
                    System.out.print("value: " + headNode.getElement());
                    System.out.print("left: " + (headNode.getLeft() != null ? headNode.getLeft().getElement() : ""));
                    System.out.print("right: " + (headNode.getRight() != null ? headNode.getRight().getElement() : ""));
                }
            }
        }
    
        /** * 二叉查找树转双向链表，顺序 * 递归处理后，找出最左节点 */
        public static BinaryNode convertBinary(BinaryNode root) { 
            BinaryNode pLastNodeInList = null;
            pLastNodeInList = convertNode(root, pLastNodeInList);
            BinaryNode pHeadOfLast = pLastNodeInList;
            while (pHeadOfLast != null && pHeadOfLast.getLeft() != null) { 
                pHeadOfLast = pHeadOfLast.getLeft();
            }
            return pHeadOfLast;
        }
    
        public static BinaryNode convertNode(BinaryNode node, BinaryNode pLastNodeInList) { 
            if (node == null) { 
                return pLastNodeInList;
            }
            BinaryNode current = node;
            if (current.getLeft() != null) { 
                //递归左节点
                pLastNodeInList = convertNode(current.getLeft(), pLastNodeInList);
            }
            //此时node节点是根，将左子树的最大节点pLastNodeInList 设置为根的left节点
            current.setLeft(pLastNodeInList);
            if (pLastNodeInList != null) { 
                //此时的pLastNodeInList 是左子树的最大节点，他的right应该是root，也就是当前的current
                pLastNodeInList.setRight(current);
            }
            //此时左节点干完，左节点的最大节点是当前root也就是current
            pLastNodeInList = current;
            //递归右节点
            if (current.getRight() != null) { 
                pLastNodeInList = convertNode(current.getRight(), pLastNodeInList);
            }
            return pLastNodeInList;
        }
    
        /** * 中序遍历 */
        public static void printMiddle(BinaryNode root) { 
            if (root == null || root.getElement() == null) { 
                return;
            }
            printMiddle(root.getLeft());
            System.out.println(root.getElement());
            printMiddle(root.getRight());
        }
    
    }

[上一篇：数据结构与算法–复杂链表的复制][Link 2]  
[下一篇：数据结构与算法–字符串的排列组合问题][Link 3]

[20210520171704721.png]: /images/20221020/c893d32ea45a4ada88498ec942d6ad39.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/111231303
[20210521145831914.gif]: /images/20221020/a2819bf416c44905bb1ecc267633831b.png
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/116990882
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/117223345