Skip to content
Ider

沉淀我所学习,累积我所见闻,分享我所体验

Primary Navigation Menu
Menu
  • Home
  • About Ider
    • Who Ider?
    • Why Ider?
    • How Ider?
    • Where Ider?
    • What Ider?

Design Patterns(设计模式)

2021-01-14
14 January
On January 14, 2021
In Design Patterns(设计模式), English Posts(英文写作), Knowledge Base(心得笔库), Mobile Development(移动开发), Software Engineering(软件工程)

ProtoBuf 2.0 method count optimization for android development

The Protocol Buffer library was not initially built for Android, it just turned out to have a Java version to be used in Android, but it’s not optimized for Android apps, for example: it doesn’t consider the method count limit in Android.

So, in this article, I’d like to share some work I found specifically on Protocol Buffer Version 2 that can reduce the method count. If your app is also heavily relying on Protocol Buffer, I hope these approaches are useful for you too.

General Approaches

1. Use Protocol Buffer Java Lite Runtime

Just as the name indicates, the dependency library is much smaller than the regular Protocol Buffer Java runtime, the generated code is also much slimmer. However, the APIs are compatible between those two versions, so the call sites would not be affected when changing the library.

2. Don’t use <Message>OrBuilder interface

For each Protocol Buffer message definition in .proto file, the Protocol Buffer compiler generates an interface named <Message>OrBuilder (<Message> is the name defined in .proto file). This interface would be implemented by the concrete <Message> class and the corresponding Builder.

It might be attractive to use it as a variable type thereby you can depend on abstractions to not concrete classes. But calling methods on Java interface would make Dex take count of those methods.

In reality, every place can directly use either <Message> or Builder, then the optimization tool (like R8, ProGuard) can safely remove the methods declared on the interface.

Special Tricks

Protocol Buffer Java Lite is very good, but if I open the magic box of generated Java classes, I notice it’s still not optimal for Android. There are a couple places I could modify to make it more effective for Android applications.

Instead of copying the Java files and making the change, which is error prone when engineers update the .proto file, I created a script to automate the job. Just add the execution of this script at the end of the Protocol Buffer gradle task, so it works just as a complement of Protocol Buffer code generation process.

[codesyntax lang=”groovy” lines=”normal”]

protobuf {
  protoc {
    artifact = 'com.google.protobuf:protoc:3.7.0'
  }
  plugins {
    javalite {
      artifact = 'com.google.protobuf:protoc-gen-javalite:3.0.0'
    }
  }
  generateProtoTasks {
    all().each { task ->
      task.builtins {
        remove java
      }
      task.plugins {
        javalite { }
      }

      // `getOutputDir()` can only be read during configuration, 
      // so it’s out of action block
      def outputDir = task.getOutputDir(task.plugins[0])
      task.doLast {
          exec {
              commandLine file('protobuf-optimizer.py')
              args outputDir
          }
      }    
    }
  }
}

[/codesyntax]

In the script, I have made the following modification on generated java code.

1. Change the modifier of Builder constructor from private to package

Simply running the sample addressbook.proto from Protocol Buffer tutorial side, you would get a class like the following snippet:

[codesyntax lang=”java” lines=”normal”]

public static final class Person {
    private Person() {}

    protected final Object dynamicMethod(
            com.google.protobuf.GeneratedMessageLite.MethodToInvoke method,
            Object arg0, Object arg1) {
        switch (method) {
            case NEW_BUILDER: {
                return new Builder();
            }
        }
    }

    public static final class Builder {
        private Builder() {}
    }

}

[/codesyntax]

When analyzing the APK file, we could would find some synthetic classes and methods:

This is because the outer class is accessing the private constructor of the inner class. The generated synthetic class would contribute an extra constructor to the Dex file. Therefore, by simply removing the private from Builder(), you can remove such classes and methods.
Read More →

2018-06-29
29 June
On June 29, 2018
In Data Structures(数据结构), Design Patterns(设计模式), Language Tips(语言初试)

隐秘而诡异的Java合成方法

Java程序里其实有很多我们看不到的代码,这些代码由Java编译器在编译过程中生成帮助程序更准确地运行。本文就来深入了解一下由编译器加入到Java代码中的方法(Method),特别是合成方法(Synthetic Method)。

合成方法

合成成员(Synthetic Member)在JVM细则里可以找到简单的定义

A class member that does not appear in the source code must be marked using a Synthetic attribute, or else it must have its ACC_SYNTHETIC flag set.

合成成员包含有合成类(Synthetic Class),合成变量(Synthetic Variable),合成方法(Synthetic Method),本文主要讨论合成方法。

合成方法不出现在.java文件中,不过编译之后会在.class里出现,并可以通过以下几个方法发现它们:

  • 在设置断点进行debug时会在方法栈上看到这些由编译器加入的方法
  • 通过反射(Reflection)查找到方法,通过isSyntehtic()方法来判定是否是合成函数
  • 利用一些反编译工具,比如 javap、JD-GUI、jad,查看.class文件可以找到这些方法

对于一般的Java程序而言并没有什么大的问题,只不过是额外的方法调用,代价比较低。但是像Android,它的Dex文件对于Java的方法有一定的约束,就值得去考虑如何避免额外的方法被生成。下边就来介绍一些常见的会出现合成方法的情况让我们有清楚地了解Java的运行机制。

嵌套类和私有成员

先来看一个代码案例,代码中定义了一个顶层类和嵌套类,互相会方法对方的一些private修饰的方法和字段。

[codesyntax lang=”java” lines=”normal”]

public class Outer {

  private int privateField = 21;
  private Inner inner = new Inner();

  private int privateMethod() {
    return inner.privateMethod();
  }

  private void print() {
    inner.print();
  }

  private static int privateStaticMethod() {
    return 7;
  }

  class Inner {
    private int privateMethod() {
      return privateField;
    }

    private void print() {
      System.out.println(Outer.this.privateMethod());
      System.out.println(privateStaticMethod());
    }
  }

  public static void main(String[] args) {
    Outer outer = new Outer();
    outer.print();
  }
}

[/codesyntax]

之前的文章有介绍了Java的修饰访问符的限制范围,类中由private修饰的成员,只能被该类自身所访问,因此嵌套类的私有成员不应该能被外部类访问。另一方面嵌套类虽然在外部类里面,但其实并不属于外部类的一部分,比如编译上边的代码会得到两个.class文件,Inner类被编译成了package可见的独立类。


Read More →

2016-12-31
31 December
On December 31, 2016
In Design Patterns(设计模式), Reading Notes(阅而后知), Software Engineering(软件工程)

面向对象开发原则:S.O.L.I.D.

solid-oop_wall-skills

一开始学编程的时候,都是在学习程序语言,觉得学好了这门语言就可以写好程序;渐渐地发现算法和数据结构更加的重要,因为语言只是细胞,要依附这些行程肉体才能产生作用;但到了实际生产应用的时候,又会察觉整个好像缺少灵魂,常常只能像僵尸般往一个方向前进,缺少驱动力来动态调整,这力量就来自各种设计模式和开发原则。

经历了越多开发中的痛楚,也越来越发觉“S.O.L.I.D.”开发原则只用几句话所概括出来的真谛和内涵。它们对于软件开发是如此有意义,当然具体的实现依然还是依赖于那些基于需求形成的数据结构和算法,只是利用这些开发原则作为灵魂,让程序走得更远更自由。

 

Single Responsibility Principle(SRP)

A class should have one, and only one, reason to change.

Open Closed Principle(OCP)

You should be able to extend a classes behavior, without modifying it.

Liskov Substitution Principle(LSP)

Derived classes must be substitutable for their base classes.

Interface Segregation Principle(ISP)

Make fine grained interfaces that are client specific.

Dependency Inversion Principle(DIP)

Depend on abstractions, not on concretions.

 

References:
  1. ArticleS.UncleBob.PrinciplesOfOod
  2. SOLID (object-oriented design) – Wikipedia
  3. S is for the Single Responsibility Principle
  4. O is for the Open/Closed Principle
  5. L is for the Liskov Substitution Principle
  6. I is for the Interface Segregation Principle
  7. D is for the Dependency Inversion Principle

(后5个是基于Android开发对这些原则做的阐述)

2016-05-03
03 May
On May 3, 2016
In Design Patterns(设计模式), Knowledge Base(心得笔库), Language Tips(语言初试), Software Engineering(软件工程)

Java的static关键字

已经看过了万能的final关键字在Java中的不同用法和效果,其实static关键字的的用处也很广泛。它的用法更多涉及到面向对象设计(Object-Oriented Design)的思想,有时更加让人迷惑。许多是否应该使用static关键字的决定也常常基于工作经验中形成的约束和规范。本文就来帮助大家解锁static的正确使用姿势,写出更加清晰的代码。

为了更好的了解Java程序,就需要了解代码被编译后的样子,所以下边会涉及到javac和javap这些指令的使用,不用担心都是比较简单直接的用法。也需要借助一些反编译(decompile)工具来查看.class文件,这里用到的是JD-GUI。

  • 静态变量 Static Variable
  • 静态方法 Static Method
  • 静态块 Static Block
  • 静态嵌套类 Static Nested Class
  • 静态引入 Static Import

Static Variable

静态变量(Static Variable)在Java中只有静态成员变量,不同于C++、PHP等,它不允许在方法内定义局部静态变量。静态成员变量也称为类变量,相对的是对象成员变量。这些变量是属于定义的类,而非某个对象实例,但是该类的所有实例都可分享该变量。

用个简单的例子会比较直观一些:
[codesyntax lang=”java” lines=”normal”]

package com.iderzheng.statickeyword;

public class StaticField {
    public static int sField;
    public int mField;

    public void print() {
        System.out.println(
                String.format("%s{sField: %d, mField: %d}", this, sField, mField)
        );
    }

    public static void main(String[] args) {
        StaticField one = new StaticField();
        StaticField two = new StaticField();

        one.sField = 7;
        one.mField = 7;

        two.sField = 21;
        two.mField = 21;

        one.print();
        two.print();

        StaticField.sField = 49;
        // Error: non-static variable mField cannot be referenced from a static context
        // StaticField.mField = 49;
        one.print();
        two.print();
    }
}

[/codesyntax]

编译运行这段代码得到如下结果:

com.iderzheng.statickeyword.StaticField@34469729{sField: 21, mField: 7}
com.iderzheng.statickeyword.StaticField@6d172f8f{sField: 21, mField: 21}
com.iderzheng.statickeyword.StaticField@34469729{sField: 49, mField: 7}
com.iderzheng.statickeyword.StaticField@6d172f8f{sField: 49, mField: 21}

很清楚的看到变量two对sField的修改影响了one中的sField值。而mField在两个对象中是独立互补影响的。也看到可以用类的名字来引用静态变量,这是提倡调用方法,不应该直接用对象变量来引用静态变量,这样做不明确调用的是静态变量,很容易带来副作用。

Static Final Variable

一般在程序中不常定义静态变量,因为静态变量的可被访问和使用的地方比局部变量和对象变量要多,维护起来更加困难。更多时候是跟final结合起来定义常量,对于无法修改的只读变量,就不用担心维护问题了。

对象变量也可以用final修饰定义为常量,只不过每个对象的常量只属于对象自己,而且每个对象都需要分配内存给这些常量。而属于类的静态变量则只需要一份内存甚至无需存储变量的值。所以如果对象变量在每个对象中都是一致的,那么就可以考虑转为静态常量。转成静态常量也能方便地用类名直接进行访问,省去创建多余的中间对象。

Java编译器对于常量会做优化,在引用它们的地方会将它们的值直接嵌入,这样就不需要内存来长期存储这些值,更不要从内存地址中寻找,所以效率要高很多。

还是做一个简单的例子:

[codesyntax lang=”java” lines=”normal”]

package com.iderzheng.statickeyword;

public class StaticFinalFields {

    static final int CONSTANT_INT = 7;
    static final String CONSTANT_STRING = "iderzheng.com";
    static final int[] CONSTANT_ARRAY = { 7, 21, 31 };

    final String name;
    final int constantInt = 21;
    final boolean constantBoolean;

    {
        constantBoolean = true;
    }

    public StaticFinalFields(String name) {
        this.name = name;
    }

    public static void main(String[] args) {
        StaticFinalFields finalFields = new StaticFinalFields("Ider");
        System.out.println(finalFields.name);
        System.out.println(finalFields.constantInt);
        System.out.println(finalFields.constantBoolean);

        System.out.println(CONSTANT_INT);
        System.out.println(CONSTANT_STRING);
        System.out.println(CONSTANT_ARRAY);
    }
}

[/codesyntax]

对于上边的代码,通过javac进行编译后得到StaticFinalFields.class,再讲其通过JD-UI打开,会看到编译后代码的
static-final-inline

[codesyntax lang=”java” lines=”normal”]

package com.iderzheng.statickeyword;

import java.io.PrintStream;

public class StaticFinalFields
{
    static final int CONSTANT_INT = 7;
    static final String CONSTANT_STRING = "iderzheng.com";
    static final int[] CONSTANT_ARRAY = { 7, 21, 31 };
    final String name;
    final int constantInt = 21;

    final boolean constantBoolean = true;

    public StaticFinalFields(String paramString)
    {
        this.name = paramString;
    }

    public static void main(String[] paramArrayOfString) {
        StaticFinalFields localStaticFinalFields = new StaticFinalFields("Ider");
        System.out.println(localStaticFinalFields.name);
        localStaticFinalFields.getClass(); System.out.println(21);
        System.out.println(localStaticFinalFields.constantBoolean);

        System.out.println(7);
        System.out.println("iderzheng.com");
        System.out.println(CONSTANT_ARRAY);
    }
}

[/codesyntax]

从编译后的代码可以看出对于原始类型的变量,在用final进行修饰并内嵌初始化后,使用这些变量的地方就直接用这些值进行了替换。虽然也有非static修饰的对象常量被智能优化后直接内嵌,但是为了代码的维护性,依然应该显示地申明成static。

至于对象变量,它们并非真正意义上的常量,对象的创建后的地址也总会不同,而且对象的内容依然可以被修改,所以这些变量加上static final也无法用其值在使用的地方进行替换。

另外还看到通过block进行初始化的对象变量虽然也是常量,但是因为放入了block,编译器觉得它的初始化比较复杂,所以就没有将其引用直接替换。

直接内嵌常量的可以提高运行的效率,但是也有一些弊端:比如项目A中使用了项目B中的静态常量,成功编译后的A会直接使用那些常量;要是B的常量值被人修改了之后只编译了B而没有重新编译A,那A就不会得到新的值。好在现代的编译器都很智能,可以发现这些依赖关系并正确编译。
Read More →

2016-02-23
23 February
On February 23, 2016
In Design Patterns(设计模式), Knowledge Base(心得笔库), Language Tips(语言初试), Special Tricks(奇技妙招)

Java的final关键字

在《Java关键字分类解析》里介绍了所有Java关键字和保留字的基本用途,到《Java修饰符及其作用对象》又介绍了所有Java修饰符的应用。通过修饰符的表格看到final是唯一一个可以在类(Class)、方法Method、变量(Variable)上都能应用的,但前文也提到final在这些作用对象上的效果是不太一样的,本文就详细展开介绍一下final的具体效果。

final class

当一个类被定义成final class,表示该类的不能被其他类继承,即不能用在extends之后。否则在编译期间就会得到错误。
[codesyntax lang=”java” lines=”normal”]

package com.iderzheng.finalkeyword;

public final class FinalClass {
}

// Error: cannot inherit from final
class PackageClass extends FinalClass {
}

[/codesyntax]
Java支持把class定义成final,似乎违背了面向对象编程的基本原则,但在另一方面,封闭的类也保证了该类的所有方法都是固定不变的,不会有子类的覆盖方法需要去动态加载。这给编译器做优化时提供了更多的可能,最好的例子是String,它就是final类,Java编译器就可以把字符串常量(那些包含在双引号中的内容)直接变成String对象,同时对运算符+的操作直接优化成新的常量,因为final修饰保证了不会有子类对拼接操作返回不同的值。

对于所有不同的类定义—顶层类(全局或包可见)、嵌套类(内部类或静态嵌套类)都可以用final来修饰。但是一般来说final多用来修饰在被定义成全局(public)的类上,因为对于非全局类,访问修饰符已经将他们限制了它们的也可见性,想要继承这些类已经很困难,就不用再加一层final限制。

另外要提到的是匿名类(Anonymous Class)虽然说同样不能被继承,但它们并没有被编译器限制成final。
[codesyntax lang=”java” lines=”normal”]

import java.lang.reflect.Modifier;

public class Main {

    public static void main(String[] args) {
        Runnable anonymous = new Runnable() {
            @Override
            public void run() {
            }
        };

        System.out.println(Modifier.isFinal(anonymous.getClass().getModifiers()));
    }
}

// Output:
// false

[/codesyntax]
Read More →

2015-10-31
31 October
On October 31, 2015
In Design Patterns(设计模式), Knowledge Base(心得笔库), Language Tips(语言初试)

Java修饰符及其作用对象

在《Java关键字分类解析》一文里已经对Java的所有关键字进行了分类归组,并对部分关键字做了一些简单的介绍分析。不过对于修饰符这部分值得更详细的探讨,所以本文就来讲述下这些修饰符在Java中的功能及应用。

Java的关键字里总共有11种修饰符,但实际上还有一种访问修饰符(Access Modifier),那就是“没有修饰”的修饰符,也就是不加任何修饰符在作用对象上。这种修饰符没有固定名称,以下都是出现过的的名字:“默认(default)”、“无修饰(No Modifier)”、“包私有(Package-Private)”、“包可见(Package)”。本文将以(package)来表示该隐形的修饰符,然后针对一共12种修饰符来作阐述。

对于所有Java的概念,可以应用修饰符的对象有三种:类(Class)、方法(Method)、变量(Variable)。进一步考虑,Java可以在类的定义里定义另一个类,所以对于类定义的位置又分出:顶层类(Top-level Class),即直接定义在文件包下的类;和嵌套类(Nested Class)。对于变量,根据其是定义在类中还是方法中,可分别定义为:类字段(Class Field)和局部变量(Local Variable)。

再进一步分类的话,嵌套类还可以分成静态嵌套类(Static Nested Class)和内部类(Inner Class),不过这只是static修饰符起的效果,所以不进一步区分。同样的对于方法也不区分静态方法和对象方法,对字段也不分静态字段(Static Field)和实例变量(Instance Variable)。对于局部变量,其实还可以细分出方法参数(Method Parameter),但它的效果基本跟方法内直接定义的变量效果一致,所以不做区分。这里也不对接口(interface)进行讨论,因为它基本相当于是完全抽象类(abstract class)。

这样就得到了5种基本的修饰符作用对象,但不是所有的修饰符都可以作用在每一种对象上,所以把12种修饰符在Java中实际可作用的对象总结成下表:

Modifier Class Method Variable
Top-Level Class Nested Class Class Field Local Variable
private NO YES YES YES NO
protected NO YES YES YES NO
public YES YES YES YES NO
(package) YES YES YES YES –
abstract YES YES YES NO NO
final YES YES YES YES YES
native NO NO YES NO NO
static NO YES YES YES NO
strictfp YES YES YES NO NO
synchronized NO NO YES NO NO
transient NO NO NO YES NO
volatile NO NO NO YES NO

Read More →

2015-06-30
30 June
On June 30, 2015
In Data Structures(数据结构), Design Patterns(设计模式), Knowledge Base(心得笔库), Mobile Development(移动开发)

Android自定义View中MeasureSpec浅析

Android的API为开发者提供了很多好用的widget和control,但在开发中依然会需要自定义一些额外的控件来满足特定的需求。当自定义的视图比较复杂时,就会跟onMeasure(int, int)、onLayout(boolean, int, int, int, int)、onDraw(android.graphics.Canvas)这些方法打交道。要在新创建自定义视图类里正确重载实现这些方法,就需要对这些方法的作用,参数意义有所了解。

本文就来对onMeasure(int, int)方法涉及到的MeasureSpec来做个简单介绍,讲讲它的值的含义,每个状态量都是在什么情况下形成,又该如何使用这些值。
Read More →

2015-04-30
30 April
On April 30, 2015
In Design Patterns(设计模式), Knowledge Base(心得笔库), Mobile Development(移动开发), Programming Life(程序人生)

黑科技尝鲜从ListView迁移到RecyclerView

在《RecyclerView体验简介》里已经介绍了RecyclerView目前的可用情况,也提供了一些文章的链接来了解这个新的Android视图的使用方法,API的调用方式。但由于RecyclerView的Adapter需要开发者重新实现,这相当于一次完整的重构了。本文就来介绍一下我在尝鲜RecyclerView所使用到的非常规手段,如果您也只是想尝试一下把原有的程序转到RecyclerView下看看效果,也许本文会有一些帮助。

ViewHolder-挂羊头卖狗肉

之前已经强调RecyclerView强制要求使用ViewHolder模式。但即使是强制,也可以采用“上有政策,下有对策”,敷衍地实现一个子类就好:

[codesyntax lang=”java” lines=”normal”]

public class DummyViewHolder extends RecyclerView.ViewHolder {
    public DummyViewHolder(View itemView) {
        super(itemView);
    }
}

[/codesyntax]

至于缓存子项视图的内部视图到变量上,就先免了。

对于比较复杂的ListView子视图应该都会遵循使用ViewHolder,只是没有具体继承与某个基类。所以只要将那些自定义的ViewHolder显示继承RecyclerView.ViewHolder,再在构造函数里调用一下super(view);就好。
Read More →

2015-04-16
16 April
On April 16, 2015
In Design Patterns(设计模式), Front Interface(界面构想), Knowledge Base(心得笔库), Mobile Development(移动开发)

RecyclerView体验简介

前些日子,组里为了在目前的Android程序里实现基于ListView子项的动画效果,希望将最新的RecyclerView引入到程序中,于是我便花了一些时间研究了一下RecyclerView的基本情况。本文算是对这些日子里了解的内容做一些汇总。

在网上关于RecyclerView的基本使用方式已经有了比较详细介绍,而且其设计结构也类似于ListView,所以本文将不重点介绍如何使用,在文末的引用中都可以相关内容。这里主要是介绍RecyclerView的基本功能、设计理念,以及系统提供API的情况。

什么是RecyclerView

RecyclerView是在Android L(也就是后来的Lollipop)中新加入的一种ViewGroup。但因为它使以support-v7库的形式加入到Android系统中,所以不仅仅是Lollipop版本以后的Android系统可以使用,只要系开发项目中引入这个库就在任意API级别中使用。不过查阅其文档,可以感受到RecyclerView是如此的强烈的“还在完善中”的感觉,因为对它的介绍只有短短的一句话:

A flexible view for providing a limited window into a large data set.

单看这句话,其实已经被经常使用的ListView和GridView基本也是满足这句描述的。而且从单呈现效果来看RecyclerView和ListView、GridView并没有大多的差别。

不过它的“flexible”并不单单指它可以在ListView和GridView之间随意互相切换,更在于它可以创造出更多的复杂的可滚动的视图,比如水平方向的ListView,或者是Web上很流行的瀑布流式布局(Masonry)。只是大部分布局系统都没有提供,必须由开发者自己实现。

所以RecyclerView的“flexible”:什么都可以做,但什么都要自己做。
Read More →

2015-01-30
30 January
On January 30, 2015
In Algorithm Analysis(算法分析), Data Structures(数据结构), Design Patterns(设计模式), Knowledge Base(心得笔库)

树结构遍历的实现汇总

在计算机数据结构中,树(Tree)结构是基础的结构之一,对于其定义、实现以及相关算法在一般的算法与数据结构书中都有详细介绍和分析。不过本文还是想要罗列一下树结构基本的遍历算法,同时简单随机介绍各种遍历算法的使用情境。

本文中将会实现树遍历主要两种方式:深度优先和广度优先。对于深度优先也会包括其三种不同方式:前序遍历、中序遍历、后续遍历。同时对于深度优先的三种方式还会包括最简单直观的递归实现,和相对复杂的迭代实现。

为方便起见文中的算法将基于二叉树(Binary Tree)结构,其树节点的结构也简单定义如下:

[codesyntax lang=”cpp” lines=”normal”]

using namespace std;
class Node {
public:
    Node *left;
    Node *right;
    int value;
};

[/codesyntax]

深度优先遍历

深度优先遍历隐藏着回溯法(Backtracking)应用,因此利用递归自动创建堆栈(stack)的性质,就可以非常好的实现这些遍历算法。虽然递归可以通过创建自定义的栈对象来变成迭代,但对于进栈出栈的控制,三种遍历方式有着不同的条件,因而实现反而变得复杂。

递归实现

对于节点的访问操作,定义了如下的方法,其实只是简单的输出节点的值再以空格分隔。对于空节点也将预留输出特别的符号来指示。

[codesyntax lang=”cpp” lines=”normal”]

#define NULL_NODE "#"

void operate(Node *node) {
    if (node == NULL) {
//        cout << (NULL_NODE" ");
    } else {
        cout << node->value << " ";
    }
}

[/codesyntax]

三种深度优先遍历的算法实现如下

[codesyntax lang=”cpp” lines=”normal”]

void preorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    // operate node before any children
    operate(node);
    preorder(node->left);
    preorder(node->right);
}

void inorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    inorder(node->left);
    // operate node in the middle of children
    operate(node);
    inorder(node->right);
}

void postorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    postorder(node->left);
    postorder(node->right);
    // operate node after all child
    operate(node);
}

[/codesyntax]
Read More →

Posts pagination

1 2 Next
Facebook
Twitter
LinkedIn
RSS
ZhiHu

Recent Posts

  • 三年居家工作感受
  • Pixel Watch智能手表和Pixel 5, 6 Pro 及 7 Pro手机
  • 我拥有过的无线耳机
  • 毕业工作一个月,我差点被开除
  • 我拥有过的移动硬盘
  • ProtoBuf 2.0 method count optimization for android development
  • 面过100场行为面试后

Categories

  • Algorithm Analysis(算法分析)
  • Article Collection(聚宝收藏)
  • Data Structures(数据结构)
  • Design Patterns(设计模式)
  • English Posts(英文写作)
  • Front Interface(界面构想)
  • IT Products(数码产品)
  • Knowledge Base(心得笔库)
  • Language Tips(语言初试)
  • Mathematical Theory(数学理论)
  • Mobile Development(移动开发)
  • Programming Life(程序人生)
  • Reading Notes(阅而后知)
  • Software Engineering(软件工程)
  • Special Tricks(奇技妙招)
  • Tangential Speech(漫话杂谈)

Tags

Aero Android API Bash Binary Search Bitwise Operation Book C/C++ Career Chrome Conference CSS Debug Device DOM Extension Framework Game Gradle Hearthstone HTML Initialization Intellij Interview iOS Java JavaScript jQuery Keyword Language Issues Mac Microsoft Mobile Modifier Objective-C PHP Principle Reference Regular Expression Static String Tools Tutorial UI XML

Blogroll

  • Ahmed's Blog
  • Gert Lombard's Blog
  • Gordon Luk
  • Jack & Allison
  • 开发部落

Archives

Designed using Chromatic. Powered by WordPress.