【数据结构与算法之树结构】二叉树的遍历

不念不忘少年蓝@ 2024-03-25 14:12 109阅读 0赞

#### 【数据结构与算法之树结构】二叉树的遍历 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之树结构】二叉树的遍历
         *   *   *  1 基于深度优先搜索的遍历
                 *   *  先序遍历DLR
                     *  中序遍历 LDR
                     *  后序遍历 LRD
                 *  2 按层次遍历

二叉树的遍历分为两种：

*  基于深度优先搜索的遍历，先中后序都属于这种
 *  按层次遍历

举个栗子，下面这棵树

![在这里插入图片描述][68a47b6509e747138d6c9d4b93bd7a97.png_pic_center]

###### 1 基于深度优先搜索的遍历 ######

基于深度优先搜索的遍历算法一般有三种：

*  先序遍历 DLR
 *  中序遍历 LDR
 *  后序遍历 LRD

D 根节点，L 左子树， R 右子树。

3种遍历算法都是基于递归的思想。

###### 先序遍历DLR ######

1.  访问根节点
2.  先序遍历根节点的左子树
3.  先序遍历根节点的右子树

Java代码描述：

public void PreOrderTraverse(BinaryTreeNode root) {
        
        visit(root); // 访问根节点
        PreOrderTraverse(root.leftChild);
        PreOrderTraverse(root.rightChild);
    }

对上面图中的树进行先序遍历的结果为\*\*\{2, 3, 5, 0, 6, 7\}\*\*

###### 中序遍历 LDR ######

1.  中序遍历根节点的左子树
2.  访问根节点
3.  中序遍历根节点的右子树

Java代码描述：

public void InOrderTraverse(BinaryTreeNode root) {
        
        InOrderTraverse(root.leftChild);
        visit(root);
        InOrderTraverse(root.rightChild);
    }

对上面图中的树进行中序遍历的结果为\*\*\{5, 3, 0, 2, 7, 6\}\*\*

###### 后序遍历 LRD ######

1.  后序遍历根节点的左子树
2.  后序遍历根节点的右子树
3.  访问根节点

Java代码描述：

public void PostOrderTraverse(BinaryTreeNode root) {
        
        PostOrderTraverse(root.leftChild);
        PostOrderTraverse(root.rightChild);
        visit(root);
    }

对上面图中的树进行后序遍历的结果为\*\*\{5, 0, 3, 7, 6, 2\}\*\*

###### 2 按层次遍历 ######

按层次遍历二叉树是一种基于广度优先搜索思想的二叉树遍历算法。

在遍历时，需要一个队列作为辅助，步骤：

1.  将二叉树的根节点指针入队
2.  将队首的指针元素出队并利用这个指针访问该节点，然后依次将该节点的左孩子(如果存在)和右孩子(如果存在)的指针入队。
3.  重复2， 直到队空

Java代码描述：

public void LayerOrderTraverse() {
        
        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
        queue.offer(root); // 根节点入队
    
        while (!queue.isEmpty()) {
        
            BinaryTreeNode node = queue.poll(); // 取出队头元素
            visit(node); // 访问该节点
            if (node.leftChild != null) {
        
                queue.offer(node.leftChild); // 左孩子不为空就入队
            }
            if (node.rightChild != null) {
        
                queue.offer(node.rightChild); // 右孩子不为空就入队
            }
        }
    }

对上面图中的树进行层次遍历的结果为\{2, 3, 6, 5, 0, 7\}

[68a47b6509e747138d6c9d4b93bd7a97.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/fda73a0431fa4c89b0bf6873a3592203.png