【数据结构与算法笔记02】对树的遍历方式的思考

树的遍历

　　树的遍历算法分为两种：广度优先遍历（BFS）和深度优先遍历（DFS）。

　　所谓的BFS其实就是层次遍历，而DFS指的是前序/中序/后序遍历。

广度优先遍历：

　　用队列实现，迭代:

  • Init: Q.push(root)
  • Each Loop: 取出队首元素：①访问该元素 ②将该节点的左孩子右孩子依次入队（先入队的先访问，所以如果是从左至右访问每一层就先把左孩子入队，从右至左访问就先把右孩子入队）

　　

深度优先遍历：

　　从根结点开始，沿着一个方向一直走到底，走到走不下去了就回退到父节点，从父节点的另一个孩子开始，再沿着这个方向一路往下走...重复这个过程直到把树中所有的节点都访问过一遍。

　　如果每次都沿着向左的方向一路走到底，那其实意味着访问到每一个节点时都选择接下来优先访问该节点的左孩子（这其实就是先序遍历啊喂！！）

　　

前序、中序、后序遍历：（就是DFS！！这两个给我放在一起理解！）

 　　在深度优先遍历中：每个节点会被经过3次，而前序、中序、后序的区别在于：在哪一次经过该节点时对其进行访问。

2. 递归实现

traverseRecursive(BiTrNode* node):

    basecase:
        if(node == nullptr) return;

    general:
        1 print(node->data);
        2 traverseRecursive(node->lchild);
        3 traverseRecursive(node->rchild);

        前序：123
        中序：213
        后序：132

3. 非递归实现

　　首先需要明确的是，所谓的递归实现其实是在模拟递归栈，所以使用的基本数据结构是stack。

　　这里如何设计节点的入栈策略是关键，因为执行的时候无非就是依次从stack中取出栈顶元素进行处理，所以stack中节点的入栈顺序就是访问顺序。

　　那既然我们已经知道了，每个节点都会被经过3次，所谓前序、中序、后序的区别无非就是第几次经过时对其进行操作（这里我们把对节点的操作简化成print node->data）。

初步想法

　　给每一个节点增加一个字段(lookTimes)表示这是第几次经过该节点。

　　模拟一下3次经过的入栈顺序：①第一次经过该节点 -> ②遍历该节点的左孩子 -> ③回到该节点（第二次经过）-> ④遍历该节点的右孩子 -> ⑤回到该节点（第三次经过）。

　　init：所有节点的lookTimes都设为0，将根节点入栈。

　　从stack中取出栈顶元素表示经过一次该节点(lookTimes++)，然后看lookTimes进行相应的操作：

  • lookTimes = 1：第一次访问该节点，接下来要访问该节点的左子树，然后再回到该节点，再所以应该依次：push（自己），push（左孩子） （后入先出）
  • lookTimes = 2：第二次访问该节点，接下来要访问该节点的右子树，然后再回到该节点，所以应该依次：push（自己），push（右孩子）
  • lookTimes = 3：第三次访问该节点，此时对该节点的3次访问就结束了，所以就没有什么额外操作等着取下一个节点就行了。

　　模拟好3次经过之后，要实现前序/中序/后序遍历只需在每一次push前print(node->data)就可以了。比如，如果是前序遍历就在p->lookTimes == 1的if语句块的第一行加上print(node->data)就可以了。

　　伪码如下：

//version1.0
while(stack is not empty){
        p = stack.pop();
        (p->lookTimes)++;

        if(p->lookTimes == 1){
            //print(p->data); 前序遍历
            stack.push(p);
            if(p->lchild)
                stack.push(p->lchild);
        }else if(p->lookTimes == 2){
            //print(p->data); 中序遍历
            stack.push(p);
            if(p->lchild)
                stack.push(p->rchild);
        }else if(p->lookTimes == 3){
            //print(p->data); 后序遍历
        }         
    }

优化版本

　　上面是一种比较通用的想法，但是在考虑到具体的某一种遍历方式时，比如前序遍历：既然在lookTimes == 1时就已经对该节点进行访问了，那么后面的两次回到该节点显然是没有必要的。

　　因此根据每一种遍历方式的特点进行优化：

　　1. 前序

　　入栈顺序：①第一次经过该节点 -> ②遍历该节点的左孩子 -> ③遍历该节点的右孩子。而且这样的话每个节点只会经过一次，lookTimes字段也就没有必要了。

//前序遍历_version2.0：without lookTimes    
while(stack is not empty){
        p = stack.pop();
        print(p->data);

        if(p->lchild)
                stack.push(p->lchild);

        if(p->rchild)
                stack.push(p->rchild);         
 }

　　2. 中序

　　入栈顺序：①第一次经过该节点 -> ②遍历该节点的左孩子 -> ③回到该节点（第二次经过）-> ④遍历该节点的右孩子。

//中序遍历_version2.0
while(stack is not empty){
        p = stack.pop();
        (p->lookTimes)++;

        if(p->lookTimes == 1){
            stack.push(p);
            if(p->lchild)
                stack.push(p->lchild);
        }else if(p->lookTimes == 2){
            print(p->data);
            if(p->lchild)
                stack.push(p->rchild);
        }   
    }

　　3. 后序

　　后序因为在第三次经过时才会访问，所以不能再优化了。

数据结构与算法学习笔记

相关

标签