你好,游客 登录 注册 搜索
背景:
阅读新闻

Java中树的存储结构实现

[日期:2017-05-17] 来源:Linux社区  作者:Dylansuns [字体: ]

一、树

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

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

二、树的父节点表示法

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

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-05/143888.htm

linux
相关资讯       Java存储结构 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款