二叉树关键概念点
二叉树的遍历
首发于微信公众号东哥夜谈。欢迎关注东哥夜谈，让我们一起聊聊个人成长、投资、编程、电影、运动等话题。
本帐号所有文章均为原创。文章可以随意转载，但请务必注明作者。如果觉得文章有用，欢迎转发朋友圈分享。
1 问题
这段时间在研究数据结构，在二叉树上花了不少时间，感觉终于摸到了点正确的学习方法。
以二叉树为例。二叉树的概念是从上到下的链表，每个结点有两个子树。二叉树的关键操作为遍历，遍历又分为以下几类：
- 先序遍历
- 递归法
- 堆栈法
- 中序遍历
- 递归法
- 堆栈法
- 后序遍历
- 递归法
- 堆栈法
- 层次遍历
- 队列法
所以一共有递归法、堆栈法和队列发三种方法。把这三种方法搞清楚了，遍历问题就可以说是基本解决。
下面我们以中国大学MOOC 2017年里陈越、何钦铭的数据结构第03-01题为例，说明这几种遍历的方法。
输入格式:
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输入样例：
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
最后生成的二叉树：
2 数据结构分析
层级遍历需要用到队列法。核心思想是先把根结点放入队列，然后每次从队首取出结点时，都将其子结点按从左到右的顺序放入队列。这样最后队列为空时，所有结点按从上到下、从左到右的顺序遍历结束。
输入数据为三个，大写英文字母、左孩子编号、右孩子编号。考虑用二叉树完成，需要额外用两个指针 lchild 和 rchild。故需要设置数据结构如下
typedef struct BiNode * BiTree;
struct BiNode
{
char data[2];
int left, right, loc;
BiTree lchild, rchild;
};
用二叉树及链表时的一个好习惯是设置头结点。对于本题目，需要先读入结点数。我们用头结点的loc 域存放该数据。
3 队列法
用队列法遍历需要用到队列，该队列需要有两个参数，一个用来存放结点指针，一个用来存放队列下一项的指针。队列需要有存放头指针和尾指针的地方，于是还需要一个结构体来表示该队列。
于是有如下数据结构
typedef struct QNode * QPointer;
struct QNode
{
BiTree data;
QPointer next;
};
struct QLink
{
QPointer front;
QPointer rear;
};
层次遍历先将找到的根结点放入队列，然后依次取出，每次取出时将其子结点放入队列。类似二叉树，我们给队列也设置一个头结点，最初将头指针和尾指针都指向该结点，每放入一个树结点就新生成一个队列结点，将树结点的指针存放在 data 域里，同时将尾指针后移到该结点。每取出一个树结点，就将头结点后移，并将该队列结点空间释放。
对于本题目，可在数据读入的时候生成树结点，依次将每一个后输入的结点都作为前一个输入的左孩子，则最后会形成一个以输入顺序为顺序的左斜二叉树。然后我们只需要在其中找出根结点，然后根据根结点里面存储的 left/right 域，相应查找各个子结点即可。
于是有如下代码
tree->lchild = pBefore->lchild; // pBefore 为根结点的父节点，可通过遍历找到；
// 该处必须用父节点，因为后面需要断开排序好的树结点；
Queue.front = Queue.rear = (QPointer)malloc(sizeof(struct QNode)); // 生成头结点
Queue.front->data = NULL; // 原则：任何时候都不要出现随机指向的指针；
Queue.rear->next = (QPointer)malloc(sizeof(struct QNode));
Queue.rear = Queue.rear->next;
Queue.rear->data = tree->lchild; // 放入根结点
Queue.rear->next = NULL;
pBefore->lchild = pBefore->lchild->lchild; // 断开排序好的树结点
tree->lchild->lchild = NULL; // 排完序的树结点因为其子结点尚未找到，先设置为空；
// 第二次强调原则：任何时候都不要出现随机指向的指针；
while (Queue.front->next != NULL) {
tCurrent = Queue.front->next->data;
if(tCurrent->left != -1)
{
pBefore = line; // line 为原输入的乱序左斜二叉树；
while (tCurrent->left != pBefore->lchild->loc) {
pBefore = pBefore->lchild;
}
Queue.rear->next = (QPointer)malloc(sizeof(struct QNode));
Queue.rear = Queue.rear->next;
Queue.rear->data = pBefore->lchild;
Queue.rear->next = NULL;
pBefore->lchild = pBefore->lchild->lchild;
tCurrent->lchild = Queue.rear->data;
}
else tCurrent->lchild = NULL;
if(tCurrent->right != -1)
{
pBefore = line; // line 为原输入的乱序左斜二叉树；
while (tCurrent->right != pBefore->lchild->loc) {
pBefore = pBefore->lchild;
}
Queue.rear->next = (QPointer)malloc(sizeof(struct QNode));
Queue.rear = Queue.rear->next;
Queue.rear->data = pBefore->lchild;
Queue.rear->next = NULL;
pBefore->lchild = pBefore->lchild->lchild;
tCurrent->rchild = Queue.rear->data;
}
else tCurrent->rchild = NULL;
qTmp = Queue.front->next; // 释放已被取出的队头结点
Queue.front->next = qTmp->next;
free(qTmp);
} // End while
3 递归法
递归法的核心在于深入一直到最后一个结点，然后返回。用递归可以形成先序访问、中序访问和后续访问三种遍历方法。
用刚才生成的二叉树举例，即输入
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
采用依次打印各数据的方法访问。对于先序访问，是先打印父节点，然后递归进入子结点，打印该时的父节点，再递归进入子结点。当子结点打印完毕后，返回到上一级父节点，打印其右结点，然后返回。于是有
int TPrePrint(BiTree tree)
{
// This function printf the tree with a head Node.
if (strlen(tree->data) == 0) {
TPrePrint(tree->lchild);
return 0;
}
printf("data: \t%s, the address is:\t%p.\n", tree->data, tree);
printf("\tThe lchild is %p, the rchild is %p.\n", tree->lchild, tree->rchild);
if(tree->lchild!=NULL) TPrePrint(tree->lchild);
if(tree->rchild!=NULL) TPrePrint(tree->rchild);
return 0;
}
这里打印的时候没有打印头结点，因为头结点不算是二叉树内容的组成部分。所以要提前设置一个判断头结点的方法，这里用的是其 data 为空。其他方法也可以，比如 loc 为负值。
对于中序访问，则可改为
int TInPrint(BiTree tree)
{
// This function printf the tree with a head Node.
if (strlen(tree->data) == 0) {
TInPrint(tree->lchild);
return 0;
}
if(tree->lchild!=NULL) TInPrint(tree->lchild);
printf("%s ", tree->data);
if(tree->rchild!=NULL) TInPrint(tree->rchild);
return 0;
}
对于后续访问，可改为
int TPostPrint(BiTree tree)
{
// This function printf the tree with a head Node.
if (strlen(tree->data) == 0) {
TPostPrint(tree->lchild);
return 0;
}
if(tree->lchild!=NULL) TPostPrint(tree->lchild);
if(tree->rchild!=NULL) TPostPrint(tree->rchild);
printf("%s ", tree->data);
return 0;
}
打印的结果顺序会相应有所不同。
4 堆栈法
堆栈法需要先建立堆栈。堆栈可以用单向链表的方法建立，所以需要先建立单向链表数据。堆栈与队列的结点数据内容其实一样，区别在于队列需要一个结构体，里面存储队列头尾两个指针，而堆栈只需要一个头指针即可，也就不需要结构体。所以可以直接利用队列的数据结构来做堆栈，故有
typedef struct QSNode * QSPointer;
struct QSNode
{
BiTree data;
QSPointer next;
};
从根结点开始，将每一个结点放入堆栈，然后移向其左孩子。当左孩子为空时，结点出栈，移向其右孩子。先序遍历和中序遍历的区别在于，先序是在结点入栈的时候访问，中序是在其结点出栈、准备移向其右孩子的时候访问。
所以，对于先序遍历，有
while (tCurrent != NULL || stack->next != NULL) {
// tCurrent != NULL is ok to Push
// stack->next != NULL is ok to Pop
while(tCurrent != NULL)
{
sCurrent = stack->next;
stack->next = (QSPointer)malloc(sizeof(struct QSNode));
printf("%s ", tCurrent->data); // Visit before in stack
stack->next->data = tCurrent;
stack->next->next = sCurrent;
tCurrent = tCurrent->lchild; // in stack over;
} // End while. now tCurrent == NULL.
if(stack->next != NULL){
// Pop stack
sCurrent = stack->next;
stack->next = sCurrent->next; // Pop
tCurrent = sCurrent->data->rchild;
}
}
对于中序遍历，有
while (tCurrent != NULL || stack->next != NULL) {
// tCurrent != NULL is ok to Push
// stack->next != NULL is ok to Pop
while(tCurrent != NULL)
{
sCurrent = stack->next;
stack->next = (QSPointer)malloc(sizeof(struct QSNode));
stack->next->data = tCurrent;
stack->next->next = sCurrent;
tCurrent = tCurrent->lchild; // in stack over;
} // End while. now tCurrent == NULL.
if(stack->next != NULL){
// Pop stack
sCurrent = stack->next;
stack->next = sCurrent->next; // Pop
tCurrent = sCurrent->data;
printf("%s ", tCurrent->data);
tCurrent = tCurrent->rchild;
}
}
但对后序遍历，就有问题了。后序遍历的时候，结点入栈，然后移向其左孩子；当左孩子为空时，结点出栈（1），然后移向其右孩子。当右孩子为空时，结点出栈（2），访问该结点。
可以看出，该结点需要出栈两次，所以也需要入栈两次。在左孩子为空处返回出栈后，就需要再次入栈；直到从右孩子为空再次返回出栈，这时才需要访问。所以第一次出栈是不可访问的，第二次出栈才可以访问，我们需要一个变量跟踪其出栈次数。
所以栈结点除了像之前的栈结点那样有两个指针外，还需要一个变量用来标识其访问次数，所以栈结点需要修改为
typedef struct SNode * pSNode;
struct SNode
{
int flag;
BiTree data;
pSNode next;
};
相应的遍历流程可以修改为
tCurrent = tree->lchild;
while (tCurrent != NULL || stack->next != NULL) {
sCurrent = stack->next;
if (tCurrent != NULL) {
stack->next = (pSNode)malloc(sizeof(struct SNode));
stack->next->data = tCurrent;
stack->next->flag = 1;
stack->next->next = sCurrent;
tCurrent = tCurrent->lchild;
} // End while. tree node in stack. tree->lchild == NULL;
else
{
if(sCurrent->flag == 1) // Pop and go rchild
{
tCurrent = sCurrent->data->rchild;
sCurrent->flag = 2; // 再次入栈
}
else
{
stack->next = sCurrent->next; // 出栈
printf("%s ", sCurrent->data->data); // 访问
}
}
}
至此，用堆栈法后序遍历二叉树搞定。
相关代码可详见代码仓库：PTA0300
http://t.cn/RloOpfB
5 总结
数据结构第一部分链表还算简单，第二部分二叉树把我难住很久，一道题花好几天的时间都搞不定。无数次碰壁之后终于渐渐意识到，自己以前的「听理论，勤思考」的方式其实不怎么好。
计算机领域很多问题，都已经有很成熟的解决方法。我们需要做的，是了解这些解决方案，在需要的时候恰当的调用就是了，完全没有必要搞独创。
所谓学习，首先是消化和理解前人总结出来的经典算法。根据概念自创方法，貌似高端，实际效果却很差。想要走得快，先要学会潜的深。
公众号里有朋友问，如何自学 Python？其实学习这事儿，都是相通的，Python 也不例外。无外乎找几本经典教材，把基本知识搞定，然后勤动手写代码就是了。
但为什么有无数的人经历无数次从入门到放弃？错的不在方法，在自己。自己是不是热爱，自己有没有坚持。
有没有连续一周把所有业余时间都花上，为了一个调试错误不眠不休。有没有心惊胆战的点了运行程序却奔溃，自己也崩溃，却能在狠狠的揪完头发后，开始下一轮的排查。
就像这点东西，我大概用了两周。衣带渐宽，为她憔悴啊。
就看你，有没有这个韧性，能不能搞定。而已。