Древовидная структура и реализация Java
содержание
предисловие
Когда дело доходит до структуры данных «дерева», я считаю, что первое, что приходит на ум, это «бинарное дерево».
Действительно, бинарное дерево является важной структурой данных, сочетающей в себе преимущества массивов и компоновщиков, и имеет множество важных приложений.
Все мы знаем, что функции запроса массива быстро, в соответствии с индексом, чтобы быстро найти элемент. Однако, если вы хотите вставить элемент, вам нужно переместить все элементы этого элемента после местоположения. В среднем длина упорядоченного массива N, количество элементов для перемещения элемента вставки равно N/2. Временная сложность упорядоченного массива вставляется O (N), временная сложность операции удаления также O (N).
Отсортированные массивы не рекомендуются для часто вставляемых и удаляемых данных.
Эффективность вставки и удаления связанного списка очень высока, пока ссылка на некоторые значения изменяется, временная сложность составляет O (1). Однако эффективность запроса связанного списка очень низка, и каждый раз, когда необходимо искать с самого начала, по очереди обращаются к каждому элементу данных связанного списка. В среднем, чтобы запросить элемент из связанного списка с N элементами, требуется пройти N/2 элемента, а временная сложность составляет O(N).
Связанные списки не рекомендуются для поиска часто встречающихся данных.
В этом разделе мы не будем знакомить с бинарным деревом, а сначала поговорим о структуре данных дерева. Я считаю, что со знаниями из этого раздела в качестве основы будет намного проще понять бинарное дерево.
концепция дерева
Обзор
В информатике дерево — это абстрактный тип данных (ADT) или структура данных, которая реализует этот абстрактный тип данных и используется для моделирования набора данных с древовидными свойствами.
Он состоит из n (n>0) конечных узлов, образующих набор с иерархическими отношениями.
Его называют «деревом», потому что оно выглядит как перевернутое дерево, что означает, что у него корни вверх, а листья вниз.
Он имеет следующие характеристики:
Каждый узел имеет только ограниченное количество дочерних элементов или не имеет дочерних элементов; Узел без родительского узла называется корневым узлом; Каждый некорневой узел имеет один и только один родительский узел; За исключением корневого узла, каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев; В дереве нет циклов -- Википедия
По определению дерева следующая структура не является "деревом":
срок
- дорожка
Все узлы, которые в свою очередь переходят от узла к другому узлу, являются путями между этими двумя узлами.
- корень
Верхний узел дерева называется корнем. Существует только один путь от корня к любому узлу.
- родительский узел
За исключением корневого узла, каждый узел может найти уникальный узел выше, который является родительским узлом текущего узла. Соответственно, дочерний узел находится ниже родительского узла.
- листовой узел
«Голый командир» без дочерних узлов называется листовым узлом.
- поддерево
Дерево, в котором каждый дочерний элемент является корнем, является поддеревом.
- Этаж
Алгебра древовидной структуры - это уровень дерева.
- Тратить
В дереве степень наибольшего узла называется степенью дерева.
- родственный узел
Узлы с одним и тем же родительским узлом называются родственными узлами;
практическое применение
Древовидная структура имеет очень широкий спектр применений, например, наша широко используемая система файловых каталогов является древовидной структурой.
Например, введите в командной строке CMD операционной системы Windows10treeкомандой, вы можете вывести дерево каталогов:
tree
卷 Windows 的文件夹 PATH 列表
卷序列号为 1CEB-7ABE
C:.
├─blog
│ ├─cache
│ │ └─JavaCacheGuidance
│ ├─datastructure
│ ├─editor
│ │ └─notepad++
│ ├─framework
│ │ └─guava
│ │ └─retry
│ ├─git
│ └─java
│ └─package-info
├─category
│ ├─food
│ │ ├─fruit
│ │ └─self
│ ├─job
│ │ └─bz
│ │ └─project
│ │ └─ad
│ │ └─exch
│ ├─people
│ ├─practical
│ │ └─work
│ │ └─ecommerce
│ │ └─inventory
│ ├─tech
│ │ ├─algorithm
│ │ │ └─tree
│ │ └─java
│ │ ├─concurrent
│ │ │ └─thread
│ │ ├─design
│ │ ├─i18n
│ │ ├─jcf
│ │ └─spring
│ │ └─springboot
│ └─tool
│ ├─data
│ │ └─db
│ │ ├─mysql
│ │ └─redis
│ └─site
│ └─stackoverflow
└─me
└─phonephoto
дерево реализации
После объяснения характеристик и связанных с ними концепций древовидной структуры далее используется Java для реализации основных операций древовидной структуры и демонстрации таких операций, как создание дерева, добавление дочерних узлов, обход дерева и поиск указанных узлов.
TreeNode
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.tree;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* 实现树结构
*
* @author ijiangtao
* @create 2019-04-18 15:13
**/
public class TreeNode<T> implements Iterable<TreeNode<T>> {
/**
* 树节点
*/
public T data;
/**
* 父节点，根没有父节点
*/
public TreeNode<T> parent;
/**
* 子节点，叶子节点没有子节点
*/
public List<TreeNode<T>> children;
/**
* 保存了当前节点及其所有子节点，方便查询
*/
private List<TreeNode<T>> elementsIndex;
/**
* 构造函数
*
* @param data
*/
public TreeNode(T data) {
this.data = data;
this.children = new LinkedList<TreeNode<T>>();
this.elementsIndex = new LinkedList<TreeNode<T>>();
this.elementsIndex.add(this);
}
/**
* 判断是否为根：根没有父节点
*
* @return
*/
public boolean isRoot() {
return parent == null;
}
/**
* 判断是否为叶子节点：子节点没有子节点
*
* @return
*/
public boolean isLeaf() {
return children.size() == 0;
}
/**
* 添加一个子节点
*
* @param child
* @return
*/
public TreeNode<T> addChild(T child) {
TreeNode<T> childNode = new TreeNode<T>(child);
childNode.parent = this;
this.children.add(childNode);
this.registerChildForSearch(childNode);
return childNode;
}
/**
* 获取当前节点的层
*
* @return
*/
public int getLevel() {
if (this.isRoot()) {
return 0;
} else {
return parent.getLevel() + 1;
}
}
/**
* 递归为当前节点以及当前节点的所有父节点增加新的节点
*
* @param node
*/
private void registerChildForSearch(TreeNode<T> node) {
elementsIndex.add(node);
if (parent != null) {
parent.registerChildForSearch(node);
}
}
/**
* 从当前节点及其所有子节点中搜索某节点
*
* @param cmp
* @return
*/
public TreeNode<T> findTreeNode(Comparable<T> cmp) {
for (TreeNode<T> element : this.elementsIndex) {
T elData = element.data;
if (cmp.compareTo(elData) == 0)
return element;
}
return null;
}
/**
* 获取当前节点的迭代器
*
* @return
*/
@Override
public Iterator<TreeNode<T>> iterator() {
TreeNodeIterator<T> iterator = new TreeNodeIterator<T>(this);
return iterator;
}
@Override
public String toString() {
return data != null ? data.toString() : "[tree data null]";
}
}
TreeNodeIterator
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.tree;
import java.util.Iterator;
/**
*
* 迭代器
*
* @author ijiangtao
* @create 2019-04-18 15:24
**/
public class TreeNodeIterator<T> implements Iterator<TreeNode<T>> {
enum ProcessStages {
ProcessParent, ProcessChildCurNode, ProcessChildSubNode
}
private ProcessStages doNext;
private TreeNode<T> next;
private Iterator<TreeNode<T>> childrenCurNodeIter;
private Iterator<TreeNode<T>> childrenSubNodeIter;
private TreeNode<T> treeNode;
public TreeNodeIterator(TreeNode<T> treeNode) {
this.treeNode = treeNode;
this.doNext = ProcessStages.ProcessParent;
this.childrenCurNodeIter = treeNode.children.iterator();
}
@Override
public boolean hasNext() {
if (this.doNext == ProcessStages.ProcessParent) {
this.next = this.treeNode;
this.doNext = ProcessStages.ProcessChildCurNode;
return true;
}
if (this.doNext == ProcessStages.ProcessChildCurNode) {
if (childrenCurNodeIter.hasNext()) {
TreeNode<T> childDirect = childrenCurNodeIter.next();
childrenSubNodeIter = childDirect.iterator();
this.doNext = ProcessStages.ProcessChildSubNode;
return hasNext();
} else {
this.doNext = null;
return false;
}
}
if (this.doNext == ProcessStages.ProcessChildSubNode) {
if (childrenSubNodeIter.hasNext()) {
this.next = childrenSubNodeIter.next();
return true;
} else {
this.next = null;
this.doNext = ProcessStages.ProcessChildCurNode;
return hasNext();
}
}
return false;
}
@Override
public TreeNode<T> next() {
return this.next;
}
/**
* 目前不支持删除节点
*/
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
контрольная работа
Древовидная структура, реализованная ниже, точно такая же, как древовидная структура на предыдущем рисунке.
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.tree;
/**
* tree
*
* @author ijiangtao
* @create 2019-04-18 15:03
**/
public class TreeDemo1 {
public static void main(String[] args) {
System.out.println("********************测试遍历*************************");
TreeNode<String> treeRoot = getSetA();
for (TreeNode<String> node : treeRoot) {
String indent = createIndent(node.getLevel());
System.out.println(indent + node.data);
}
System.out.println("********************测试搜索*************************");
Comparable<String> searchFCriteria = new Comparable<String>() {
@Override
public int compareTo(String treeData) {
if (treeData == null)
return 1;
boolean nodeOk = treeData.contains("F");
return nodeOk ? 0 : 1;
}
};
TreeNode<String> foundF = treeRoot.findTreeNode(searchFCriteria);
System.out.println("F: parent=" + foundF.parent + ",children=" + foundF.children);
}
private static String createIndent(int depth) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) {
sb.append(' ');
}
return sb.toString();
}
public static TreeNode<String> getSetA() {
TreeNode<String> A = new TreeNode<String>("A");
{
TreeNode<String> B = A.addChild("B");
TreeNode<String> C = A.addChild("C");
TreeNode<String> D = A.addChild("D");
{
TreeNode<String> E = B.addChild("E");
TreeNode<String> F = C.addChild("F");
TreeNode<String> G = C.addChild("G");
{
TreeNode<String> H = F.addChild("H");
TreeNode<String> I = F.addChild("I");
TreeNode<String> J = F.addChild("J");
}
}
}
return A;
}
}
- вывод
********************测试遍历*************************
A
B
E
C
F
H
I
J
G
D
********************测试搜索*************************
F: parent=C,children=[H, I, J]
Суммировать
В этом разделе я познакомлю вас с важной структурой данных дерева, объясню концепции и термины, связанные с деревом, и, наконец, реализую основные операции с деревом для всех.
Изучив содержание этого раздела, вы познакомитесь с бинарным деревом, которое мы представим далее, а также с Java.TreeSetиTreeMapИсточник, поможет.