- 中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树（左->根->右）
中序遍历的递归算法
思路：
- 遍历左子树
- 访问根节点
- 遍历右子树
代码如下：
//二叉树的中序遍历（递归）
void BinaryTreePrevOrder(BTNode* root){if (root){BinaryTreePrevOrder(root->lChild);putchar(root->data);BinaryTreePrevOrder(root->rChild);}
}
中序遍历的非递归算法
思路：
借助栈来实现
- 传入二叉树根节点
- 从该节点开始遍历左子树，将所有节点入栈，直至左子树为空
- 取出栈顶并打印，再将栈顶出栈
- 如果有右孩子，从步骤2开始；没有右孩子从步骤3开始（直至全部出栈）
图解非递归算法
代码如下：
//二叉树的中序遍历（非递归）
void BinaryTreeInOrderNonR(BTNode * root)
{BTNode * cur = root;Stack st;StackInit(&st, 100);while (cur || !StackIsEmpty(&st)){for (; cur; cur = cur->lChild) //将当前节点及左孩子们入栈{StackPush(&st, cur);}cur = StackTop(&st);//1、如果右孩子为空，for循环不进，直接取栈顶//2、如果右孩子不为空，那么这是一个没有左孩子的节点//第一种情况是左子树访问完毕，第二种情况是左子树为空，无论哪种，当前节点都要打印putchar(cur->data);StackPop(&st);cur = cur->rChild; //当右子树为空时，检查栈是否为空，如果栈也空了，循环跳出}StackDestory(&st);
}
栈函数实现如下：
typedef char BTDataType;
// 二叉链的结构体
typedef struct BinaryTreeNode {BTDataType data; // 当前节点值域struct BinTreeNode* lChild; // 指向当前节点左孩子 struct BinTreeNode* rChild;// 指向当前节点右孩子
}BTNode;typedef BTNode* StDataType;
// 栈的结构体
typedef struct Stack {StDataType* array; // 指向动态开辟的数组size_t size; // 有效数据个数size_t capicity; // 容量空间的大小
}Stack;void StackInit(Stack* psl, size_t capicity)
{assert(psl);psl->capicity = capicity;psl->array = (StDataType *)malloc(capicity * sizeof(StDataType));assert(psl->array);psl->size = 0;
}void StackDestory(Stack* psl)
{assert(psl);if (psl->array){free(psl->array);psl->array = NULL;psl->size = 0;psl->capicity = 0;}
}void CheckCapacity(Stack* psl)
{assert(psl);if (psl->size == psl->capicity){psl->capicity *= 2;psl->array = (StDataType *)realloc(psl->array, psl->capicity * sizeof(StDataType));}
}void StackPush(Stack* psl, StDataType x)
{assert(psl);CheckCapacity(psl);psl->array[psl->size] = x;psl->size++;
}void StackPop(Stack* psl)
{assert(psl || psl->size);psl->size--;
}StDataType StackTop(Stack* psl)
{if (StackIsEmpty(psl)){return (StDataType)0;}return psl->array[psl->size - 1];
}int StackIsEmpty(Stack* psl)
{return psl->size == 0;
}
