DevSONG | 欢迎来到DevSONG个人博客

熟悉安卓开发的朋友应该对OKHttp这个网络框架不陌生，使用OKHttp框架可以轻松地进行网络操作。但是奇怪的一点是OKHttp并未提供Session持久化选项，这就导致如果我们需要用session记录一些东西，如登录状态时，就不行了。所以我们需要手动编写session持久化的代码。本篇笔记围绕的就是Session的持久化操作，网络上也有很多相关的博文，我整理了一些优秀且实测可用的内容。在文章末尾，你可根据需要下载我写的简单Demo，可以参考操作。 HttpSession 持久化主要涉及三个类：（1）PersistentCookieStore ，这个类主要是将Cookie缓存在内存中以及从内存中将持久化文件重新转换为Cookie。代码如下： package org.devsong.okhttpsessionpersistent.httputil; import android.content.Context; import android.content.SharedPreferences; import android.text.TextUtils; import android.util.Log; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Locale; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import okhttp3.Cookie; import okhttp3.HttpUrl; /** * Created by SONG on 2018/3/9. */ public class PersistentCookieStore { private static final String LOG_TAG = "PersistentCookieStore"; private static final String COOKIE_PREFS = "Cookies_Prefs"; private final Map<String, ConcurrentHashMap<String, Cookie>> cookies; private final SharedPreferences cookiePrefs; public PersistentCookieStore(Context context) { cookiePrefs = context.getSharedPreferences(COOKIE_PREFS, 0); cookies = new HashMap<>(); //将持久化的cookies缓存到内存中即map cookies Map<String, > prefsMap = cookiePrefs.getAll(); for (Map.Entry<String, > entry : prefsMap.entrySet()) { String[] cookieNames = TextUtils.split((String) entry.getValue(), ","); for (String name : cookieNames) { String encodedCookie = cookiePrefs.getString(name, null); if (encodedCookie != null) { Cookie decodedCookie = decodeCookie(encodedCookie); if (decodedCookie != null) { if (!cookies.containsKey(entry.getKey())) { cookies.put(entry.getKey(), new ConcurrentHashMap<String, Cookie>()); } cookies.get(entry.getKey()).put(name, decodedCookie); } } } } } protected String getCookieToken(Cookie cookie) { return cookie.name() + "@" + cookie.domain(); } public void add(HttpUrl url, Cookie cookie) { String name = getCookieToken(cookie); //将cookies缓存到内存中如果缓存过期就重置此cookie if (!cookie.persistent()) { if (!cookies.containsKey(url.host())) { cookies.put(url.host(), new ConcurrentHashMap<String, Cookie>()); } cookies.get(url.host()).put(name, cookie); } else { if (cookies.containsKey(url.host())) { cookies.get(url.host()).remove(name); } } //将cookies持久化到本地 SharedPreferences.Editor prefsWriter = cookiePrefs.edit(); prefsWriter.putString(url.host(), TextUtils.join(",", cookies.get(url.host()).keySet())); prefsWriter.putString(name, encodeCookie(new SerializableOkHttpCookies(cookie))); prefsWriter.apply(); } public List<Cookie> get(HttpUrl url) { ArrayList<Cookie> ret = new ArrayList<>(); if (cookies.containsKey(url.host())) ret.addAll(cookies.get(url.host()).values()); return ret; } public boolean removeAll() { SharedPreferences.Editor prefsWriter = cookiePrefs.edit(); prefsWriter.clear(); prefsWriter.apply(); cookies.clear(); return true; } public boolean remove(HttpUrl url, Cookie cookie) { String name = getCookieToken(cookie); if (cookies.containsKey(url.host()) && cookies.get(url.host()).containsKey(name)) { cookies.get(url.host()).remove(name); SharedPreferences.Editor prefsWriter = cookiePrefs.edit(); if (cookiePrefs.contains(name)) { prefsWriter.remove(name); } prefsWriter.putString(url.host(), TextUtils.join(",", cookies.get(url.host()).keySet())); prefsWriter.apply(); return true; } else { return false; } } public List<Cookie> getCookies() { ArrayList<Cookie> ret = new ArrayList<>(); for (String key : cookies.keySet()) ret.addAll(cookies.get(key).values()); return ret; } /** * cookies 序列化成 string * * @param cookie 要序列化的cookie * @return 序列化之后的string */ protected String encodeCookie(SerializableOkHttpCookies cookie) { if (cookie == null) return null; ByteArrayOutputStream os = new ByteArrayOutputStream(); try { ObjectOutputStream outputStream = new ObjectOutputStream(os); outputStream.writeObject(cookie); } catch (IOException e) { Log.d(LOG_TAG, "IOException in encodeCookie", e); return null; } return byteArrayToHexString(os.toByteArray()); } /** * 将字符串反序列化成cookies * * @param cookieString cookies string * @return cookie object */ protected Cookie decodeCookie(String cookieString) { byte[] bytes = hexStringToByteArray(cookieString); ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(bytes); Cookie cookie = null; try { ObjectInputStream objectInputStream = new ObjectInputStream(byteArrayInputStream); cookie = ((SerializableOkHttpCookies) objectInputStream.readObject()).getCookies(); } catch (IOException e) { Log.d(LOG_TAG, "IOException in decodeCookie", e); } catch (ClassNotFoundException e) { Log.d(LOG_TAG, "ClassNotFoundException in decodeCookie", e); } return cookie; } /** * 二进制数组转十六进制字符串 * * @param bytes byte array to be converted * @return string containing hex values */ protected String byteArrayToHexString(byte[] bytes) { StringBuilder sb = new StringBuilder(bytes.length * 2); for (byte element : bytes) { int v = element & 0xff; if (v < 16) { sb.append('0'); } sb.append(Integer.toHexString(v)); } return sb.toString().toUpperCase(Locale.US); } /** * 十六进制字符串转二进制数组 * * @param hexString string of hex-encoded values * @return decoded byte array */ protected byte[] hexStringToByteArray(String hexString) { int len = hexString.length(); byte[] data = new byte[len / 2]; for (int i = 0; i < len; i += 2) { data[i / 2] = (byte) ((Character.digit(hexString.charAt(i), 16) << 4) + Character.digit(hexString.charAt(i + 1), 16)); } return data; } } 另一个重要的类是SerializableOkHttpCookies，也就是序列化Cookie，以便进行网络传输。代码如下： package org.devsong.okhttpsessionpersistent.httputil; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import okhttp3.Cookie; /** * Created by SONG on 2018/3/9. */ public class SerializableOkHttpCookies implements Serializable { private transient final Cookie cookies; private transient Cookie clientCookies; public SerializableOkHttpCookies(Cookie cookies) { this.cookies = cookies; } public Cookie getCookies() { Cookie bestCookies = cookies; if (clientCookies != null) { bestCookies = clientCookies; } return bestCookies; } private void writeObject(ObjectOutputStream out) throws IOException { out.writeObject(cookies.name()); out.writeObject(cookies.value()); out.writeLong(cookies.expiresAt()); out.writeObject(cookies.domain()); out.writeObject(cookies.path()); out.writeBoolean(cookies.secure()); out.writeBoolean(cookies.httpOnly()); out.writeBoolean(cookies.hostOnly()); out.writeBoolean(cookies.persistent()); } private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { String name = (String) in.readObject(); String value = (String) in.readObject(); long expiresAt = in.readLong(); String domain = (String) in.readObject(); String path = (String) in.readObject(); boolean secure = in.readBoolean(); boolean httpOnly = in.readBoolean(); boolean hostOnly = in.readBoolean(); boolean persistent = in.readBoolean(); Cookie.Builder builder = new Cookie.Builder(); builder = builder.name(name); builder = builder.value(value); builder = builder.expiresAt(expiresAt); builder = hostOnly builder.hostOnlyDomain(domain) : builder.domain(domain); builder = builder.path(path); builder = secure builder.secure() : builder; builder = httpOnly builder.httpOnly() : builder; clientCookies = builder.build(); } } 最后是CookiesManager ，这个作为最顶层的管理文件，从response中读取并存储信息到Cookie，从存储的Cookie文件中加载信息放到Request传输至服务器。代码如下： /** * Cookie 管理类，自动管理Cookie */ public class CookiesManager implements CookieJar { private final PersistentCookieStore cookieStore = new PersistentCookieStore(getApplicationContext()); @Override public void saveFromResponse(@NonNull HttpUrl url, @NonNull List<Cookie> cookies) { if (cookies.size() > 0) { for (Cookie item : cookies) { cookieStore.add(url, item); } } } @Override public List<Cookie> loadForRequest(@NonNull HttpUrl url) { return cookieStore.get(url); } } Demo测试，服务器部分有了以上三个类，我们就能进行下一步的工作了，首先，得先写一个服务端。这里我只是简单写了一个servlet，当收到请求时，以文本的形式回复客户端。servlet如下： package org.devsong.servlet; import java.io.IOException; import java.io.PrintWriter; import javax.servlet.ServletException; import javax.servlet.annotation.WebServlet; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; @WebServlet(urlPatterns={"/"}, name="SessionIdServlet") public class SessionServlet extends HttpServlet { private static final long serialVersionUID = 1L; @Override protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException { doPost(req, resp); } @Override protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException { String sessionId = req.getSession().getId(); System.out.println("当前SessionId:" + sessionId); resp.setContentType("text/plain; charseet=utf-8"); PrintWriter writer = resp.getWriter(); writer.print("当前SessionId:" + sessionId); writer.flush(); writer.close(); } } 服务端其他文件就不贴出来，如果您需要，可以到文章末尾选择下载。安卓客户端Demo 服务器端构建完成，下面就是客户端了，客户端也很简单，就是发送请求，然后将接收到的信息加载到一个TextView。由于网络操作是一个耗时的操作，直接在ui线程中操作显然是不合理的，所以需要单独创建一个线程：HttpThread，代码如下： HttpThread.java package org.devsong.okhttpsessionpersistent.httputil; import android.util.Log; import java.io.IOException; import okhttp3.Call; import okhttp3.Callback; import okhttp3.OkHttpClient; import okhttp3.Request; import okhttp3.Response; public class HttpThread extends Thread { private static OkHttpClient okHttpClient; private IDataProcess dataProcess; private String url; public static void initHttpThread(OkHttpClient okHttpClient) { HttpThread.okHttpClient = okHttpClient; } public HttpThread(String url, IDataProcess dataProcess) { this.url = url; this.dataProcess = dataProcess; } @Override public void run() { if (okHttpClient == null) { Log.e("HttpThread", "error: HTTPThread 尚未初始化"); return; } //如果需要传数据，那么只需要新建一个RequestBody，然后build进去就行了 Request.Builder builder = new Request.Builder(); Request request = builder.url(url).build(); Call call = okHttpClient.newCall(request); call.enqueue(new Callback() { @Override public void onFailure(Call call, IOException e) { e.printStackTrace(); dataProcess.process("error: 数据请求失败！描述：" + e.getMessage()); } @Override public void onResponse(Call call, Response response) throws IOException { dataProcess.process(response.body().string()); } }); } } 为方便查看，这里也贴出MainActivity.java package org.devsong.okhttpsessionpersistent; import android.support.annotation.NonNull; import android.support.v7.app.AppCompatActivity; import android.os.Bundle; import android.text.method.ScrollingMovementMethod; import android.view.View; import android.widget.EditText; import android.widget.TextView; import android.widget.Toast; import org.devsong.okhttpsessionpersistent.httputil.HttpThread; import org.devsong.okhttpsessionpersistent.httputil.IDataProcess; import org.devsong.okhttpsessionpersistent.httputil.PersistentCookieStore; import org.devsong.okhttpsessionpersistent.utils.MyTools; import java.util.List; import java.util.concurrent.TimeUnit; import okhttp3.Cookie; import okhttp3.CookieJar; import okhttp3.HttpUrl; import okhttp3.OkHttpClient; public class MainActivity extends AppCompatActivity { private TextView tv; private String ip = "172.31.241.22:8080"; private EditText et_ip; @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_main); tv = findViewById(R.id.tv_res_disp); tv.setMovementMethod(new ScrollingMovementMethod()); et_ip = findViewById(R.id.ip); et_ip.setText(ip); //新建OKHttpClient对象 OkHttpClient client = new OkHttpClient.Builder().connectTimeout(10, TimeUnit.SECONDS).cookieJar(new CookiesManager()).build(); //初始化HttpThread HttpThread.initHttpThread(client); } /** * Cookie 管理类，自动管理Cookie */ public class CookiesManager implements CookieJar { private final PersistentCookieStore cookieStore = new PersistentCookieStore(getApplicationContext()); @Override public void saveFromResponse(@NonNull HttpUrl url, @NonNull List<Cookie> cookies) { if (cookies.size() > 0) { for (Cookie item : cookies) { cookieStore.add(url, item); } } } @Override public List<Cookie> loadForRequest(@NonNull HttpUrl url) { return cookieStore.get(url); } } public void click(View view){ switch (view.getId()){ case R.id.btn_send: doSend(); break; } } /** * 发送一次请求，将服务器返回结果显示在文本区 */ public void doSend(){ ip = et_ip.getText().toString(); if("".equals(ip.trim())){ Toast.makeText(MainActivity.this, "请输入IP或网址", Toast.LENGTH_SHORT).show(); return; } //访问本机端口8080 //安卓虚拟机访问电脑不能用Localhost:8080, 要将localhost替换为本机IP new HttpThread("http://" + ip + "/", new IDataProcess() { @Override public void process(final String data) { runOnUiThread(new Runnable() { @Override public void run() { tv.setText(String.format("%s%s\n\n%s", MyTools.getDateStr(System.currentTimeMillis(), "yyyy/MM/dd HH:mm:ss ->"), data, tv.getText().toString())); } }); } }).start(); } } 最终测试效果最后效果如下，可以看到每次请求服务器返回的 SessionId 是一致的：附件下载：服务器端工程（Eclipse）：点此下载客户端工程（AndroidStudio）：点此下载客户端APK文件：点此下载

上一篇文章说到了二叉树，简单实现了一下二叉树的基本操作，用常规的递归思想测试了二叉树的遍历。本篇文章我们来探讨一下二叉树的非递归遍历。【提示：请忽略文章中 “结点”“节点”的混用，懒得改了，输入法承担一半责任】二叉树的非递归遍历除了前、中、后序遍历外，还有一个层序遍历。前三者常用堆栈辅助完成遍历过程，层序遍历则借助队列完成。本篇文章只探讨前中后三种遍历算法的非递归实现。在此之前，我们需要准备一个可用的“堆栈”。堆栈不用多解释了，实现方式很多，每个人的写法和实现思路或许都会有一些不一样，但是只要能达到设计目 ”后进先出“ 就行了。此处我也简单实现了一下，简单测试完毕，不排除有潜在问题，仅供参考： stack.h #ifndef STACK_H #define STACK_H #include "misc.h" #include <stdio.h> #include <stdlib.h> stack_t * initStack(); void traverseStackReverse(stack_t * stack, void (*callBack)()); void traverseStack(stack_t * stack, void (*callBack)()); int isStackEmpty(stack_t *stack); stackDataType popData(stack_t *stack); int pushData(stack_t *stack, stackDataType data); stackDataType getTopData(stack_t *stack); void destroyStack(stack_t **stack); #endif // STACK_H 由于此次测试需要用到上一篇中二叉树相关的东西，所以增加了一个额外的文件：misc.h #ifndef MISC_H #define MISC_H typedef int dataType; //数据类型，简单测试，将 DataType 设置为 int //节点类型 typedef struct nodeData{ struct nodeData *leftChild; struct nodeData *rightChild; dataType data; }node_t; //堆栈数据类型 typedef node_t stackDataType; //堆栈数据结点结构 typedef struct stackNode{ struct stackNode *pre; struct stackNode *next; stackDataType data; }stackNode_t; //堆栈结点类型 //堆栈结构 typedef struct myStack{ int size; stackNode_t *node; stackNode_t * stackPointer; }stack_t; #endif // MISC_H stack.c #include "stack.h" /** *初始化堆栈 */ stack_t * initStack(){ stack_t *temp = (stack_t *)malloc(sizeof(stack_t)); if(temp == NULL){ printf("\nERROR : memory initial error!\n"); return NULL; } temp->size = 0; temp->stackPointer = NULL; temp->node = NULL; return temp; } /** *入栈操作 */ int pushData(stack_t *stack, stackDataType data){ if(stack == NULL){ printf("\nERROR: stack is NULL\n"); return -1; } if(stack->size == 0){ stack->node = (stackNode_t *)malloc(sizeof(stackNode_t)); if(stack->node == NULL){ printf("\nERROR : push data failed, memory initial error!\n"); return -1; } stack->node->next = NULL; stack->node->pre = NULL; stack->node->data = data; stack->size++; stack->stackPointer = stack->node; return 0; } stack->stackPointer->next = (stackNode_t *)malloc(sizeof(stackNode_t)); if(stack->stackPointer->next == NULL){ printf("\nERROR : push data failed, memory initial error!\n"); return -1; } stack->size++; stack->stackPointer->next->data = data; stack->stackPointer->next->pre = stack->stackPointer; stack->stackPointer->next->next = NULL; stack->stackPointer = stack->stackPointer->next; return 0; } /** *弹出栈顶元素 */ stackDataType popData(stack_t *stack){ if(stack == NULL){ printf("\nERROR: stack is NULL!\n"); return; } if(stack->size <= 0){ printf("\nERROR: stack is empty!\n"); return; } stackNode_t *temp = stack->stackPointer; stack->stackPointer = stack->stackPointer->pre; if(stack->stackPointer != NULL){ stack->stackPointer->next = NULL; } stack->size--; sizeof(temp->data); return temp->data; free(temp); } /** *获取栈顶元素 */ stackDataType getTopData(stack_t *stack){ if(stack == NULL){ printf("\nERROR: stack is NULL!\n"); return; } if(stack->size <= 0){ printf("\nERROR: stack is empty!\n"); return; } return stack->stackPointer->data; } /** *堆栈是否为空 *@return int ：空 ----- 1 ：非空 ----- 0 */ int isStackEmpty(stack_t *stack){ if(stack == NULL){ printf("\nERROR:stack is NULL\n"); return -1; } return stack->size == 0 1 : 0; } /** *堆栈元素遍历 */ void traverseStack(stack_t * stack, void (*callBack)()){ if(stack == NULL){ printf("\nERROR:stack is NULL\n"); return; } if(stack->size == 0){ printf("\nWARNING : stack is empty\n"); return; } stackNode_t *temp = stack->stackPointer; while(temp != NULL){ callBack(temp->data); temp = temp->pre; } } /** *堆栈元素遍历（反序） */ void traverseStackReverse(stack_t * stack, void (*callBack)()){ if(stack == NULL){ printf("\nERROR:stack is NULL\n"); return; } if(stack->size == 0){ printf("\nWARNING : stack is empty\n"); return; } stackNode_t *temp = stack->node; while(temp != NULL){ callBack(temp->data); temp = temp->next; } } /** *销毁堆栈 */ void destroyStack(stack_t **stack){ if(*stack == NULL){ return; } if((*stack)->size != 0){ stackNode_t *temp = (*stack)->node; stackNode_t *temp1 = temp; while(temp != NULL){ temp1 = temp; temp = temp->next; free(temp1); } } free(*stack); *stack = NULL; } 测试：main函数 int main(){ node_t *p; //初始化 node_t *tree = initBiTree(); tree->data = 10; p = insertRightChildByData(tree, 20); p = insertLeftChildByData(p, 50); insertRightChildByData(p, 60); insertLeftChildByData(p, 70); p = insertLeftChildByData(tree, 30); insertLeftChildByData(p, 40); /*构建了如下结构的二叉树 10 / \ 30 20 / / 40 50 / \ 70 60 */ //遍历输出 printf("============= 二叉树遍历（递归方式） ===========\n"); puts("former: "); formerTraversal(tree, visitNodeAction); puts("\nin: "); inTraversal(tree, visitNodeAction); puts("\nafter: "); afterTraversal(tree, visitNodeAction); /*********** 堆栈测试 ***********/ printf("\n\n============= 堆栈测试 ===========\n"); stackDataType data1 = {NULL, NULL, 1}; stackDataType data2 = {NULL, NULL, 2}; stackDataType data3 = {NULL, NULL, 3}; //构建堆栈 stack_t *stack = initStack(); pushData(stack, data1); pushData(stack, data2); pushData(stack, data3); //输出堆栈 printf("size: %d\n", stack->size); traverseStack(stack, visitStack); puts(""); traverseStackReverse(stack, visitStack); //获取栈顶元素 printf("\ntop data: %d\n", getTopData(stack).data); //弹出栈顶元素 printf("data: %d\n", popData(stack).data); printf("size: %d\n", stack->size); traverseStack(stack, visitStack); puts(""); traverseStackReverse(stack, visitStack); printf("\n\n============= 结合堆栈进行二叉树非递归遍历 ===========\n"); /******** 结合堆栈进行二叉树非递归遍历 *********/ puts("前序遍历（非递归）:"); preOrder(tree, visitNodeAction); puts("\n中序遍历（非递归）:"); inOrder(tree, visitNodeAction); puts("\n后序遍历（非递归）:"); postOrder(tree, visitNodeAction); //销毁二叉树 destroyBiTree(&tree); //销毁堆栈 destroyStack(&stack); return 0; } 以上只是部分代码，如果您觉得网页不便查看代码，可以下载完整源文件：点击此处下载前序（先序）遍历先序遍历比较简单，也容易理解，只要保证根节点在子节点之前访问即可。实现步骤：（1）初始化堆栈（2）将根节点入栈（3）当堆栈非空时，循环执行 a、b、c 三步： a、出站一个结点，访问该节点 b、若该节点的右孩子节点非空，则入栈该节点的右孩子节点 c、若该节点的左孩子节点非空，则入栈该节点的左孩子结点（4）结束 C语言实现： /** *前序（先序）遍历（非递归方式） *@param tree : 待遍历二叉树根节点 *@param callack : 回调函数 */ void preOrder(node_t *tree, void (*callback)()){ stack_t *stack = initStack(); node_t temp; pushData(stack, *tree); while(!isStackEmpty(stack)){ temp = popData(stack); callback(&temp); if(temp.rightChild != NULL){ pushData(stack, *temp.rightChild); } if(temp.leftChild != NULL){ pushData(stack, *temp.leftChild); } } destroyStack(&stack); } 中序遍历实现步骤：（1）初始化堆栈（2）当临时结点不为空或者堆栈不为空的情况下循环执行以下操作： a、若临时节点不为空将临时结点指向的当前节点入栈，并让当前节点指向其左孩子节点 b、若临时结点为空，则出栈一个元素，访问该元素，之后让当前节点指向出栈元素的右孩子节点（3）结束遍历 C语言实现： /** *中序遍历（非递归方式） *@param tree : 待遍历二叉树根节点 *@param callack : 回调函数 */ void inOrder(node_t *tree, void (*callback)()){ stack_t *stack = initStack(); node_t *node = tree; node_t temp; while(node != NULL || !isStackEmpty(stack)){ if(node != NULL){ pushData(stack, *node); node = node->leftChild; }else{ temp = popData(stack); callback(&temp); node = temp.rightChild; } } destroyStack(&stack); } 后序遍历后序遍历相交于以上两者而言稍微复杂了一些，如果依旧用一个堆栈来操作的话过程很繁琐，期间还需要对一些节点作标记。注意到后序遍历对比前序遍历的反向过程非常类似，所以可以借助两个堆栈，堆栈一主要是做一个临时枢纽，每个节点都先入堆栈一，不作访问，堆栈2保留最终待访问的顺序，最后依次输出堆栈2进行访问即可。【或许我描述的不够准确，直接看代码即可】 C语言实现 /** *后序遍历（非递归方式） *@param tree : 待遍历二叉树根节点 *@param callack : 回调函数 */ void postOrder(node_t *tree, void (*callback)()){ //利用两个堆栈进行操作 stack_t *stack = initStack(); stack_t *stackParent = initStack(); node_t node; pushData(stack, *tree); //细心的你可能会发现此步骤和前序遍历有些相似 //实际上原理一致，仔细对比前序遍历和后序遍历的过程，它们很相似，##但又不仅仅是直接反序那么简单## while(!isStackEmpty(stack)){ node = popData(stack); pushData(stackParent, node); //此处必须左孩子结点在右孩子结点之前入栈， //因为后面出站再入栈（stackParent）又会有一个顺序的转变 //只有这样才能保证最终遍历结果是正确的（此处体现“但又不仅仅是直接反序那么简单”这句话） if(node.leftChild != NULL){ pushData(stack, *node.leftChild); } if(node.rightChild != NULL){ pushData(stack, *node.rightChild); } } while(!isStackEmpty(stackParent)){ node = popData(stackParent); callback(&node); } //销毁堆栈 destroyStack(&stack); destroyStack(&stackParent); } 测试结果： ============= 二叉树遍历（递归方式） =========== former: 10 30 40 20 50 70 60 in: 40 30 10 70 50 60 20 after: 40 30 70 60 50 20 10 ============= 堆栈测试 =========== size: 3 3 2 1 1 2 3 top data: 3 data: 3 size: 2 2 1 1 2 ============= 结合堆栈进行二叉树非递归遍历 =========== 前序遍历（非递归）: 10 30 40 20 50 70 60 中序遍历（非递归）: 40 30 10 70 50 60 20 后序遍历（非递归）: 40 30 70 60 50 20 10 总结以上简单实现了一下二叉树的非递归遍历，对比递归方式的实现，非递归还是显得有些麻烦。当然并不是说非递归实现不好，此处没有孰好孰坏的说法，只有合不合适的说法。递归固然方便理解和实现且速度快，但是其有一个不可忽视的缺点，那就是内存占用很大，如果一棵非常大的二叉树用常规的递归算法去遍历，每一个结点都是一次递归的调用，这样下来会占用非常大的内存资源，非递归实现对于内存的占用则好很多。所以不同情况下对于遍历算法的选择也是有很多考虑因素的。完整源文件在文章中已给出链接。此外查看系列文章只需点击文章下面的标签即可以上只是我个人的见解，能力有限，难免会出错，若您发现问题或者您有不同看法，欢迎留言。【原创内容，转载请注明出处】