二叉树的遍历
首发于微信公众号东哥夜谈。欢迎关注东哥夜谈,让我们一起聊聊个人成长、投资、编程、电影、运动等话题。
本帐号所有文章均为原创。文章可以随意转载,但请务必注明作者。如果觉得文章有用,欢迎转发朋友圈分享。
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 也不例外。无外乎找几本经典教材,把基本知识搞定,然后勤动手写代码就是了。
但为什么有无数的人经历无数次从入门到放弃?错的不在方法,在自己。自己是不是热爱,自己有没有坚持。
有没有连续一周把所有业余时间都花上,为了一个调试错误不眠不休。有没有心惊胆战的点了运行程序却奔溃,自己也崩溃,却能在狠狠的揪完头发后,开始下一轮的排查。
就像这点东西,我大概用了两周。衣带渐宽,为她憔悴啊。
就看你,有没有这个韧性,能不能搞定。而已。