java数组实现数据结构：自由树

叁歲伎倆 2022-02-15 08:37 279阅读 0赞

在之前我们学习了数组和链表等线性结构的数据类型，今天来了解一下**非线性结构**的数据类型**树**（***一对多***）。树形结构在我们日常生活中经常会用到，比如我们的论文目录、部门人员结构图和计算机系统的文件结构等等。它和一般的线性结构相比更具有层次性，它的功能比线性数据结构的功能更强大。因此作者这篇文章介绍一下怎样用数组实现一个自由树。

先从网上搜集一下树的相关定义和属性特点：

### *解释* ###

***树状图**是一种[数据结构][Link 1]，它是由n（n>=1）个有限结点组成一个具有层次关系的[集合][Link 2]。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：*

*每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树*

### *定义* ###

***树**（tree）是包含n（n>=0）个结点的有穷集，其中：*

*（1）每个元素称为结点（node）；*

*（2）有一个特定的结点被称为根结点或树根（root）。*

*（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。*

*树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。*

*我们可以形式地给出树的[递归][Link 3]定义如下:*

*单个结点是一棵树，树根就是该结点本身。*

*设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。*

*空集合也是树，称为空树。空树中没有结点。*

## *相关术语* ##

***节点的度**：一个节点含有的子树的个数称为该节点的度；*

***叶节点或终端节点**：度为0的节点称为叶节点；*

***非终端节点或分支节点**：度不为0的节点；*

***双亲节点或父节点**：若一个节点含有子节点，则这个节点称为其子节点的父节点；*

***孩子节点或子节点**：一个节点含有的子树的根节点称为该节点的子节点；*

***兄弟节点**：具有相同父节点的节点互称为兄弟节点；*

***树的度**：一棵树中，最大的节点的度称为树的度；*

***节点的层次**：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；*

***树的高度或深度**：树中节点的最大层次；*

***堂兄弟节点**：双亲在同一层的节点互为堂兄弟；*

***节点的祖先**：从根到该节点所经分支上的所有节点；*

***子孙**：以某节点为根的子树中任一节点都称为该节点的子孙。*

***森林**：由m（m>=0）棵互不相交的树的集合称为森林；*

看完上面一大堆的专业术语介绍自后，在你的脑海里应该有一个大概的模型了，但可能还不够清晰，下面我们用一张图来帮助我们理解一下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70][]

树形结构示意图

这张图片就表示了一颗自由树的一种形态，如果我们把这张图旋转180°，那么这各结构就接近像我们生活中的一棵树，在树的底端是树的根和主干，然后往上就是树的主干长出的树的枝条，枝条之间是没有交叉关系的，都是从主干中独立出去的一部分，再往上就是树的叶子了。

我们今天学习的这个树形结构同样可以用这些名词来描述，只不过我们学习的这个树形结构是倒过来的，在它的顶端是它的根（图中的1号节点就是根节点），一个树形结构最多只能有一个根（它可以没有根，没有根的树我们称之为空树），根下面可以有0-n个节点（2、3、4号节点都属于根的子节点），每个节点下面又可以有0-n个子节点...没有子节点的节点我们称之为叶子（5、6、7、8均属于叶子节点），因为它已经是最顶层了。另外除了根之外，树形结构的其余节点或叶子都有且只有一个父节点。

在树形结构中每个节点到根节点之间都只有唯一一条路径。

添加新节点操作：往树形结构中添加新的节点时需要指定其父节点是谁。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 1][]

添加新节点示意图

图中红色9号为新添加的节点，它指定的父节点为2号节点，因此添加后9号节点连在2号节点下面。

删除节点操作：若删除的节点为叶子节点，则只删除它本身，否则会删除该节点及其所有子孙节点，若删除的节点为根节点，则删除整棵树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 2][]

删除节点示意图

图中删除的是3号节点，所以3号节点及其子节点6号和7号都将被删除。

遍历操作：找出图中所有的节点到根节点的路径，并找到所有节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 3][]

遍历节点示意图

## 实现 ##

在理论学习了树形结构的相关特点之后我们现在用代码来实现一下。

树的实现有两种方式：

1.  数组
2.  链表

今天这篇文章将介绍怎样用数组实现自由树。

先整理一下需求：

1.  我们需要创建一棵树
2.  可以实现往树中添加新的节点
3.  可以实现删除树中的某节点及其子节点
4.  可以返回树的深度
5.  可以遍历树中的所有节点
6.  可以返回一个节点的父节点
7.  可以返回一个节点下面的所有子节点

暂时我们就先完成这7条需求；

话不多说，上代码：

package dataStructure;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * Created by Viking on 2019/4/22
     */
    public class MyArrayTree<E> {
    
        private static final int DEFAULT_SIZE=20;
        private int size;
        private Node<E>[] nodes;
        private int nodeNum;
    
        @SuppressWarnings("unchecked")
        public MyArrayTree(E data){
            size = DEFAULT_SIZE;
            nodes = new Node[size];
            nodes[0] = new Node<>(data,-1);
            nodeNum++;
        }
        @SuppressWarnings("unchecked")
        public MyArrayTree(E data,int capacity){
            size = capacity;
            nodes = new Node[size];
            nodes[0] = new Node<>(data,-1);
            nodeNum++;
        }
    
        /**
         * 添加新节点
         */
        public Node<E> addNode(E data,Node parent){
            for (int i=0;i<size;i++){
                if (null==nodes[i]) {
                    nodes[i] = new Node<>(data, pos(parent));
                    nodeNum++;
                    return nodes[i];
                }
            }
            throw new RuntimeException("该树已满,无法添加新节点");
        }
    
        /**
         * 删除节点及其所有子节点
         */
        public void remove(Node node){
            while (children(node).size()>0){
                for (Node child : children(node)){
                    remove(child);
                }
            }
            for (int i=0;i<nodes.length;i++){
                if (nodes[i]!=null&&nodes[i]==node){
                    nodes[i]=null;
                    size--;
                }
            }
        }
        public List<String> list(){
            return list(getRoot());
        }
        public List<String> list(Node root){
            return list(new ArrayList<>(),"",root);
        }
        /**
         * 遍历
         */
        private List<String> list(List<String>list,String index,Node root){
            List<Node<E>> children = children(root);
            list.add(index+root.data);
            while (children.size()>0){
                for (Node node : children){
                    list = list(list,index+"\t",node);
                }
                children.clear();
            }
            return list;
        }
    
        public boolean isEmpty(){
            return nodeNum==0;
        }
        public Node<E> getRoot(){
            return nodes[0];
        }
        public Node<E> getParent(Node node){
            return nodes[node.parent];
        }
        /**
         * 列出所有的子节点
         */
        public List<Node<E>> children(Node node){
            List<Node<E>> list = new ArrayList<>();
            for (int i=0;i<size;i++){
                if (null!=nodes[i]&&nodes[i].parent==pos(node))
                    list.add(nodes[i]);
            }
            return list;
        }
    
        /**
         * 树的深度
         */
        public int deep(){
            int max = 0;
            for (int i = 0;i<size&&nodes[i]!=null;i++){
                int deep = 1;
                int p = nodes[i].parent;
                while(-1!=p&&nodes[p]!=null){
                    p = nodes[p].parent;
                    deep++;
                }
                if (deep>max) max = deep;
            }
            return max;
        }
    
        private int pos(Node node){
            for (int i=0;i<size;i++){
                if (nodes[i]==node) return i;
            }
            return -1;
        }
    
        public static class Node<T>{
            T data;
            int parent;
    
            public Node(T data ,int parent){
                this.data = data;
                this.parent = parent;
            }
        }
    }

编写一个测试类：

import dataStructure.MyArrayTree;
    
    import java.util.List;
    
    /**
     * Created by Viking on 2019/4/22
     * 测试自定义实现的树形结构
     */
    public class TestMyTree {
    
        public static void main(String[] args) {
            MyArrayTree<String> tree = new MyArrayTree<>("root");
            System.out.println("Before add node:"+tree.deep());
            MyArrayTree.Node<String> node = tree.addNode("node", tree.getRoot());
            System.out.println("After add node:"+tree.deep());
            MyArrayTree.Node<String> root = tree.getRoot();
            List<MyArrayTree.Node<String>> children = tree.children(root);
            tree.addNode("Children",children.get(0));
            System.out.println("After children node:"+tree.deep());
            tree.remove(tree.children(children.get(0)).get(0));
            System.out.println("After remove node:"+tree.deep());
            MyArrayTree.Node<String> left = tree.addNode("left", root);
            MyArrayTree.Node<String> right = tree.addNode("right", root);
            tree.addNode("grandson1OfLeft",left);
            tree.addNode("grandson2OfLeft",left);
            tree.addNode("grandson1OfRight",right);
            tree.addNode("grandson2OfRight",right);
            MyArrayTree.Node<String> childOfNode = tree.addNode("childOfNode", node);
            tree.addNode("childOfNodes'child",childOfNode);
            List<String> list = tree.list();
            for (String data : list){
                System.out.println(data);
            }
            System.out.println("----------------------------------");
            List<String> list1 = tree.list(node);
            for (String data : list1){
                System.out.println(data);
            }
        }
    }

测试结果：

Before add node:1
    After add node:2
    After children node:3
    After remove node:2
    root
    	node
    		childOfNode
    			childOfNodes'child
    	left
    		grandson1OfLeft
    		grandson2OfLeft
    	right
    		grandson1OfRight
    		grandson2OfRight
    ----------------------------------
    node
    	childOfNode
    		childOfNodes'child

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450
[Link 2]: https://baike.baidu.com/item/%E9%9B%86%E5%90%88
[Link 3]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70]: /images/20220215/1426a22c8ff0404badea080a2ed3e69c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 1]: /images/20220215/b2ed058b2e8247c983e084480c6c908e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 2]: /images/20220215/2546c37a5df6433fa1f9871b92c5b40e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 3]: /images/20220215/ff38f66b9c7d4053aba5c6ca29891cc0.png