二叉链表的 遍历 是 二叉链表 各种 操作的 基础，例如 ：创建 二叉树;求树的 长度；求树的 叶子节点数；求 节点的 层 数；求 树的 深度，宽度 等等。
总之 不掌握 遍历，就没有 掌握 二叉树；
二叉链表的 遍历 根据 根节点的访问顺序有：先（根节点）序，中（根节点）序，后（根节点）序， 和 层序；
算法思路 有两类：
1. 递归 算法，算法 清晰，容易 证明算法的正确性，但是 效率较低 和 受 系统 栈区 大小的限制，不能 递归太多层次
2.非 递归算法，算法 较复杂一些，但是效率高，，又 不受 栈区大小的限制
下面 讲解 这两种 算法：
1.递归算法 ，递归没什么 说的，比较 简单
//递归算法 先序void preOrderTraverse(Tree tree){if (tree != NULL){printf("%d\t",tree->data);preOrderTraverse(tree->leftChild);preOrderTraverse(tree->rightChild);}}//递归算法 中序void inOrderTraverse(Tree tree){if (tree != NULL){inOrderTraverse(tree->leftChild);printf("%d\t",tree->data);inOrderTraverse(tree->rightChild);}}//递归算法 后序void postOrderTraverse(Tree tree){if (tree != NULL){postOrderTraverse(tree->leftChild);postOrderTraverse(tree->rightChild);printf("%d\t",tree->data);}}
2.重点 讲解 非 递归算法，非递归 算法 需要 借助 栈 （先，中，后序） 或者 队列（层序） 来进行遍历。
2.1 非递归 先序 算法 总共 有 三种 方法：
下面 的两种算法 思路一致，都是 找左子树最左下角节点的同时访问节点，然后 将 节点的 右子树入栈。然后 重复寻找..
void preOrderTraverse1(Tree t){linkStack stack;stackInit(&stack);stackPush(&stack,t);while (!stackEmpty(stack)){while (stackGetTop(stack,&t) && t){printf("%d\t",t->data);stackPush(&stack,t->leftChild);}stackPop(&stack,&t);//NULL 出栈if (!stackEmpty(stack)){stackPop(&stack,&t);stackPush(&stack,t->rightChild);}}stackDestory(&stack);}void preOrderTraverse2(Tree tree){linkStack stack;stackInit(&stack);while (tree || !stackEmpty(stack)){if (tree){printf("%d\t",tree->data);stackPush(&stack,tree);tree = tree->leftChild;}else{stackPop(&stack,&tree);tree = tree->rightChild;}}stackDestory(&stack);}第三种 思路 较 前两种 清晰，更加 易懂
1.空树 不操作 2.将 树根入栈 3.访问 根 节点 ，将根节点出栈 4. 右子树不为空，将 右子树 入栈 5. 左子树 不为空，将左子树入栈 6.重复 3~ 5 步
比较 奇思妙想的是 先 将 右子树入栈 ，再将 左子树入栈，这样每次 都 先 访问 栈顶 的 左子树。
void preOrderTraverse3(Tree tree){if (tree != NULL){linkStack stack;stackInit(&stack);stackPush(&stack,tree);while (!stackEmpty(stack)){stackPop(&stack,&tree);printf("%d\t",tree->data);if (tree->rightChild != NULL){stackPush(&stack,tree->rightChild);}if (tree->leftChild != NULL){stackPush(&stack,tree->leftChild);}}}}
2.2 非递归 中序 有两种算法
算法 思路 同 先序 前两种 算法 的思路 一致，只是 先序是在 在 找 左子树的时候 访问，而中序 是 在 退栈的时候访问
//中序非递归void inOrderTraverse1(Tree tree){linkStack stack;stackInit(&stack);stackPush(&stack,tree);while (!stackEmpty(stack)){while (stackGetTop(stack,&tree) && tree) stackPush(&stack,tree->leftChild);stackPop(&stack,&tree);if (!stackEmpty(stack)){stackPop(&stack,&tree);printf("%d\t",tree->data);stackPush(&stack,tree->rightChild);}}stackDestory(&stack);}void inOrderTraverse2(Tree tree){linkStack stack;stackInit(&stack);while (tree || !stackEmpty(stack)){if (tree){stackPush(&stack,tree);tree = tree->leftChild;}else{stackPop(&stack,&tree);printf("%d\t",tree->data);tree = tree->rightChild;}}stackDestory(&stack);}
2.3 后序遍历 是 所有遍历中 最难的 一种我在网上 研究了 一番，发现了 一种 思路 比较 清晰的算法。
大致 的思路 是 ：只有 底下 三种情况的时候 访问 根节点。
1. 节点的 左子树 为空 并且 右 子树 为空 ，2. 刚访问过 右子树 3. 刚访问过左子树 并且 右子树 为空的 时候
这个算法 需要 记住 上一个 访问的 节点 和 利用 先 右子树 入栈 后 左子树 入栈，始终 先访问 左子树。
void postOrderTraverse1(Tree tree){if (tree != NULL){linkStack stack;stackInit(&stack);stackPush(&stack,tree);Tree pre = NULL;while (!stackEmpty(stack)){stackGetTop(stack,&tree);//左右子树都为空，或者 左子树刚访问过，并且 右子树为空，或者 刚访问过 右子树. 可以直接访问if ((tree->leftChild == NULL && tree->rightChild == NULL) || (pre != NULL && (tree->leftChild == pre || tree->rightChild == pre))){printf("%d\t",tree->data);stackPop(&stack,&tree);pre = tree;}else{if (tree->rightChild != NULL){stackPush(&stack,tree->rightChild);}if(tree->leftChild != NULL){stackPush(&stack,tree->leftChild);}}}}}2.4 层序 访问， 是 按 从 上 到下，从左 到右 的顺序 访问树。这时候 我们 需要 借助 队列。
这个算法 有一个特点，左子树 一定 在 右子树 前 访问，左子树的 孩子 一定 在 右子树的 孩子前 访问。
为你的快乐而快乐的是朋友，为你的难过而难过的才是你的知己。
