二叉树的遍历和查找

栏目: 数据库 · 发布时间: 3年前

内容简介:若二叉树非空,则执行以下操作:若二叉树非空,则执行以下操作:若二叉树非空,则执行以下操作:

前序遍历

若二叉树非空,则执行以下操作:

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

中序遍历

若二叉树非空,则执行以下操作:

  1. 中序遍历左子树;
  2. 访问根结点;
  3. 中序遍历右子树。

后序遍历

若二叉树非空,则执行以下操作:

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

实例说明

graph TD 3-->1 3-->5 1-->2 5-->4 5-->6

对于上面的二叉树而言,

  1. 前序遍历结果: 3 1 2 5 4 6
  2. 中序遍历结果: 1 2 3 4 5 6
  3. 后序遍历结果: 2 1 4 6 5 3

树的遍历代码实现

定义一个树结构

@ToString
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

定义一个遍历方式的枚举

/**
 * 遍历的方向.
 */
enum Direct {
  /**
   * 中序
   */
  middle,
  /**
   * 前序
   */
  before,
  /**
   * 后序
   */
  after;
}

实现代码

/**
   * 遍历.
   */
  public void print(Direct direct) {
    StringBuffer stringBuffer = new StringBuffer();
    print(stringBuffer, this, direct, "ROOT:");
    System.out.println(stringBuffer.toString());
  }

  private void print(StringBuffer stringBuffer, TreeNode treeNode, Direct direct, String node) {
    if (treeNode != null) {

      if (direct == Direct.before) {
        stringBuffer.append(node + treeNode.val + "\n");
        print(stringBuffer, treeNode.left, direct, "L:");
        print(stringBuffer, treeNode.right, direct, "R:");
      } else if (direct == Direct.middle) {
        print(stringBuffer, treeNode.left, direct, "L:");
        stringBuffer.append(node + treeNode.val + "\n");
        print(stringBuffer, treeNode.right, direct, "R:");
      } else {
        print(stringBuffer, treeNode.left, direct, "L:");
        print(stringBuffer, treeNode.right, direct, "R:");
        stringBuffer.append(node + treeNode.val + "\n");
      }
    }
  }

二叉查询树实现了二分查找法

时间复杂度是Olog(n)到O(n),也就是说它最好的情况是Olog(n),当然运气不好,也就是你查询的是叶子节点,那就是O(n)了。

/*
   * 二分查找,最优时间复杂度OLog(n).
   */
  private TreeNode search(TreeNode x, int key) {
    if (x == null)
      return x;

    int cmp = key - x.val;
    if (cmp < 0)
      return search(x.left, key);
    else if (cmp > 0)
      return search(x.right, key);
    else
      return x;
  }

  public TreeNode search(int key) {
    return search(this, key);
  }
}

对于树的知识还有很多,本文章主要介绍树的遍历和查找!


以上所述就是小编给大家介绍的《二叉树的遍历和查找》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

自制编译器

自制编译器

[日] 青木峰郎 / 严圣逸、绝云 / 人民邮电出版社 / 2016-6 / 99.00元

本书将带领读者从头开始制作一门语言的编译器。笔者特意为本书设计了CЬ语言,CЬ可以说是C语言的子集,实现了包括指针运算等在内的C语言的主要部分。本书所实现的编译器就是C Ь语言的编译器, 是实实在在的编译器,而非有诸多限制的玩具。另外,除编译器之外,本书对以编译器为中心的编程语言的运行环境,即编译器、汇编器、链接器、硬件、运行时环境等都有所提及,介绍了程序运行的所有环节。一起来看看 《自制编译器》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具