菜鸡的算法修炼：二叉搜索树（二叉搜索树与双向链表）

2016 年 3 月 4 日

题目描述(引自剑指offer)

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

菜鸡与大佬的对话

菜鸡修炼坊

数据结构
树	树是由n（n>=0）个有限节点组成一个具有层次关系的集合。满足以下特点： ①每个元素称为结点； ②没有父结点的结点称为根结点； ③除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T0，T1，T2，……，Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树。
二叉树是每个结点最多有两个子树的树结构。
二叉搜索树	二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

题目分析
在了解二叉搜索树的定义之后，菜鸡觉得可以用递归和非递归两种方式来解决。首先考虑递归的方式，首先一个结点的引用标记，然后按照右子树，根，左子树的顺序进行遍历，在遍历的过程中调整指针的指向，并移动引用标记，最后就能得到排序的双向链表，标记引用的就是双向链表的头结点（最小结点）。其次考虑非递归的方式，同样的原理，只不过需要借助栈的数据结构来进行操作。菜鸡理顺思路之后，决定用Java代码实现他的心路历程。

代码实现

// 树的定义

public class TreeNode {

    int value = 0;

    TreeNode left = null;

    TreeNode right = null;




    public TreeNode(int value) {

        this.value = value;

    }

}

public class Solution {

    // 定义结点引用标记

    TreeNode result = null;

    

    // 递归解决方案

    public TreeNode convertByRecursion(TreeNode root) {

        // 递归出口

        if(root == null) return root;

        // 递归遍历右子树

        convertByRecursion(root.right);

        // 找到最右结点，设置引用标记

        if(result == null){

            result = root;

        } 

        // 非最右结点，调整指针指向，并移动引用标记，逐步串起整个链表

        else {

            result.left = root;

            root.right = result;

            result = root;

        }

        // 递归遍历左子树

        convertByRecursion(root.left);

        // 返回链表头结点（最小结点）的引用

        return result;

    }

}

import java.util.Stack;




public class Solution {




    // 非递归解决方案

    public TreeNode convertByNonRecursion(TreeNode root) {

        // 空树直接返回

        if(root == null) return root;

        // 定义结点引用标记

        TreeNode result = null;

        // 申请辅助栈

        Stack stack = new Stack();

        while(root != null || !stack.isEmpty()){

            // 遍历右子树         

            if(root != null) {

                stack.push(root);

                root = root.right;

            }

            else {

                root = stack.pop();

                // 找到最右结点，设置引用标记

                if(result == null) {

                    result = root;

                } 

                // 非最右结点，调整指针指向，并移动引用标记，逐步串起整个链表

                else {

                    result.left = root;

                    root.right = result;

                    result = root;

                }

                // 遍历左子树

                root = root.left;

            }

        }

        // 返回链表头结点（最小结点）的引用

        return result;

    }

}

经过这次修炼，菜鸡对树型结构有了一定的了解，菜鸡发现像链表，树这样递归定义的数据结构，在很多问题上都可以考虑递归的方式去解决。另外，菜鸡还掌握了二叉搜索树的特性，他发现，二叉搜索树在平面上的投影，其实就是有序的线性表。菜鸡越发体会到了基础知识的重要性，也越发体会到活学活用的重要性。菜鸡隐隐察觉到，修炼的终极产物是思想……

About The Author

stack