329 lines
8.4 KiB
Markdown
329 lines
8.4 KiB
Markdown
---
|
|
id: 587d8257367417b2b2512c7e
|
|
title: Usar busca em profundidade em uma árvore binária de busca
|
|
challengeType: 1
|
|
forumTopicId: 301719
|
|
dashedName: use-depth-first-search-in-a-binary-search-tree
|
|
---
|
|
|
|
# --description--
|
|
|
|
Sabemos como procurar por um valor específico em uma árvore binária. Mas e se quisermos pesquisar a árvore inteira? E se não tivermos uma árvore ordenada e precisarmos simplesmente pesquisar por um valor? Aqui, vamos introduzir alguns métodos de travessia que podem ser usados para pesquisar essa estrutura de dados. O primeiro método será a busca em profundidade. Na busca em profundidade, uma determinada subárvore é pesquisada o mais profundamente possível antes da busca continuar para outra subárvore. Podemos realizar essa busca de três formas: Em ordem: começa a pesquisa no nó mais à esquerda e termina no nó mais à direita. Pré-ordem: pesquisa todas as raízes antes das folhas. Pós-ordem: pesquisa todas as folhas antes das raízes. Como você pode imaginar, você pode escolher métodos de busca diferentes, dependendo dos dados que sua árvore armazena e do que você está procurando. Em uma árvore binária de busca, uma travessia de ordem retorna os nós de forma ordenada.
|
|
|
|
# --instructions--
|
|
|
|
Aqui, vamos usar estes três métodos de pesquisa na nossa árvore binária de busca. A busca em profundidade é uma operação inerentemente recursiva que continua a pesquisar mais subárvores enquanto existirem nós filhos. Uma vez que você entende este conceito básico, você pode simplesmente reorganizar a ordem da pesquisa nos nós e nas subárvores para produzir qualquer uma das três buscas. Por exemplo, na busca de pós-ordem, a pesquisa deve, recursivamente, ir até o nó da folha antes de retornar qualquer um dos nós em si. Por outro lado, na busca de pré-ordem, a pesquisa deve retornar os nós primeiro e depois continuar a pesquisa pela árvore. Use os métodos em ordem (`inorder`), pré-ordem (`preorder`) e pós-ordem (`postorder`) na nossa árvore. Cada um desses métodos deve retornar um array de itens que representa a travessia da árvore. Certifique-se de retornar os valores numéricos em cada nó do array, não os nós em si. Por fim, retorne `null` se a árvore estiver vazia.
|
|
|
|
# --hints--
|
|
|
|
A estrutura de dados `BinarySearchTree` deve existir.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
}
|
|
return typeof test == 'object';
|
|
})()
|
|
);
|
|
```
|
|
|
|
A árvore binária de busca deve ter um método chamado `inorder`.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
return typeof test.inorder == 'function';
|
|
})()
|
|
);
|
|
```
|
|
|
|
A árvore binária de busca deve ter um método chamado `preorder`.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
return typeof test.preorder == 'function';
|
|
})()
|
|
);
|
|
```
|
|
|
|
A árvore binária de busca deve ter um método chamado `postorder`.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
return typeof test.postorder == 'function';
|
|
})()
|
|
);
|
|
```
|
|
|
|
O método `inorder` deve retornar um array com os valores de cada nó.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.inorder !== 'function') {
|
|
return false;
|
|
}
|
|
test.add(7);
|
|
test.add(1);
|
|
test.add(9);
|
|
test.add(0);
|
|
test.add(3);
|
|
test.add(8);
|
|
test.add(10);
|
|
test.add(2);
|
|
test.add(5);
|
|
test.add(4);
|
|
test.add(6);
|
|
return test.inorder().join('') == '012345678910';
|
|
})()
|
|
);
|
|
```
|
|
|
|
O método `preorder` deve retornar um array com os valores de cada nó.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.preorder !== 'function') {
|
|
return false;
|
|
}
|
|
test.add(7);
|
|
test.add(1);
|
|
test.add(9);
|
|
test.add(0);
|
|
test.add(3);
|
|
test.add(8);
|
|
test.add(10);
|
|
test.add(2);
|
|
test.add(5);
|
|
test.add(4);
|
|
test.add(6);
|
|
return test.preorder().join('') == '710325469810';
|
|
})()
|
|
);
|
|
```
|
|
|
|
O método `postorder` deve retornar um array com os valores de cada nó.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.postorder !== 'function') {
|
|
return false;
|
|
}
|
|
test.add(7);
|
|
test.add(1);
|
|
test.add(9);
|
|
test.add(0);
|
|
test.add(3);
|
|
test.add(8);
|
|
test.add(10);
|
|
test.add(2);
|
|
test.add(5);
|
|
test.add(4);
|
|
test.add(6);
|
|
return test.postorder().join('') == '024653181097';
|
|
})()
|
|
);
|
|
```
|
|
|
|
O método `inorder` deve retornar `null` quando a árvore estiver vazia.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.inorder !== 'function') {
|
|
return false;
|
|
}
|
|
return test.inorder() == null;
|
|
})()
|
|
);
|
|
```
|
|
|
|
O método `preorder` deve retornar `null` quando a árvore estiver vazia.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.preorder !== 'function') {
|
|
return false;
|
|
}
|
|
return test.preorder() == null;
|
|
})()
|
|
);
|
|
```
|
|
|
|
O método `postorder` deve retornar `null` quando a árvore estiver vazia.
|
|
|
|
```js
|
|
assert(
|
|
(function () {
|
|
var test = false;
|
|
if (typeof BinarySearchTree !== 'undefined') {
|
|
test = new BinarySearchTree();
|
|
} else {
|
|
return false;
|
|
}
|
|
if (typeof test.postorder !== 'function') {
|
|
return false;
|
|
}
|
|
return test.postorder() == null;
|
|
})()
|
|
);
|
|
```
|
|
|
|
# --seed--
|
|
|
|
## --after-user-code--
|
|
|
|
```js
|
|
BinarySearchTree.prototype = Object.assign(
|
|
BinarySearchTree.prototype,
|
|
{
|
|
add: function(value) {
|
|
function searchTree(node) {
|
|
if (value < node.value) {
|
|
if (node.left == null) {
|
|
node.left = new Node(value);
|
|
return;
|
|
} else if (node.left != null) {
|
|
return searchTree(node.left);
|
|
}
|
|
} else if (value > node.value) {
|
|
if (node.right == null) {
|
|
node.right = new Node(value);
|
|
return;
|
|
} else if (node.right != null) {
|
|
return searchTree(node.right);
|
|
}
|
|
} else {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
var node = this.root;
|
|
if (node == null) {
|
|
this.root = new Node(value);
|
|
return;
|
|
} else {
|
|
return searchTree(node);
|
|
}
|
|
}
|
|
}
|
|
);
|
|
```
|
|
|
|
## --seed-contents--
|
|
|
|
```js
|
|
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
|
|
function Node(value) {
|
|
this.value = value;
|
|
this.left = null;
|
|
this.right = null;
|
|
}
|
|
function BinarySearchTree() {
|
|
this.root = null;
|
|
// Only change code below this line
|
|
|
|
// Only change code above this line
|
|
}
|
|
```
|
|
|
|
# --solutions--
|
|
|
|
```js
|
|
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
|
|
function Node(value) {
|
|
this.value = value;
|
|
this.left = null;
|
|
this.right = null;
|
|
}
|
|
function BinarySearchTree() {
|
|
this.root = null;
|
|
this.result = [];
|
|
|
|
this.inorder = function(node) {
|
|
if (!node) node = this.root;
|
|
if (!node) return null;
|
|
|
|
if (node.left) this.inorder(node.left);
|
|
this.result.push(node.value);
|
|
if (node.right) this.inorder(node.right);
|
|
return this.result;
|
|
};
|
|
this.preorder = function(node) {
|
|
if (!node) node = this.root;
|
|
if (!node) return null;
|
|
|
|
this.result.push(node.value);
|
|
if (node.left) this.preorder(node.left);
|
|
if (node.right) this.preorder(node.right);
|
|
return this.result;
|
|
};
|
|
this.postorder = function(node) {
|
|
if (!node) node = this.root;
|
|
if (!node) return null;
|
|
|
|
if (node.left) this.postorder(node.left);
|
|
if (node.right) this.postorder(node.right);
|
|
this.result.push(node.value);
|
|
|
|
return this.result;
|
|
};
|
|
}
|
|
```
|