二叉树关键概念点

in c •  7 years ago 

二叉树的遍历

首发于微信公众号东哥夜谈。欢迎关注东哥夜谈,让我们一起聊聊个人成长、投资、编程、电影、运动等话题。
本帐号所有文章均为原创。文章可以随意转载,但请务必注明作者。如果觉得文章有用,欢迎转发朋友圈分享。


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 也不例外。无外乎找几本经典教材,把基本知识搞定,然后勤动手写代码就是了。

但为什么有无数的人经历无数次从入门到放弃?错的不在方法,在自己。自己是不是热爱,自己有没有坚持。

有没有连续一周把所有业余时间都花上,为了一个调试错误不眠不休。有没有心惊胆战的点了运行程序却奔溃,自己也崩溃,却能在狠狠的揪完头发后,开始下一轮的排查。

就像这点东西,我大概用了两周。衣带渐宽,为她憔悴啊。

就看你,有没有这个韧性,能不能搞定。而已。

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!