一、树

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

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

二、树的父节点表示法

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

package com.ietree.basic.datastructure.tree;

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

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

  public static class Node<T> {

    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<E>[] nodes;
  // 记录树的节点数
  private int nodeNums;

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

  // 以指定根节点、指定treeSize创建树
  public TreeParent(E data, int treeSize) {
    this.treeSize = treeSize;
    nodes = new Node[treeSize];
    nodes[0] = new Node<E>(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<E> root() {
    // 返回根节点
    return nodes[0];
  }

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

  // 返回指定节点（非叶子节点）的所有子节点
  public List<Node<E>> children(Node parent) {
    List<Node<E>> list = new ArrayList<Node<E>>();
    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<String> tp = new TreeParent<String>("root");
    TreeParent.Node root = tp.root();
    System.out.println(root);
    tp.addNode("节点1", root);
    System.out.println("此树的深度：" + tp.deep());
    tp.addNode("节点2", root);
    // 获取根节点的所有子节点
    List<TreeParent.Node<String>> 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<E> {

  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> {
    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<E>[] nodes;
  // 记录节点数
  private int nodeNums;

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

  // 以指定根节点、指定treeSize创建树
  public TreeChild(E data, int treeSize) {
    this.treeSize = treeSize;
    nodes = new Node[treeSize];
    nodes[0] = new Node<E>(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<E> root() {
    // 返回根节点
    return nodes[0];
  }

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

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

  }

  // 返回指定节点（非叶子节点）的第index个子节点
  public Node<E> 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<String> tp = new TreeChild<String>("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<TreeChild.Node<String>> 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树存储结构  # Java  # 树形结构存储  # java递归实现树形结构数据完整案例  # java数据结构之树基本概念解析及代码示例  # java父子节点parentid树形结构数据的规整  # 子树  # 一棵树  # 其父  # 第一个  # 递归  # 已满  # 为空  # 组中  # 都有  # 是一种  # 多个  # 这是一个  # 只有一个  # 为其  # 被称为  # 大家多多  # 棵树  # 其子  # 链表  # 链中 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： JS中对数组元素进行增删改移的方法总结  如何用PHP快速搭建CMS系统？  教你用AI润色文章，让你的文字表达更专业  高端建站如何打造兼具美学与转化的品牌官网？  BootStrap整体框架之基础布局组件  EditPlus中的正则表达式 实战(2)  Bootstrap CSS布局之列表  Win11怎样安装网易有道词典_Win11安装词典教程【步骤】  怎么用AI帮你设计一套个性化的手机App图标？  Laravel中DTO是什么概念_在Laravel项目中使用数据传输对象(DTO)  如何快速搭建高效服务器建站系统？  高防网站服务器：DDoS防御与BGP线路的AI智能防护方案  iOS发送验证码倒计时应用  中山网站制作网页,中山新生登记系统登记流程？  制作企业网站建设方案,怎样建设一个公司网站？  香港服务器网站推广：SEO优化与外贸独立站搭建策略  香港服务器如何优化才能显著提升网站加载速度？  Laravel Asset编译怎么配置_Laravel Vite前端构建工具使用  Laravel事件和监听器如何实现_Laravel Events & Listeners解耦应用的实战教程  edge浏览器无法安装扩展 edge浏览器插件安装失败【解决方法】  Laravel如何实现API版本控制_Laravel版本化API设计方案  Python面向对象测试方法_mock解析【教程】  Laravel怎么实现搜索功能_Laravel使用Eloquent实现模糊查询与多条件搜索【实例】  Laravel如何使用.env文件管理环境变量？（最佳实践）  javascript日期怎么处理_如何格式化输出  详解Android图表 MPAndroidChart折线图  微博html5版本怎么弄发语音微博_语音录制入口及时长限制操作【教程】  公司门户网站制作流程,华为官网怎么做？  如何在宝塔面板中修改默认建站目录？  C#如何调用原生C++ COM对象详解  Python正则表达式进阶教程_复杂匹配与分组替换解析  Windows驱动无法加载错误解决方法_驱动签名验证失败处理步骤  Laravel中的Facade(门面)到底是什么原理  Edge浏览器如何截图和滚动截图_微软Edge网页捕获功能使用教程【技巧】  android nfc常用标签读取总结  linux写shell需要注意的问题(必看)  Chrome浏览器标签页分组怎么用_谷歌浏览器整理标签页技巧【效率】  Laravel如何配置中间件Middleware_Laravel自定义中间件拦截请求与权限校验【步骤】  Laravel的辅助函数有哪些_Laravel常用Helpers函数提高开发效率  Laravel请求验证怎么写_Laravel Validator自定义表单验证规则教程  Laravel如何与Docker（Sail）协同开发？（环境搭建教程）  如何在万网利用已有域名快速建站？  ,南京靠谱的征婚网站？  如何在新浪SAE免费搭建个人博客？  jQuery中的100个技巧汇总  laravel怎么为应用开启和关闭维护模式_laravel应用维护模式开启与关闭方法  简历在线制作网站免费版,如何创建个人简历？  如何在 Telegram Web View（iOS）中防止键盘遮挡底部输入框  Python自动化办公教程_ExcelWordPDF批量处理案例  如何快速重置建站主机并恢复默认配置？