欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-01 23:36:10
一、树 树与线性表、栈、队列等线性结构不同,树是一种非线性结构。 一棵树只有一个根节点,如果一棵树有了多个根节点,那它已经不再是一棵树了,而是多棵树的集合,也被称为森林...

一、树

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

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

二、树的父节点表示法

树中除根节点之外每个节点都有一个父节点,为了记录树中节点与节点之间的父子关系,可以为每个节点增加一个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

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