美文网首页
二叉树的遍历

二叉树的遍历

作者: 吕艳凯 | 来源:发表于2019-12-04 18:44 被阅读0次

二叉树有很多种,二叉查找树是其中的一种
二叉查找树在二叉树的基础上增加了以下几个条件。
如果左子树不为空,则左子树上所有节点的值均小于根节点的值
如果右子树不为空,则右子树上所有节点的值均大于根节点的值
左、右子树也都是二叉查找树

二叉树,是典型的非线性数据结构,遍历时需要把非线性关联的节点转化成一个线性的序列,以不同的方式来遍历,遍历出的序列顺序也不同。

二叉树都有哪些遍历方式呢?

  1. 前序遍历。
  2. 中序遍历。
  3. 后序遍历。
  4. 层序遍历。

从更宏观的角度来看,二叉树的遍历归结为两大类。

  1. 深度优先遍历(前序遍历、中序遍历、后序遍历)。
  2. 广度优先遍历(层序遍历)。

深度优先和广度优先这两个概念不止局限于二叉树,它们更是一种抽象的算法思想,决定了访问某些复杂数据结构的顺序。

深度优先遍历

1. 前序遍历(Preorder Traversal)
方法:先访问根节点,然后访问左子树,最后访问右子树。在访问左、右子树的时候,同样,先访问子树的根节点,再访问子树根节点的左子树和右子树,这是一个不断递归的过程。
理解:前序遍历的特点就是遍历根节点的同时,在访问左节点时判断是否左节点为根节点,找到最小左字数,然后按照根节点,左子树,右子树的顺序遍历

前序遍历.gif
应用场景:运用最多的场合包括在树里进行搜索以及创建一棵新的树。

2. 中序遍历(Inorder Traversal)
方法:先访问左子树,然后访问根节点,最后访问右子树,在访问左、右子树的时候,同样,先访问子树的左边,再访问子树的根节点,最后再访问子树的右边。
理解:中序遍历的主要特别点就是遍历过程是一个从小到大的过程,根据左<中<右的特点,依大小顺序遍历

中序遍历.gif

应用场景:最常见的是二叉搜索树,由于二叉搜索树的性质就是左孩子小于根节点,根节点小于右孩子,对二叉搜索树进行中序遍历的时候,被访问到的节点大小是按顺序进行的。

3. 后序遍历(Postorder Traversal)
方法:先访问左子树,然后访问右子树,最后访问根节点。
理解:仿佛修叶子,从左向右,把最低端的叶子修剪

后序遍历.gif
应用场景:在对某个节点进行分析的时候,需要来自左子树和右子树的信息。收集信息的操作是从树的底部不断地往上进行,好比你在修剪一棵树的叶子,修剪的方法是从外面不断地往根部将叶子一片片地修剪掉。

递归方式代码实现:
二叉树,每个根节点下必有左、右两个子树,所以二叉树可以拆分为n个只含有一个根节点、左子树、右子树的最小二叉树。基于递归的算法思想,只需要根据遍历规则顺序输出最小二叉树,然后不断的自调。
具体代码:

/**
* 构建二叉树
* @param inputList 输入序列
*/
public static TreeNode createBinaryTree(LinkedList<Integer>inputList){
    TreeNode node = null;
    if(inputList==null || inputList.isEmpty()){
        return null;
    }
    Integer data = inputList.removeFirst();
    if(data != null){
        node = new TreeNode(data);
        node.leftChild = createBinaryTree(inputList);
        node.rightChild = createBinaryTree(inputList);
    }
    return node;
}

/**
* 二叉树前序遍历
* @param node 二叉树节点
*/
public static void preOrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    System.out.println(node.data);
    preOrderTraveral(node.leftChild);
    preOrderTraveral(node.rightChild);
}

/**
* 二叉树中序遍历
* @param node 二叉树节点
*/
public static void inOrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    inOrderTraveral(node.leftChild);
    System.out.println(node.data);
    inOrderTraveral(node.rightChild);
}


/**
* 二叉树后序遍历
* @param node 二叉树节点
*/
public static void postOrderTraveral(TreeNode node){
    if(node == null){
        return;
    }
    postOrderTraveral(node.leftChild);
    postOrderTraveral(node.rightChild);
    System.out.println(node.data);
}


/**
* 二叉树节点
*/
private static class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;

    TreeNode(int data) {
        this.data = data;
    }
}

public static void main(String[] args) {
    LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
    TreeNode treeNode = createBinaryTree(inputList);
    System.out.println(" 前序遍历:");
    preOrderTraveral(treeNode);
    System.out.println(" 中序遍历:");
    inOrderTraveral(treeNode);
    System.out.println(" 后序遍历:");
    postOrderTraveral(treeNode);
}

在代码的main函数中,通过{3,2,9,null,null,10,null,null,8,null,4}这样一个线性序列,构建成的二叉树如下。


image.png

非递归代码实现:
基本思想:
依据遍历规则将左节点依次入栈,然后利用栈的回溯性,找到非叶子节点的右节点
具体代码:

/**
* 二叉树非递归前序遍历
* @param root 二叉树根节点
*/
public static void preOrderTraveralWithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode treeNode = root;
    while(treeNode!=null || !stack.isEmpty()){
        //迭代访问节点的左孩子,并入栈
        while (treeNode != null){
            System.out.println(treeNode.data);
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子,则弹出栈顶节点,访问节点右孩子
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            treeNode = treeNode.rightChild;
        }
    }
}

/**
* 二叉树非递归中序遍历
* @param root 二叉树根节点
*/
public static void preOrderTraveralWithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode treeNode = root;
    while(treeNode!=null || !stack.isEmpty()){
        //迭代访问节点的左孩子,并入栈
        while (treeNode != null){
            stack.push(treeNode);
            treeNode = treeNode.leftChild;
        }
        //如果节点没有左孩子,则弹出栈顶节点,输出节点,找右孩子
        //如果没有右孩子,则取栈顶节点,输出节点,即位前一个左孩子的根节点,再找右孩子
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            System.out.println(treeNode.data);
            treeNode = treeNode.rightChild;
        }
    }
}
//后序遍历有待开发

广度优先遍历

如果说深度优先遍历是在一个方向上“一头扎到底”,那么广度优先遍历则恰恰相反:先在各个方向上各走出1步,再在各个方向上走出第2步、第3步……一直到各个方向全部走完。
层序遍历,顾名思义,就是二叉树按照从根节点到叶子节点的层次关系,一层一层横向遍历各个节点。


image.png

上图就是一个二叉树的层序遍历,每个节点左侧的序号代表该节点的输出顺序。
广度优先遍历要借助一个数据结构来辅助工作,这个数据结构就是队列。
具体思想就是:从上到下,遍历队列,输出节点的同时,将节点的左右非空孩子节点入队,根据队列先进先出的特点,则遍历过程就是一个按照层级的输出过程。
具体代码如下:

/**
* 二叉树层序遍历
* @param root 二叉树根节点
*/
public static void levelOrderTraversal(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    //先将根节点入队
    queue.offer(root);
    while(!queue.isEmpty()){
        //按入队顺序出队输出
        TreeNode node = queue.poll();
        System.out.println(node.data);
        //将左右非空孩子节点入队
        if(node.leftChild != null){
            queue.offer(node.leftChild);
        }
        if(node.rightChild != null){
            queue.offer(node.rightChild);
        }
    }
}

相关文章

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 关于二叉树的算法题

    前序遍历中序遍历后序遍历判断是否是平衡二叉树判断是否是对称二叉树判断二叉树高度按照层遍历二叉树判断二叉树宽度

  • 二叉树三种遍历Swift代码实现

    二叉树的三种遍历 二叉树 前序遍历 中序遍历 后序遍历 另外 不得不说,得到二叉树的前序遍历和中序遍历的结果或者后...

  • 数据结构与算法之二叉树遍历(七)

    目录 前序遍历中序遍历后序遍历层序遍历遍历方式的选择条件根据遍历结果重构二叉树翻转二叉树计算二叉树的高度判断一棵树...

  • 二叉树的遍历

    二叉树的遍历 二叉树遍历 分为前序遍历、中序遍历和后序遍历。 前序遍历 (DLR) 先访问根节点,然后前序遍历左子...

  • 数据结构:树的实现和遍历(c++)

    (一)二叉树的遍历——递归实现 二叉树常见的遍历方式分为前序遍历、中序遍历和后序遍历。 1 前序遍历 前序遍历也叫...

  • 二叉树的蛇形层次遍历(LeetCode.103)

    题目 解析 首先参考二叉树的层次遍历层次遍历二叉树(LeetCode--102二叉树的层次遍历)[https://...

  • 算法精选题总结之二叉树类

    1.二叉树的中序遍历中序遍历的迭代方法中序遍历的递归方法2.二叉树前序遍历3.二叉树后续遍历4.二叉树的最近公共祖...

网友评论

      本文标题:二叉树的遍历

      本文链接:https://www.haomeiwen.com/subject/wmwlgctx.html