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

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());  }}

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());  }}