Эта статья является оригинальной работой и впервые была опубликована в публичном аккаунте WeChat: [Г-н Сакамото]. Если вам нужно ее перепечатать, укажите «Перепечатано в публичном аккаунте WeChat: [Г-н Сакамото]» в начале статьи, в противном случае вы будете нести юридическую ответственность.
Адрес статьи WeChat:Фактический боевой алгоритм - полный обход дерева с несколькими ветвями
предисловие
В этой статье изучается, как пройти полный путь дерева с несколькими ветками и вывести результат полного пути. Изучение этой проблемы может быть использовано в задаче просмотра всех значений словаря в дереве Trie. В этой статье будет подробно смоделирована проблема и реализован код, обсуждены преимущества и недостатки рекурсивных и нерекурсивных методов и их реализация соответственно.Если читатели не заинтересованы в преимуществах и недостатках этих двух методов, они могут сразу перейти кпроблемное зданиеглава для чтения. Статья длинная, рекомендую сначала собрать, а потом читать.
Каталог статей
Рекурсивное и нерекурсивное сравнение
На Quora уже есть много ответов на этот вопрос (Ууху. Call.com/question/20…
рекурсия
Проблема разбивается на несколько относительно небольших проблем, и встречается рекурсивный выход, а затем возвращается к исходному пути.Поэтому соответствующие промежуточные значения должны быть сохранены.Эти промежуточные значения помещаются в стек для хранения.Когда задача большая, она займет много памяти.
нерекурсивный
Эффективность выполнения высока, а время работы увеличивается только за счет увеличения количества циклов, и нет дополнительных накладных расходов. Нет увеличения площади
Недостатки и преимущества рекурсии
Недостатки рекурсии
-
Рекурсия подвержена ошибкам "переполнения стека". Рекурсия очень интенсивно использует память, потому что тысячи или сотни записей вызовов должны быть сохранены одновременно.
-
С точки зрения эффективности рекурсия может иметь избыточные вычисления. Использование рекурсии будет иметьизбыточное вычисление(Например, наиболее типична последовательность Фибоначчи. Для вычисления 6-го нужно вычислить 4-е и 5-е, а для вычисления 5-го нужно вычислить 4-е, и расположение будет повторяться). Итерация имеет в этом отношении абсолютное преимущество.
Преимущества рекурсии
Рекурсия имеет лучшую читаемость кода, а для операций с небольшим объемом данных рекурсивных алгоритмов более чем достаточно.
проблемное здание
Теперь есть дерево с несколькими ответвлениями, и его узлы такие, как показано на рисунке ниже, и необходимо указать метод для вывода всех путей конечных узлов.
Окончательный вывод должен иметь 5, а именно [rad, rac, rbe, rbf, rg]
проблема решена
Сначала мы анализируем узлы и строим класс узла (TreeNode), а затем нам нужен класс дерева (MultiTree), который содержит метод печати полного пути. Наконец, нам нужно создать метод Main для тестирования. Окончательная структура проекта выглядит следующим образом:
Примечание. В этой статье используется аннотация lombok без реализации методов get, set и связанных с ними. Если читатели не использовали ломбок, они также могут написать соответствующие методы get и set самостоятельно.В следующих разделах объясняются методы, которые необходимо реализовать для каждого класса, что не влияет на основной код.
Класс TreeNode
Класс узла, в основном, содержит два поля:
- контент: используется для хранения контента, сохраненного текущим узлом
- дочерние элементы: используется для хранения информации о дочерних узлах, строка HashMap хранит содержимое дочерних узлов, а реализация дочерних элементов с использованием HashMap способствует быстрому поиску дочерних узлов.
Этот класс содержит необходимые методы get, set, конструктор без аргументов и конструктор с полными параметрами.
@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
private String content;
private HashMap<String,TreeNode> childs;
}
Класс MultiTree
Включены только два поля:
- root: root.
- pathList: используется для хранения пути, полученного в процессе обхода
В конструкторе этого класса я вручную создаю рассматриваемую конструкцию дерева, и соответствующий код выглядит следующим образом:
public MultiTree(){
//创建根节点
HashMap rootChilds = new HashMap();
this.root = new TreeNode("r",rootChilds);
//第一层子节点
HashMap aChilds = new HashMap();
TreeNode aNode = new TreeNode("a",aChilds);
HashMap bChilds = new HashMap();
TreeNode bNode = new TreeNode("b",bChilds);
HashMap gChilds = new HashMap();
TreeNode gNode = new TreeNode("g",gChilds);
//第二层结点
HashMap dChilds = new HashMap();
TreeNode dNode = new TreeNode("d",dChilds);
HashMap cChilds = new HashMap();
TreeNode cNode = new TreeNode("c",cChilds);
HashMap eChilds = new HashMap();
TreeNode eNode = new TreeNode("e",eChilds);
HashMap fChilds = new HashMap();
TreeNode fNode = new TreeNode("f",fChilds);
//建立结点联系
rootChilds.put("a",aNode);
rootChilds.put("b",bNode);
rootChilds.put("g",gNode);
aChilds.put("d",dNode);
aChilds.put("c",cNode);
bChilds.put("e",eNode);
bChilds.put("f",fNode);
}
В этом дереве у каждого узла есть потомки,Если это листовой узел, размер в дочерних элементах равен 0., что является важной основой для определения того, является ли узел листовым узлом или нет.Далее мы реализуем основной код алгоритма.
Основной класс
public class Main {
public static void main(String[] args) {
MultiTree tree = new MultiTree();
List<String> path1 = tree.listAllPathByRecursion();
System.out.println(path1);
List<String> path2 = tree.listAllPathByNotRecursion();
System.out.println(path2);
}
}
рекурсивный метод
Необходимо улучшить метод listAllPathByRecursion и метод listPath в классе MultiTree.
Метод рекурсивного процесса: listAllPathByRecursion
Схема алгоритма выглядит следующим образом:
Код реализован следующим образом:
public void listPath(TreeNode root,String path){
if(root.getChilds().isEmpty()){//叶子节点
path = path + root.getContent();
pathList.add(path); //将结果保存在list中
return;
}else{ //非叶子节点
path = path + root.getContent() + "->";
//进行子节点的递归
HashMap<String, TreeNode> childs = root.getChilds();
Iterator iterator = childs.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry entry = (Map.Entry)iterator.next();
TreeNode childNode = (TreeNode) entry.getValue();
listPath(childNode,path);
}
}
}
Метод рекурсивного вызова: listAllPathByRecursion
public List<String> listAllPathByRecursion(){
//清空路径容器
this.pathList.clear();
listPath(this.root,"");
return this.pathList;
}
нерекурсивный метод
По сравнению с рекурсивным методом объем кода нерекурсивного метода просто слишком велик, а его содержание нелегко понять. Я не знаю, сможете ли вы понять код, который я написал. Я старался изо всех сил, чтобы пишите соответствующие комментарии.
Сначала устанавливаются два стека.Схема выглядит следующим образом.Реализация стека использует Deque.Необходимо обратить внимание на ситуацию с нулевым указателем в коде.
-
Основной стек: используется для обработки хранения узлов и временных путей.Когда основной стек пуст, это означает, что узел был обработан.
-
Вторичный стек: используется для хранения ожидающих узлов.Когда вторичный стек пуст, это означает, что обход узла завершен.
Введение других связанных переменных:
- popCount : используется для хранения количества всплывающих окон дочерних узлов узла. Например, у r есть дочерние узлы 3. Если количество всплывающих окон, соответствующих r, равно 3, это означает, что листовые узлы r обработаны, и r может быть всплывающим. Потому что после извлечения r в основном стеке нет элементов, поэтому обработка завершена.
- curString: используется для хранения временного пути. Когда изменяется основной элемент стека, curString также изменяется. Например, curString на приведенном выше рисунке — «r->g->». Когда верхний элемент стека извлекается, " g->" необходимо вычесть. Если верхний элемент стека является листовым узлом, это означает, что путь был пройден и его необходимо добавить в контейнер пути пути.
Схема программы:
Конкретный код реализации выглядит следующим образом:
/**
* 非递归方法输出所有路径
*/
public List<String> listAllPathByNotRecursion(){
//清空路径容器
this.pathList.clear();
//主栈，用于计算处理路径
Deque<TreeNode> majorStack = new ArrayDeque();
//副栈，用于存储待处理节点
Deque<TreeNode> minorStack = new ArrayDeque();
minorStack.addLast(this.root);
HashMap<String,Integer> popCount = new HashMap<>();
String curString = "";
while(!minorStack.isEmpty()){
//出副栈，入主栈
TreeNode minLast = minorStack.pollLast();
majorStack.addLast(minLast);
curString+=minLast.getContent()+"->";
//将该节点的子节点入副栈
if(!minLast.getChilds().isEmpty()){
HashMap<String, TreeNode> childs = minLast.getChilds();
Iterator iterator = childs.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry entry = (Map.Entry)iterator.next();
TreeNode childNode = (TreeNode) entry.getValue();
minorStack.addLast(childNode);
}
}
//出主栈
TreeNode majLast = majorStack.peekLast();
//循环条件：栈顶为叶子节点 或 栈顶节点孩子节点遍历完了（需要注意空指针问题）
while(majLast.getChilds().size() ==0 ||
(popCount.get(majLast.getContent())!=null && popCount.get(majLast.getContent()).equals(majLast.getChilds().size()))){
TreeNode last = majorStack.pollLast();
majLast = majorStack.peekLast();
if(majLast == null){ //此时主栈为空，运算完毕
return this.pathList;
}
if(popCount.get(majLast.getContent())==null){//第一次弹出孩子节点，弹出次数设为1
popCount.put(majLast.getContent(),1);
}else{ //非第一次弹出孩子节点，在原有基础上加1
popCount.put(majLast.getContent(),popCount.get(majLast.getContent())+1);
}
String lastContent = last.getContent();
if(last.getChilds().isEmpty()){//如果是叶子节点才将结果加入路径集中
this.pathList.add(curString.substring(0,curString.length()-2));
}
//调整当前curString，减去2是减的“->”这个符号
curString = curString.substring(0,curString.length()-lastContent.length()-2);
}
}
return this.pathList;
}
контрольная работа
Вызов основного метода в классе Main и получение результата выполнения, который совпадает с ожидаемым результатом, и код проходит проверку
listAllPathByRecursion[r->a->c, r->a->d, r->b->e, r->b->f, r->g]
listAllPathByNotRecursion[r->g, r->b->f, r->b->e, r->a->d, r->a->c]
в заключении
Фактически, эта статья является промежуточным продуктом моего исследования «внедрения чувствительного алгоритма фильтрации слова на основе Trie Tree». На самом деле, он должен также реализовать проблему обхода пути чрезмерных вилков, но из-за причин времени и оригинала Отсутствие лучшей системы управления знаниями, код и заметки теряются, и сегодня я возьму возможность сделать еще одно резюме. Надеюсь, что эта статья может помочь тем, кто это нужно.