起航学习网

Java开发中知识点很多，不少学子为了能够学到Java开发中的详细技能，对Java开发中的某一些知识点也加以深究，下面就让我们一起来看看学员如何学习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<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

关于达内IT培训网，了解更多关于Java方面的技能，如果想要学习Java技能，赶紧来报名吧！

文章出自：http://qh.itpxw.cn/peixun/software/201736987.html

文章标题：达内教程：如何学习Java中树的存储结构实现



免责声明：本站文章均由入驻起航学习网的会员所发或者网络转载，所述观点仅代表作者本人，不代表起航学习网立场。如有侵权或者其他问题，请联系举报，必删。侵权投诉

(责任编辑：IT培训网)