从二叉树的前中后序遍历我们来说递归和快速排序

jiezi

5 年前

我是很喜欢算法的, 打算写一个数据结构与算法系列的记录, 很多都用到了递归, 所以这星期打算说说大家都觉得很简单, 但是我觉得并不简单的递归, 毕竟很多人对递归的认识也就是自己调用自己, 但是我觉得这并不深入, 或者说这并不是递归的实质, 或者说解释递归解释的并不好。

首先我们准备一颗二叉树:

我们需要定义一些术语, 我们所使用的数据结构由结点组成, 结点包含的链接可以为空也可以指向其他结点.

   在二叉树中, 每个结点只能有一个父节点(只有一个例外, 也就是根节点, 它没有父节点), 而且每个结点只有两个链接,
   分别指向自己的左子结点和右子结点. 尽管链接指向的是结点, 但我们可以将每个链接看做指向了另一颗二叉树,
   而这棵树的根节点就是被指向的节点. 因此, 我们可以将二叉树定义为一个空链接
   , 或者是一个有左右两个链接的结点, 每个链接都指向一颗 (独立的) 二叉树。----《算法》第四版。

前中后序遍历 (这是本篇文章的要讨论的核心问题之一，由前中后序遍历来讨论递归, 然后再到荷兰国旗问题和快速排序)
结点代码:

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

二叉树:

   public class BinaryTree {

    TreeNode root;

    public BinaryTree(TreeNode root) {this.root = root;}

    /**
     * 前序遍历
     */
    public void frontShow(){}

    /**
     * 中序遍历
     */
    public void middleShow(){}
    /**
     * 后序遍历
     */
    public void afterShow(){}
}

虽然百度不招人喜欢, 但是百度百科的一些词条编辑的还是不错的.
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

(1) 访问结点本身（N），
(2) 遍历该结点的左子树（L），
(3) 遍历该结点的右子树（R）。

前序遍历: 根节点左子树右子树
中序遍历: 左子树根节点右子数
后序遍历: 左子树右子树根节点

其实组合的话是有六种的, 但是讨论递归的话, 前中后序就足够了.

我们现在来任意的给一颗二叉树, 不用代码。我们来写出前中后序遍历的结果:

前序遍历: 3 8 5 2 6 1 7
中序遍历: 5 2 8 3 1 7 6
后序遍历: 5 2 8 1 7 6 3

前中后序遍历的进一步解释:

当我到达一个结点, 先打印出来, 再去访问其他子结点就是前序遍历
当我到达一个结点, 不是先打印当前结点, 而是接着访问该节点的左子节点, 某个节点没有子节点(或者说子结点是 null)
我就打印当前节点, 这就是中序遍历

以前序遍历为例, 我首先打印根节点, 然后判断它的左子节点是否为空, 如果非空, 打印该节点, 然后接着进行这样的操作,
翻译成代码就是这样的:

在 BinaryTree 中的代码:

 public void frontShow(){System.out.println(root.data);
    if (root.leftNode != null){root.leftNode.frontShow();
    }
    if (root.rightNode != null){root.rightNode.frontShow();
    }
}

结点中的代码也是这样的,

public void frontShow(){System.out.println(root.data);
        if (root.leftNode != null){root.leftNode.frontShow();
        }
        if (root.rightNode != null){root.rightNode.frontShow();
        }
}

中后序代码把打印顺序调整一下就可以了, 其实这个很好理解, 不是多么酷炫的事情.
以下一个问题在我个人看来才是值得值得思考的, 就是程序在遍历二叉树的过程, 每个节点经过了几次。
其实这个问题, 也是十分简单, 你按着程序走就可以了.

首先来到 3, 接着来到 8, 接着来到 5, 然后发现 5 的左右子节点都是空的, 然后回到 ….

这里再介绍另一种在形式上略有不同的前序遍历方式:

public void frontShow(TreeNode root){if (root == null){return;}
        System.out.println(data);
        frontShow(root.leftNode);
        frontShow(root.rightNode);
    }

这种形式上的前中后序遍历:

每个节点会到达三次, 前序遍历就是第一次碰到的时候打印出来, 中序是第二次，后序是第三次
各位有兴致的话可以自己写一写, 画一画.

请注意上面那张图, 虽然他十分的丑, 但是大家不觉得它像一个栈吗? 递归就是程序在帮你压栈.

那既然递归是系统在帮你压栈，那非递归版我就自己压栈, 不让程序帮我们压栈就可以了吗?
我们先用下图来演示非递归版的遍历:

许多时候, 问题的规模是会影响我们的判断, 为了解决问题, 我们可以先把问题的规模先降低到看起来容易解决的地步, 再试着去解决问题, 如果解决了, 我们再逐步的扩大问题的规模

荷兰国旗问题: 给定一个数组 arr 和一个数 num, 请把小于 num 的数放在 num 的左边, 大于 num 的数放在 num 右边。
等于 num 的数放在中间

例子: 输入: arr [5,7,5,8,1,9,10] ,num =5

       输出:   [1, 5, 5, 8, 9, 10, 7]]

思路:

    > 准备一个变量 less 和 more。1. less 区域内 (即数组下标 <= less) 全部是小于 num 的,         
             2. more 区域内 (即数组下标 >more) 全部是大于 num
             3. 我们需要一个变量来帮助我们遍历数组。在一开始的时候,less  = -1 , more = 数组的长度。这代表刚开始这两个区域还不存在
             当 arr[curr] < num 的时候, less 区域的下一个数和 arr[curr]交换。然后 less 右移一个位置,
             curr 右移一个位置
             当 arr[curr] > num 的时候, more 区域的上一个数和 arr[curr]交换。然后 more 左移一个位置，此时我们是无法保证从 more 区域的上一个数, 究竟是大于 num 还是小于 num,
             因此我们仍然需要将 num 和这个数进行比较.
             以上的思路翻译成代码是用循环来完成的, 那么循环结束的条件是什么呢?
             curr 的左侧是 less 区域,  当排序完成的时候, (less,curr]区域为等于 num 的区域,
             但是当 curr + 1 = more 时, 这个时候 arr[curr+1]还是未进行判断的,
             我们仍然需要对 arr[curr+1] 和 num 进行比较

那这跟快速排序有什么问题呢? 我们来思考一下快速排序(这里讨论是基础版的快速排序)。快速排序是一种分治的排序算法, 它将一个数组分成两个子数组, 将两部分独立的排序。荷兰国旗就相当于快速排序中的切分过程。快速排序的关键就在于这个切分过程。

快速排序的思想就是:

            
首先根据 num, 将数组切分成两个子数组, 然后再对这两个子数组进行切分, 当子数组的数量小于 2, 默认数组即为有序。理解这个切分过程对快速排序来说十分的重要

这也是我在写算法的时候考虑的一个问题,

答案有两种:
1. 严谨一点的话就是数学建模, 通过数学来证明你算法的正确性。2. 利用计算机这个工具来印证我们算法的正确性, 意思就是试, 找到一个虽然是正确的, 但是时间复杂度不那么好的正确算法。通过随机函数产生大量的样本, 比较你的算法和时间复杂度不那么好的正确算法所产生的结果。这种方法

比如说对于排序算法,
首先利用随机函数不断的产生各种各样的数组, 并且向数组中填充随机数.

然后将数组复制一份, 给正确的算法用

然后比较两个算法的结果.

从二叉树的前中后序遍历我们来说递归和快速排序

二叉树

二叉树的定义

非递归版

从荷兰国旗问题到快速排序

荷兰国旗问题

快速排序

如何证明你的算法的正确性