二叉排序树 转 链表

一、目标

算法：二叉排序树 转成 单向链表。 返回链表头结点。
方案：left 置空，right 为下一个节点。要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

二叉排序树 的具体实现逻辑已经在其他文章中实现。本文再次基础上实现 二叉排序树 转 单链表。

二、定义节点

    /**
     * 树中的节点
     */
    public static class TreeNode {
        int data;          //本例中以 int 型数据为例
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;

        public TreeNode(int data) {
            this.data = data;
        }
    }

三、实践

实现的思路其实就是二叉树 中序遍历 的思路。使用一个stack的结构辅助实现，出站的顺序即是 中序遍历 的顺序，把出栈的 节点 连起来就构成了一个单链表。

    /**
     * 算法：二叉排序树 转成 单向链表。 返回链表头结点。
     * 方案：left 置空，right 为下一个节点。要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
     */
    public TreeNode getSingleList(){
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack();
        TreeNode target = root;
        while (target != null){
            stack.push(target);
            target = target.leftChild;
        }

        /**
         *  出栈的顺序就是 中序遍历。 出栈时，把所有节点串联成单链表即可。
         */
        TreeNode head = stack.peek();
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            TreeNode tmp = node.rightChild;
            while (tmp != null){
                stack.push(tmp);
                tmp = tmp.leftChild;
            }

            node.leftChild = null;
            node.rightChild = stack.isEmpty() ? null : stack.peek();
        }

        return head;
    }

四、扩展

要求：把二叉排序树 转成 双向链表。 返回链表尾结点。
方案：left 为上一个节点，right 为下一个节点。要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

    /**
     * 算法：二叉排序树 转成 双向链表。 返回链表尾结点。
     * 方案：left 上一个节点，right 为下一个节点。要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
     */
    public TreeNode getDoubleList(){
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack();
        TreeNode target = root;
        while (target != null){
            stack.push(target);
            target = target.leftChild;
        }

        TreeNode cache = null;
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            TreeNode tmp = node.rightChild;
            while (tmp != null){
                stack.push(tmp);
                tmp = tmp.leftChild;
            }

            node.leftChild = cache;
            node.rightChild = stack.isEmpty() ? null : stack.peek();
            cache = node;
        }

        return cache;
    }

实现思路跟转成单链表逻辑基本一致，只要再把 leftChild的值赋值即可。