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

巴特西

Java中树的存储结构实现

一、树

二、树的父节点表示法

三、子节点链表示法

最新文章

热门文章