图形二叉树和Java实现代码的三种遍历方法

二叉树是一棵树，其中每个节点不能有两个以上的子节点.

1. 二叉树节点

作为图的一种特殊形式，二叉树的基本组成是节点和边；作为数据结构二叉树 java实现，其基本组成实体是二叉树节点，边对应于节点之间的相互引用.

下面显示了二叉树节点的数据和相关代码:

  // 定义节点类：
  private static class BinNode {
    private Object element;
    private BinNode lChild;// 定义指向左子树的指针
    private BinNode rChild;// 定义指向右子树的指针
    public BinNode(Object element, BinNode lChild, BinNode rChild) {
      this.element = element;
      this.lChild = lChild;
      this.rChild = rChild;
    }
  }

2. 递归遍历

二叉树本身没有自然的全局顺序，因此为了实现遍历，有必要通过在每个节点及其子节点之间约定特定的局部顺序来间接定义特定的全局顺序.

通常，左兄弟优先于右兄弟，因此二叉树 java实现，如果节点及其子节点分别表示为V，L和R（如下图所示），则本地访问的顺序可以是三个选择: VLR，LVR和LRV. 根据节点V的访问顺序，这三种策略也分别称为前遍历，中阶遍历和后遍历.

2.1遍历

图标:

代码实现:

  /**
   * 对该二叉树进行前序遍历 结果存储到list中 前序遍历
   */
  public static void preOrder(BinNode node) {
    list.add(node); // 先将根节点存入list
    // 如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点
    if (node.lChild != null) {
      preOrder(node.lChild);
    }
    // 无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序
    if (node.rChild != null) {
      preOrder(node.rChild);
    }
  }

2.2有序遍历

图标:

代码实现:

  /**
   * 对该二叉树进行中序遍历 结果存储到list中
   */
  public static void inOrder(BinNode node) {
    if (node.lChild != null) {
      inOrder(node.lChild);
    }
    list.add(node);
    if (node.rChild != null) {
      inOrder(node.rChild);
    }
  }

2.3后遍历

示例说明:

代码实现:

  /**
   * 对该二叉树进行后序遍历 结果存储到list中
   */
  public static void postOrder(BinNode node) {
    if (node.lChild != null) {
      postOrder(node.lChild);
    }
    if (node.rChild != null) {
      postOrder(node.rChild);
    }
    list.add(node);
  }

附加: 测试相关代码

  private static BinNode root;
  private static List<BinNode> list = new ArrayList<BinNode>();
  public static void main(String[] args) {
    init();
    // TODO Auto-generated method stub
    //preOrder(root);
    //inOrder(root);
    postOrder(root);
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i).element + " ");
    }
  }
  // 树的初始化:先从叶节点开始,由叶到根
  public static void init() {
    BinNode b = new BinNode("b", null, null);
    BinNode a = new BinNode("a", null, b);
    BinNode c = new BinNode("c", a, null);
    BinNode e = new BinNode("e", null, null);
    BinNode g = new BinNode("g", null, null);
    BinNode f = new BinNode("f", e, g);
    BinNode h = new BinNode("h", f, null);
    BinNode d = new BinNode("d", c, h);
    BinNode j = new BinNode("j", null, null);
    BinNode k = new BinNode("k", j, null);
    BinNode m = new BinNode("m", null, null);
    BinNode o = new BinNode("o", null, null);
    BinNode p = new BinNode("p", o, null);
    BinNode n = new BinNode("n", m, p);
    BinNode l = new BinNode("l", k, n);
    root = new BinNode("i", d, l);
  }

以上是本文的全部内容. 希望对大家的学习有所帮助. 我也希望每个人都支持该脚本主页.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-147607-1.html