专栏首页老沙课堂数据结构与算法(六) 二叉树遍历

数据结构与算法(六) 二叉树遍历

二叉树遍历

二叉搜索树(Binary Search Tree)

又称为二叉查找树,二叉排序树。简称为BST

•任意一个节点的值都大于子树的值•任意一个节点的值都小于子树的值•他的左右子树也是一颗二叉搜索树•二叉搜索树可以大大提高效率(搜索和添加删除时间复杂度都是logn)•二叉搜索树的元素必须是具备可比较性•自定义类型需要指定比较方式•不允许为null•二叉树没有索引的概念

•前序遍历(Preorder Traversal)•中序遍历(Inorder Traversal)•后序遍历(Postorder Traversal)•层序遍历(Level Order Traversal)

所说的序是指根节点的顺序

二叉树遍历

二叉树例子

前序遍历(Perorder Traversal)

遍历顺序:根节点,左子树,右子树

10,8,6,3,7,8,9,12,11,13

public void preorderTraversal() {
    preorderTraversal(root);
}

private void preorderTraversal(Node<E> node) {
    if (node == null) {
        return;
    }
    System.out.println(node.element);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

中序遍历(Inrorder Traversal)

遍历顺序:左子树,根节点,右子树。

3,6,7,8,9,10,11,12,13

遍历顺序:右子树,根节点,左子树。

13,12,11,10,9,8,7,6,3

•如果是二叉搜索树(BST)中序遍历输出为有序数列

public void inorderTraversal() {
  inorderTraversal(root);
}

private void inorderTraversal(Node<E> node) {
  if (node == null) {
    return;
  }
  inorderTraversal(node.left);
  System.out.println(node.element);
  inorderTraversal(node.right);
}

后序遍历(Postorder Traversal)

遍历顺序:左子树,右子树,根节点。

3,7,6,9,8,11,13,12,10

遍历顺序:右子树,左子树,根节点。

13,11,12,9,7,3,6,8,10

public void postorderTraversal() {
  postderTraversal(root);
}

private void postderTraversal(Node<E> node) {
  if (node == null) {
    return;
  }
  postderTraversal(node.left);
  postderTraversal(node.right);
  System.out.println(node.element);
}

层序遍历(Level Order Traversal)

一层一层的访问, 从上到下 ,从左到右。

10,8,9,6,9,11,13,3,7

实现思路:

利用队列

1、将跟节点入队

2、while(队列不为空){

将队头节点出队 进行访问

将队头左右子节点分别入队

}

public void levelOrderTraversal() {
  if (root == null) {
    return;
  }
  Queue<Node<E>> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    Node<E> node = queue.poll();
    System.out.println(node.element);
    if(node.left != null) {
      queue.offer(node.left);    
    }
    if(node.right!= null) {
      queue.offer(node.right);
    }    
  }
}

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(六) 二叉树

    •每个节点的度最大为2。•左子树和右子树是有序的。•即使某个节点只有一颗子树,也要区分是左右子树。

    老沙
  • 数据结构与算法(十二) 红黑树

    •节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节...

    老沙
  • 数据结构与算法(十一)B树

    •1个节点可以存储超过2个元素、可以拥有超过2个子节点•拥有二叉搜索树的一些特质(小的子节点在左面 大的子节点在右面)•平衡,每个节点的所有子树高度一致•比较矮

    老沙
  • [数据结构]C语言二叉树的实现

    树和图是数据结构中比较麻烦的东西,里面涉及的概念比较多,也最有用, 就比如一般树广泛应用于人工智能的博弈上,而基于图的广度优先和深度优先搜索也广泛应用于人工智能...

    racaljk
  • 二叉树层次遍历

    二叉树层次遍历,又称为宽度优先搜索,按树的层次依次访问树的结点。层次遍历使用队列对遍历节点进行 存储,先进入队列的结点, 优先遍历拓展其左孩子与 右孩子。

    小飞侠xp
  • 前端学数据结构与算法(六):二叉树的四种遍历方式及其应用

    上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历。主要包括前序遍历、中序遍历、后序...

    飞跃疯人院
  • Data Structure前情提要——二叉树红黑树

    叶子节点就是左右孩子都是空的,但是并不是每一颗树都像上图所示的那样这么规整,有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值,...

    西红柿炒鸡蛋
  • 数据结构+算法(第13篇):精通二叉树的“独门忍术”——线索二叉树(上)

    如果要写出非递归的遍历算法,无论用哪种遍历方法,根据《再不会“降维打击”你就Out了!》《神力加身!动态编程》《史上最猛之递归屠龙奥义》三篇文章中讲到的知识和技...

    用户5224393
  • List、Set、Map 集合遍历 小结

    Map:Map不继承Collection接口。Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个value。

    qubianzhong
  • 一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

    二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找...

    desperate633

扫码关注云+社区

领取腾讯云代金券