一、设计思想
二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的
顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算
法分，又分为递归遍历和非递归遍历。
递归算法：
1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将
左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至
结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。
2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为
根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，
打印右子，直至结束。
3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则
将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入
判断，打印右子。左右子判断完成后打印根结点。
非递归算法：
1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有
左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判
断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。
若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左
子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，
打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都
为空，且栈为空时，遍历结束。
2.中序遍历：首先建立一个栈，定义一个常量 flag（flag 为 0 或者 1），用 flag 记录结点
的左子是否去过，没有去过为 0，去过为 1，默认为 0.首先将指针指向根结点，将根结点入
栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点
的左子，直至左子为空，则指针返回，flag 置 1，出栈一个元素，作为当前结点，打印该结
点，然后判断 flag，flag 为 1 则将指针指向当前结点右子，将右子作为新的结点，结点入栈，
再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到
结束，使得当前结点右子为空，且栈空，遍历结束。
3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为 status，取值为 0，1，2.0
代表左右子都没有去过，1 代表去过左子，2，代表左右子都去过，默认为 0。第二个常量为
flag，取值为 0 或者 1，0 代表进左栈，1 代表进右栈。初始时指针指向根结点，判断根结点
是否有左子，有左子则，将根结点入左栈，status 置 0，flag 置 0，若没有左子则判断结点有
没有右子，有右子就把结点入右栈，status 置 0，flag 置 1，若左右子都没有，则打印该结点，
并将指针指向空，此时判断 flag，若 flag 为 0，则从左栈出栈一个元素作为当前结点，重新
判断；若 flag 为 1 则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若 status
为 1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status 置 1，flag 置 1，若
没有右子，则打印当前结点，并将指针置空，然后再次判断 flag。若当前结点 status 为 2，
且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，
按上述方法处理，直至遍历结束。
