Слияние кода завершено, страница обновится автоматически
Двоичное дерево — это структура дерева, в которой каждый узел имеет не более двух поддеревьев. Обычно эти поддеревья называются «левое поддерево» (left subtree) и «правое поддерево» (right subtree). Двоичные деревья часто используются для реализации двоичных деревьев поиска и двоичных куч.
В двоичном дереве у каждого узла есть максимум два поддерева (не существует узлов со степенью больше 2), двоичное дерево имеет разделение на левое и правое поддеревья, порядок нельзя изменить. В двоичном дереве i-го уровня не более 2^(i-1) узлов; в двоичном дереве глубины k не более 2^k-1 узлов; для любого двоичного дерева T, если количество его конечных узлов равно n_0, а количество узлов степени 2 равно n_2, то n_0 = n_2 + 1.
Дерево глубины k с 2^k-1 узлами называется полным двоичным деревом; дерево глубины k с n узлами является полным двоичным деревом только тогда, когда каждый его узел соответствует узлу полного двоичного дерева глубины k с номерами от 1 до n.
//arrs - массив данных, которые будут помещены в узлы дерева, demo будет содержать данные типа int, помещённые в узлы
public List<TreeNode> initTree(int[] arrs) {
List<TreeNode> nodes = new ArrayList<TreeNode>();
for (int data : arrs) {
nodes.add(new TreeNode(data));
}
// Здесь каждый родительский узел имеет индекс < (arrs.length / 2 - 1), что гарантирует наличие левого и правого дочерних узлов для каждого родительского узла
for (int parentIndex = 0; parentIndex < arrs.length / 2 - 1; parentIndex++) {
nodes.get(parentIndex).leftNode = nodes.get(parentIndex * 2 + 1);
nodes.get(parentIndex).rightNode = nodes.get(parentIndex * 2 + 2);
}
// (arrs.length / 2 - 1) - последний родительский узел, согласно определению двоичного дерева
int lastParentIndex = arrs.length / 2 - 1;
nodes.get(lastParentIndex).leftNode = nodes.get(lastParentIndex * 2 + 1);
// Если arrs.length % 2 != 0, используется для определения, существует ли правый дочерний узел последнего родительского узла
if(arrs.length % 2 != 0){
nodes.get(lastParentIndex).rightNode = nodes.get(lastParentIndex * 2 + 2);
}
return nodes;
}
Объект TreeNode, упомянутый в методе выше, можно найти в коде (src.test.TreeNode).
(1). Прямой обход: «корень, левый, правый».
(2). Симметричный обход: «левый, корень, правый».
(3). Обратный обход: «левый, правый, корень».
Три способа обхода отличаются порядком обхода.
Прямой обход: корень → левый узел → правый узел.
Симметричный обход: левый узел → корень → правый узел.
Обратный обход: левый узел → правый узел → корень.
Использование рекурсии:
/*
* Прямой обход двоичного дерева: корень, левый, правый
*
* @param node
* Обход узла
* */
public void preOrderTraverse(TreeNode node){
if(node == null)
return;
System.out.print(node.data + " "); // Первый вход - это rootNode
preOrderTraverse(node.leftNode); // Рекурсивный вывод левого узла
preOrderTraverse(node.rightNode); // Рекурсивный вывод правого узла
}
Использование цикла:
/*
* Прямой обход двоичного дерева: корень, левый, правый
*
* Использование цикла
*
* @param node
* Узел обхода
* */
public void preOrderTraverseByWhile(TreeNode node){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(node);
TreeNode currentNode;
while (!stack.isEmpty()) {
currentNode = stack.pop();
System.out.print(currentNode.data + " ");
if(currentNode.rightNode != null){
stack.push(currentNode.rightNode);
}
if (currentNode.leftNode != null) {
stack.push(currentNode.leftNode);
}
}
}
Использование рекурсии:
/*
* Симметричный обход двоичного дерева: левый, корень, правый
*
* @param node
* Обход узла
* */
public void inOrderTraverse(TreeNode node){
if(node == null)
return;
inOrderTraverse(node.leftNode); // Рекурсивный вывод левого узла
System.out.print(node.data + " ");
inOrderTraverse(node.rightNode); // Рекурсивный вывод правого узла
}
Использование цикла:
/*
* Симметричный обход двоичного дерева: левый, корень, правый
*
* Использование цикла
*
* @param node
* Узел обхода
* */
public void inOrderTraverseByWhile(TreeNode node){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = node;
while (currentNode != null || !stack.isEmpty()) {
while(currentNode != null){
stack.push(currentNode);
currentNode = currentNode.leftNode;
}
if(!stack.isEmpty()){
currentNode = stack.pop();
System.out.print(currentNode.data + "");
currentNode = currentNode.rightNode;
}
}
}
Использование рекурсии:
/*
* Обратный обход двоичного дерева: левый, правый, корень
*
* @param node
* Обход узла
* */
public void afterOrderTraverse(TreeNode node){
if(node == null)
return;
afterOrderTraverse(node.leftNode);// Рекурсивный вывод левого узла
afterOrderTraverse(node.rightNode);// Рекурсивный вывод правого узла
System.out.print(node.data + " ");
}
Использование цикла:
/*
* Обратный обход двоичного дерева: левый, правый, корень
* */
public void afterOrderTraverseByWhile(TreeNode node){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = node;
while (currentNode != null || !stack.isEmpty()) {
while(currentNode != null){
stack.push(currentNode);
currentNode = currentNode.leftNode;
}
if(!stack.isEmpty()){
currentNode = stack.pop();
System.out.print(currentNode.data + "");
currentNode = currentNode.rightNode;
}
}
} ```
* Использование цикла
*/
public void afterOrderTraverseByWhile(TreeNode node){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode rightNode = null;
TreeNode currentNode = node;
while (currentNode != null || !stack.isEmpty()) {
while(currentNode != null){
stack.push(currentNode);
currentNode = currentNode.leftNode;
}
currentNode = stack.pop();
//когда предыдущий посещённый узел является правым потомком или текущий узел не имеет правого потомка, тогда посещаем текущий узел
while(currentNode != null && (currentNode.rightNode == null || currentNode.rightNode == rightNode)){
System.out.print(currentNode.data + " ");
rightNode = currentNode;
if(stack.isEmpty()){
return;
}
currentNode = stack.pop();
}
stack.push(currentNode);
currentNode = currentNode.rightNode;
}
}
Структура бинарного дерева, заданная в demo:
Результат RunTest:
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Комментарии ( 0 )