关于算法:由DFS到访问者模式

一、Walk与Visit思维

这里,应用一个直观的事实例子来阐明Walk与Visit思维

1. 一个比喻

咱们假如有这样一个小区,小区中的房子都是一座座独立的别墅。这个小区的组织模式呢,有点怪,以树的构造进行组织,就像下图这样

在这里

树的结点–>别墅

树的分支–>连贯别墅的路线

2. Walk程序

假如张三从大门进入来到了这个小区,他要在这个小区漫步,漫步的习惯就是深度优先,则其通过的别墅程序为,

A->B->Null->D-Null->Null->C->Null->Null

(之所以增加null是为了下文中探讨Visit机会时不便, 同时也能够让代码更容易了解与简化,这里能够先疏忽)

而以上的程序称之为Walk程序,其实就是深度遍历的程序(留神, 这里只是通过别墅,并没有进入别墅).

而对于一个给定的树来说,深度遍历的程序是固定的。

3. Visit机会

如果说, 当张三通过某一别墅时, 决定进入别墅访问客人, 或者进入别墅做一些其它事件的话,咱们将要做的事件形象为Visit操作, 对于每一个别墅来说,Visit的机会, 有三种可能. 如下图所示

对于A, 对于A其机会能够是

机会1:走到B之前,还未打算漫步到那里

机会2:从B返回,但还没打算返回C

机会3:从C返回

如果应用代码形容Walk程序与Visit机会, 则是这个样子的.

void walk(TreeNode node) {

    //机会1,还没返回B
    
    walk(node.left);    // 这时,达到了B

    //机会2, 曾经从B返回
    
    walk(node.right);    // 这时,达到了C

    //机会3, 也从C返回了
    
    return;

}

当程序中调用walk(TreeNode A)时, 能够认为达到了结点A.

当波及到树的构造时, 能够依据不同的须要抉择一个或多个机会, 对于每一个机会, 也能够进行不同的操作.

4. 再谈,前序,中序与后序遍历

后面介绍walk与visit,以及visit的三个机会,有什么用呢?

咱们来看其实际上的一个利用。那就是应用以上的模板改写前序,中序,以及后序遍历的代码。先定义一下TreeNode的构造

class TreeNode {
  int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {val = x;}
}

咱们先来看,如何写前序的代码。

这里,咱们须要搞明确,在前序遍历中,visit具体是什么操作,咱们无妨就是打印出结点的值。

那么,这个visit操作放到什么时候来做呢?其实就是机会抉择的问题,那么前序遍历,就是一达到结点,还没拜访左右子结点之前进行操作,所以,咱们能够写出如下代码

//前序
void walk(TreeNode node) {
    //走到空结点, 什么也不做
    if (node == null) return;

    print(node.val);        //还没进入左右结点
    walk(node.left);
    walk(node.right);
    return;
}

同理,中序就是从左结点拜访回来之后,进行打印,代码如下

//中序
void walk(TreeNode node) {
    //走到空结点, 什么也不做
    if (node == null) return;

    walk(node.left);
    print(node.val);        //从左结点回来啦
    walk(node.right);
    return;
}

同理,后序

//后序
void walk(TreeNode node) {
    //走到空结点, 什么也不做
    if (node == null) return;

    walk(node.left);
    walk(node.right);
    print(node.val);
    return;

}

那么,这和咱们平时对前中后序的遍历有什么不同呢?如果咱们不应用walk, visit的思路来写的话,是这样子的

void preOrder(TreeNode node) {
    if(node == null) return;

    print(node.val);
    preOrder(node.left);
    preOrder(node.right);
    return;
}

void inOrder(TreeNode node) {
    if(node == null) return;

    print(node.val);
    inOrder(node.left);
    inOrder(node.right);
    return;
}

void postOrder(TreeNode node) {
    if(node == null) return;

    print(node.val);
    postOrder(node.left);
    postOrder(node.right);
    return;
}

而walk程序,就是深度优先程序,后面说了,对于一个给定的树,只有一种walk程序,而对于visit却有三种机会,代码如下

void walk(TreeNode node) {

    if(node == null) return;

    //operateA()
    walk(node.left);
    //operateB()
    walk(node.right);
    //operateC()
    return;

}

void operateA() {}
void operateB() {}
void opearteC() {}

那么就能够说出两者的不同了

应用walk程序来写三种遍历,其实三种遍历都是同一种程序,只是visit的机会不同罢了。

而应用三种遍历思维来写三种遍历的算法,你看到的是三种不同的程序

而以上两点对待问题的角度其实有很大的区别,应用walk程序不同visit的机会来写,往往能写出更清晰易懂的代码,对于简略的打印可能不显著,上面举一个更简单的例子。

5. 打印2叉树的所有门路

题目形容见

binary-tree-paths

剖析题目, 咱们利用一个变量path来记录从root到以后结点的门路.

这里的要害是抉择操作的机会,以及做哪些操作.也就是visit的机会,以及visit具体要做什么。

首先, 当咱们达到一个结点时, 如果该结点是非叶子结点, 则须要将node.val + “->” 增加到门路中.

如果是叶子结点, 则须要将node.val增加到门路中并且将该门路放到最终的门路汇合paths中.

以上能够是机会1做的操作, 代码如下:

 static public void append(TreeNode node) {

    //叶子结点
    if (node.left == null && node.right == null) {
        path.append(node.val);
        paths.add(path.toString());
        return;
    }

    //非叶子结点
    path.append(node.val + "->");
    return;

}

那么还须要做其它的吗?

以上所做的是往门路中增加的工作, 如果咱们只加不减, 门路就会蕴含在其它结点, 这是谬误的, 所以但咱们来到某一个结点时, 即机会3时, 做以下操作.

 static public void strip(TreeNode node) {

    int valSize = Integer.toString(node.val).length();

    if (node.left == null && node.right == null) {
        path.delete(path.length() - valSize, path.length());
        return;
    }

    path.delete(path.length() - (2 + valSize), path.length());
    return;
}

walk代码,再加上机会一和机会三的操作,就是如下所示代码

static public void walk(TreeNode node) {

    if (node == null) {
        return;
    }

    append(node);
    walk(node.left);
    walk(node.right);
    strip(node);

    return;
}

可见,应用walk思维来解决题目次要是思考分明两点

  1. 抉择操作的机会
  2. 具体是什么操作

而如果是, 利用”遍历”的思维, 可能写出如下的代码

public void innerBinaryTreePaths(TreeNode root) {
    
    int valSize = Integer.toString(root.val).length();
    path.append(root.val);

    if(root.left == null && root.right == null) {
        paths.add(path.toString());
        path.delete(path.length() - valSize, path.length());
        return;
    }

    path.append("->");
    if(root.left != null) {
        innerBinaryTreePaths(root.left);
    }

    if(root.right != null) {
        innerBinaryTreePaths(root.right);

    }
    
    path.delete(path.length() - (2 + valSize), path.length());
    return;
    
}

而这种解法,显然不如第一种清晰。

比拟两种思维的解法。

  1. walk与visit思维 :则将拜访程序与操作解耦合, 写代码时, 咱们只有关怀, 操作的机会以及执行什么操作即可, 写出的代码更加清晰
  2. 一般遍历思维:则拜访程序与操作耦合在一起,代码凌乱不清晰

二 进一步

以上只是介绍了二叉树,其实这种walk与visit具备更广泛的适用性,比方一个多叉树的模板能够是这样

void walk(TreeNode node) {
  
  // 进入第一个子节点之前
  
  for(int i = 0; i < node.childRen.length; i++){
    // 进入每一个子节点之前
    
    walk(node.childRen[i]);
    
    // 从每一个子节点返回之后
    }
  
  // 从所有子节点返回了
}

实际上, 无论是二叉树, 多叉树, 还是图也好, 其Walk程序都能够归结为深度优先程序.

对于二叉树, 拜访机会有三个, n叉树, 拜访机会有n+1个, 图也是相似.

所以波及到这几种数据结构的操作, 都能够利用以上所探讨的思维解决.

三 更进一步: 访问者模式

以上只是阐明了,其在树,图构造上的利用,然而这种思维能够利用在更加一般化的构造中,咱们能够给定任意的构造,而后规定一种程序,再规定操作的机会和具体操作。这就是访问者模式。

其实这个问题的更一般化问题就是访问者模式, 其思维是将算法与构造拆散.

具体介绍见

访问者模式

四 总结

walk与visit思维的实质是:

将在一个数据结构上的操作与该数据结构拆散

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据