Java中树的存储结构实现示例代码

一、树

成都创新互联公司是一家集网站建设,越秀企业网站建设,越秀品牌网站建设,网站定制,越秀网站建设报价,网络营销,网络优化,越秀网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

树与线性表、栈、队列等线性结构不同，树是一种非线性结构。

一棵树只有一个根节点，如果一棵树有了多个根节点，那它已经不再是一棵树了，而是多棵树的集合，也被称为森林。

二、树的父节点表示法

树中除根节点之外每个节点都有一个父节点，为了记录树中节点与节点之间的父子关系，可以为每个节点增加一个parent域，用以记录该节点的父节点。

package com.ietree.basic.datastructure.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by ietree
 * 2017/4/30
 */
public class TreeParent {

  public static class Node {

    T data;
    // 保存其父节点的位置
    int parent;

    public Node() {

    }

    public Node(T data) {
      this.data = data;
    }

    public Node(T data, int parent) {
      this.data = data;
      this.parent = parent;
    }

    public String toString() {
      return "TreeParent$Node[data=" + data + ", parent=" + parent + "]";
    }

  }

  private final int DEFAULT_TREE_SIZE = 100;
  private int treeSize = 0;
  // 使用一个Node[]数组来记录该树里的所有节点
  private Node[] nodes;
  // 记录树的节点数
  private int nodeNums;

  // 以指定节点创建树
  public TreeParent(E data) {
    treeSize = DEFAULT_TREE_SIZE;
    nodes = new Node[treeSize];
    nodes[0] = new Node(data, -1);
    nodeNums++;
  }

  // 以指定根节点、指定treeSize创建树
  public TreeParent(E data, int treeSize) {
    this.treeSize = treeSize;
    nodes = new Node[treeSize];
    nodes[0] = new Node(data, -1);
    nodeNums++;
  }

  // 为指定节点添加子节点
  public void addNode(E data, Node parent) {
    for (int i = 0; i < treeSize; i++) {
      // 找到数组中第一个为null的元素，该元素保存新节点
      if (nodes[i] == null) {
        // 创建新节点，并用指定的数组元素保存它
        nodes[i] = new Node(data, pos(parent));
        nodeNums++;
        return;
      }
    }
    throw new RuntimeException("该树已满，无法添加新节点");
  }

  // 判断树是否为空
  public boolean empty() {
    // 根结点是否为null
    return nodes[0] == null;
  }

  // 返回根节点
  public Node root() {
    // 返回根节点
    return nodes[0];
  }

  // 返回指定节点（非根结点）的父节点
  public Node parent(Node node) {
    // 每个节点的parent记录了其父节点的位置
    return nodes[node.parent];
  }

  // 返回指定节点（非叶子节点）的所有子节点
  public List> children(Node parent) {
    List> list = new ArrayList>();
    for (int i = 0; i < treeSize; i++) {
      // 如果当前节点的父节点的位置等于parent节点的位置
      if (nodes[i] != null && nodes[i].parent == pos(parent)) {
        list.add(nodes[i]);
      }
    }
    return list;
  }

  // 返回该树的深度
  public int deep() {
    // 用于记录节点的最大深度
    int max = 0;
    for (int i = 0; i < treeSize && nodes[i] != null; i++) {
      // 初始化本节点的深度
      int def = 1;
      // m 记录当前节点的父节点的位置
      int m = nodes[i].parent;
      // 如果其父节点存在
      while (m != -1 && nodes[m] != null) {
        // 向上继续搜索父节点
        m = nodes[m].parent;
        def++;
      }
      if (max < def) {
        max = def;
      }
    }
    return max;
  }

  // 返回包含指定值的节点
  public int pos(Node node) {
    for (int i = 0; i < treeSize; i++) {
      // 找到指定节点
      if (nodes[i] == node) {
        return i;
      }
    }
    return -1;
  }

}

测试类：

package com.ietree.basic.datastructure.tree;

import java.util.List;

/**
 * Created by ietree
 * 2017/4/30
 */
public class treeParentTest {

  public static void main(String[] args) {

    TreeParent tp = new TreeParent("root");
    TreeParent.Node root = tp.root();
    System.out.println(root);
    tp.addNode("节点1", root);
    System.out.println("此树的深度：" + tp.deep());
    tp.addNode("节点2", root);
    // 获取根节点的所有子节点
    List> nodes = tp.children(root);
    System.out.println("根节点的第一个子节点：" + nodes.get(0));
    // 为根节点的第一个子节点新增一个子节点
    tp.addNode("节点3", nodes.get(0));
    System.out.println("此树的深度：" + tp.deep());

  }
}

程序输出：

TreeParent$Node[data=root, parent=-1]
此树的深度：2
根节点的第一个子节点：TreeParent$Node[data=节点1, parent=0]
此树的深度：3

三、子节点链表示法

让父节点记住它的所有子节点。

package com.ietree.basic.datastructure.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by ietree
 * 2017/4/30
 */
public class TreeChild {

  private static class SonNode {
    // 记录当前节点的位置
    private int pos;
    private SonNode next;

    public SonNode(int pos, SonNode next) {
      this.pos = pos;
      this.next = next;
    }
  }

  public static class Node {
    T data;
    // 记录第一个子节点
    SonNode first;

    public Node(T data) {
      this.data = data;
      this.first = null;
    }

    public String toString() {
      if (first != null) {
        return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]";
      } else {
        return "TreeChild$Node[data=" + data + ", first=-1]";
      }
    }
  }

  private final int DEFAULT_TREE_SIZE = 100;
  private int treeSize = 0;
  // 使用一个Node[]数组来记录该树里的所有节点
  private Node[] nodes;
  // 记录节点数
  private int nodeNums;

  // 以指定根节点创建树
  public TreeChild(E data) {
    treeSize = DEFAULT_TREE_SIZE;
    nodes = new Node[treeSize];
    nodes[0] = new Node(data);
    nodeNums++;
  }

  // 以指定根节点、指定treeSize创建树
  public TreeChild(E data, int treeSize) {
    this.treeSize = treeSize;
    nodes = new Node[treeSize];
    nodes[0] = new Node(data);
    nodeNums++;
  }

  // 为指定节点添加子节点
  public void addNode(E data, Node parent) {
    for (int i = 0; i < treeSize; i++) {
      // 找到数组中第一个为null的元素，该元素保存新节点
      if (nodes[i] == null) {
        // 创建新节点，并用指定数组元素保存它
        nodes[i] = new Node(data);
        if (parent.first == null) {
          parent.first = new SonNode(i, null);
        } else {
          SonNode next = parent.first;
          while (next.next != null) {
            next = next.next;
          }
          next.next = new SonNode(i, null);
        }
        nodeNums++;
        return;
      }
    }
    throw new RuntimeException("该树已满，无法添加新节点");
  }

  // 判断树是否为空
  public boolean empty() {
    // 根结点是否为null
    return nodes[0] == null;
  }

  // 返回根节点
  public Node root() {
    // 返回根节点
    return nodes[0];
  }

  // 返回指定节点（非叶子节点）的所有子节点
  public List> children(Node parent) {

    List> list = new ArrayList>();
    // 获取parent节点的第一个子节点
    SonNode next = parent.first;
    // 沿着孩子链不断搜索下一个孩子节点
    while (next != null) {
      // 添加孩子链中的节点
      list.add(nodes[next.pos]);
      next = next.next;
    }
    return list;

  }

  // 返回指定节点（非叶子节点）的第index个子节点
  public Node child(Node parent, int index) {
    // 获取parent节点的第一个子节点
    SonNode next = parent.first;
    // 沿着孩子链不断搜索下一个孩子节点
    for (int i = 0; next != null; i++) {
      if (index == i) {
        return nodes[next.pos];
      }
      next = next.next;
    }
    return null;
  }

  // 返回该树的深度
  public int deep() {
    // 获取该树的深度
    return deep(root());
  }

  // 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
  private int deep(Node node) {
    if (node.first == null) {
      return 1;
    } else {
      // 记录其所有子树的最大深度
      int max = 0;
      SonNode next = node.first;
      // 沿着孩子链不断搜索下一个孩子节点
      while (next != null) {
        // 获取以其子节点为根的子树的深度
        int tmp = deep(nodes[next.pos]);
        if (tmp > max) {
          max = tmp;
        }
        next = next.next;
      }
      // 最后，返回其所有子树的最大深度 + 1
      return max + 1;
    }
  }

  // 返回包含指定值得节点
  public int pos(Node node) {
    for (int i = 0; i < treeSize; i++) {
      // 找到指定节点
      if (nodes[i] == node) {
        return i;
      }
    }
    return -1;
  }

}

测试类：

package com.ietree.basic.datastructure.tree;

import java.util.List;

/**
 * Created by ietree
 * 2017/4/30
 */
public class TreeChildTest {

  public static void main(String[] args) {

    TreeChild tp = new TreeChild("root");
    TreeChild.Node root = tp.root();
    System.out.println(root);
    tp.addNode("节点1", root);
    tp.addNode("节点2", root);
    tp.addNode("节点3", root);
    System.out.println("添加子节点后的根结点：" + root);
    System.out.println("此树的深度：" + tp.deep());
    // 获取根节点的所有子节点
    List> nodes = tp.children(root);
    System.out.println("根节点的第一个子节点：" + nodes.get(0));
    // 为根节点的第一个子节点新增一个子节点
    tp.addNode("节点4", nodes.get(0));
    System.out.println("此树第一个子节点：" + nodes.get(0));
    System.out.println("此树的深度：" + tp.deep());

  }

}

程序输出：

TreeChild$Node[data=root, first=-1]
添加子节点后的根结点：TreeChild$Node[data=root, first=1]
此树的深度：2
根节点的第一个子节点：TreeChild$Node[data=节点1, first=-1]
此树第一个子节点：TreeChild$Node[data=节点1, first=4]
此树的深度：3

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持创新互联。

网页标题：Java中树的存储结构实现示例代码
文章位置：http://chengdu.cdxwcx.cn/article/giggeh.html

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

首页

网站建设

网站制作案例

解决方案

网站设计报价

网站制作动态

关于我们

联系我们

成都网站建设设计将想法与焦点和您一起共享

Java中树的存储结构实现示例代码

其他资讯

个性域名怎么加个性域名注册

php怎么处理数据库 php数据库编程

二维码c语言生成函数二维码生成 c语言

为什么c语言递归函数卡住 c语言递归语句

阿里云服务器设置白名单阿里云oss ip白名单

甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

成都网站建设设计 将想法与焦点和您一起共享

Java中树的存储结构实现示例代码

其他资讯

个性域名怎么加 个性域名注册

php怎么处理数据库 php数据库编程

二维码c语言生成函数 二维码生成 c语言

为什么c语言递归函数卡住 c语言递归语句

阿里云服务器设置白名单 阿里云oss ip白名单

成都网站建设设计将想法与焦点和您一起共享

个性域名怎么加个性域名注册

二维码c语言生成函数二维码生成 c语言

阿里云服务器设置白名单阿里云oss ip白名单