@[TOC]
前言：
思维导图
建议
- 二叉树是一种
递归结构!!!!!!!!!,这一点一定要时刻牢记。- 递归利用
分而自治的思想 ，对于解决二叉树问题，很方便- 递归我们一般建议先判断
假的情况，这会很大层度方便解决问题。- 在使用递归时，如果不能一下完成所有代码，可以先完成大致的部分，之后慢慢补齐细节问题。
递归的3要素
- 递归函数返回值的使用问题
- 递归函数的参数设置问题
- 递归的结束条件的判断问题。
二叉树的遍历
遍历的意思就是：打印一个二叉树中的每个结点的值，但是因为存在左右子树，二叉树的遍历有4种：前序遍历，中序遍历，后序遍历，层序遍历
PS:
- 对与空结点，默认打印NULL,方便查看。
- 遍历只能遍历玩当前的树，才能遍历其它的上一层树，或者兄弟层树。
前序遍历
要求在遍历二叉树的左右子树前， 先打印==根结点==的值，在遍历==左子树==，当==左子树遍历完==，再遍历==右子树==。简记：根-左-右
递归
思路
依据三要素：
- 前序遍历函数不需要返回值，因此void
参数，只需要一个指针就行了，因此
void PreOrder(BTNode* root);// 二叉树前序遍历---递归法
3.结束条件：if(root==NULL)
{printf("NULL "); return ;}
4. 遍历顺序printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right)
完整代码
//前序遍历是根在左右孩子前，先访问二叉树根结点。
void PreOrder(BTNode* root)
{
if(root==NULL)
{
printf("NULL ");
return ;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}非递归
思路
我们知道函数栈帧是发生在==栈区==的，而这个栈区的
特点(先进后出，先用低地址后用高地址)和数据结构中的==栈==是相同的，因此这里我们可以通过数据结构的==栈==来模拟==函数栈帧==时的==栈区==。
- 首先因为栈的特点–先进后出，因此左子树必须先被访问，因此我们先将右子树的地址存放的数组栈中，再将左子树存到数组栈中。
代码
void PreOrderNoR(BTNode* root)// 二叉树前序遍历---非递归法
{
assert(root);
stack st;
StackInit(&st);
//我们需要根结点来进入右子树，因此要存根结点
//同时一旦左子树访问完后，再进入右子树时需要根结点，后面就不需要了。因此pop
SDateType p = root;
while (1)
{
if (p != NULL)
{
printf("%c->", p->data);
StackPush(&st, p);
p = p->left;
}
else
{
printf("NULL->");
break;
}
}
while (!StackEmpty(&st)||p)//空树或者栈空结束
{
/
//p为空说明，根和左子树遍历完毕。
if (!StackEmpty(&st))
{
p = StackTop(&st);
StackPop(&st);
p = p->right;
while (1)
{
if (p != NULL)
{
printf("%c->", p->data);
StackPush(&st, p);
p = p->left;
}
else
{
printf("NULL->");
break;
}
}
}
}
printf("\n");
StackDestroy(&st);
}中序遍历
再访问根结点前，先访问左子树，当左子树为空后，再访问根结点，然后访问右子树。简介：左–根–右
递归
思路
同前序遍历差不多，需要将左子树递归完，再访问根结点。
代码
void InOrder(BTNode* root)// 二叉树中序遍历
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}非递归
思路
同样使用栈模拟栈区。但是数组栈中要先存放左子树的地址，当存入空树后，就可以访问根结点，然后遍历右子树，重复这个过程。
代码
void InOrderNoR(BTNode* root)// 二叉树中序遍历---递归法
{
assert(root);
stack st;
StackInit(&st);
//我们需要根结点来进入右子树，因此要存根
SDateType p = root;
//遍历到左子树最低端.
while (1)
{
if (p != NULL)
{
StackPush(&st, p);
p = p->left;
}
else
{
printf("NULL->");
break;
}
}
while (!StackEmpty(&st) || p)//空树或者栈空结束
{
if (!StackEmpty(&st))
{
SDateType tmp= StackTop(&st);
printf("%c->", tmp->data);
StackPop(&st);
p = tmp->right;
//根结点已经遍历玩比，后续的遍历就不需要它了。
//无论右子树是否为空，即使回来也不需要根结点。
//遍历到左子树最低端.
while (1)
{
if (p != NULL)
{
StackPush(&st, p);
p = p->left;
}
else
{
printf("NULL->");
break;
}
}
}
}
printf("\n");
StackDestroy(&st);
}后序遍历
在访问根结点前，要把 左，右子树访问完，才能访问根结点。简记：左-右-根
递归
思路
和前序相似，只是需要先将左右访问结束，再访问根结点
代码
void PostOrder(BTNode* root)// 二叉树后序遍历
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}非递归
思路
1.只有当左右子树访问完后，才能访问根结点。
因此要有一个pVisist指针来记录已访问的左或右子树。当pVisit=p->right||p- >right==NULL时，访问根结点。
2.我们访问存在的右子树时，仍把它看作一棵二叉树，因此仍需要压栈与出栈，
3.这里我打印NULL来帮助更好理解，
代码
void PostOrderNoR(BTNode* root)// 二叉树后序遍历---非递归法
{
//思路：1.只有当左右子树访问完后，才能访问根结点。
// 因此要有一个pVisist指针来记录已访问的左或右子树。当pVisit=p->right||p->right==NULL时，访问根结点。
// 2.我们访问存在的右子树时，仍把它看作一棵二叉树，因此仍需要压栈与出栈，
// 3.这里我打印NULL来帮助更好理解，
assert(root);
assert(root);
stack st;
StackInit(&st);
SDateType p = root;
SDateType pVisit = NULL;//标记左右子树的
//简化版--只是将Top赋值给p了，但是要注意当右子树不为空，一定要直接进行左子树入栈。因为p的值并不是空。
while (1)//先将左子树压栈，当左子树为空后，开始访问右子树。
{
if (p == NULL)
{
printf("NULL->");
break;
}
else
{
StackPush(&st, p);
p = p->left;
}
}
while (!StackEmpty(&st) || p)//空树或者栈空结束
{
if (!StackEmpty(&st))
{
p = StackTop(&st);
//只有当右子树为空或者右子树已访问才访问根结点,才能删除根结点.
if (p->right == NULL || p->right == pVisit)
{
if (p->right == NULL)
{
printf("NULL->");
}
StackPop(&st);
printf("%c->", p->data);
pVisit = p;
//这一部代表该子树已访问，但是不确实是左子树还是右子树，因此需要 p->right == pVisit
}
else
{
p = p->right;//下次循环将是右子树的遍历。
while (1)
{
if (p == NULL)
{
printf("NULL->");
break;
}
else
{
StackPush(&st, p);
p = p->left;
}
}
}
}
}
printf("\n");
StackDestroy(&st);
}层序遍历
- 层序遍历与前中后不同。它要求必须将树一层的结点遍历完，再遍历下一层。
- 层序遍历利用
队列来实现层序遍历。- 注意因为队列的特点（先进先出），需要左子树要先入队列。
代码
void LevelOrder(BTNode* root)// 层序遍历
{
if (root == NULL)
{
return;
}
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* tmp = QueueTop(&q);
printf("%c ", tmp->data);
QueuePop(&q);
if (tmp->left != NULL)
{
QueuePush(&q, tmp->left);
}
if (tmp->right != NULL)
{
QueuePush(&q, tmp->right);
}
}
QueueDestroy(&q);
}