|
Arabic
Bengali
Chinese
English
French
German
Hebrew
Hindi
Italian
Japanese
Korean
Malay
Polish
Portuguese
Spanish
Turkish
Ukrainian
Vietnamese|
RESUMO DA AULA, CRIBS
Информатика и информационные технологии. Графы (конспект лекций)
Diretório / Notas de aula, folhas de dicas Índice (expandir) PALESTRA No. 9. Estruturas de dados em forma de árvore 1. Estruturas de Dados em Árvore Uma estrutura de dados em forma de árvore é um conjunto finito de elementos-nós entre os quais existem relações - a conexão entre a fonte e o gerado. Se usarmos a definição recursiva proposta por N. Wirth, então uma estrutura de dados de árvore com tipo base t é uma estrutura vazia ou um nó do tipo t, com o qual um conjunto finito de estruturas de árvore com tipo base t, chamado subárvores, é associado. A seguir, damos as definições usadas ao operar com estruturas em árvore. Se o nó y estiver localizado diretamente abaixo do nó x, então o nó y é chamado de descendente imediato do nó x, e x é o ancestral imediato do nó y, ou seja, se o nó x está no i-ésimo nível, então o nó y é correspondentemente localizado em (i + 1) - o nível. O nível máximo de um nó de árvore é chamado de altura ou profundidade da árvore. Um ancestral não possui apenas um nó da árvore - sua raiz. Os nós de árvore que não têm filhos são chamados de nós de folha (ou folhas de árvore). Todos os outros nós são chamados de nós internos. O número de filhos imediatos de um nó determina o grau desse nó, e o grau máximo possível de um nó em uma determinada árvore determina o grau da árvore. Ancestrais e descendentes não podem ser intercambiados, ou seja, a conexão entre o original e o gerado atua apenas em uma direção. Se você for da raiz da árvore para algum nó específico, o número de ramos da árvore que serão percorridos nesse caso é chamado de comprimento do caminho para esse nó. Se todos os ramos (nós) de uma árvore são ordenados, então a árvore é dita ordenada. Árvores binárias são um caso especial de estruturas de árvore. São árvores em que cada filho tem no máximo dois filhos, chamados de subárvores esquerda e direita. Assim, uma árvore binária é uma estrutura de árvore cujo grau é dois. A ordenação de uma árvore binária é determinada pela seguinte regra: cada nó tem seu próprio campo de chave, e para cada nó o valor da chave é maior que todas as chaves em sua subárvore esquerda e menor que todas as chaves em sua subárvore direita. Uma árvore cujo grau é maior que dois é chamada fortemente ramificada. 2. Operações em árvores Além disso, consideraremos todas as operações em relação às árvores binárias. I. Construção de árvores Apresentamos um algoritmo para construir uma árvore ordenada. 1. Se a árvore estiver vazia, os dados serão transferidos para a raiz da árvore. Se a árvore não estiver vazia, um de seus ramos desce de tal forma que a ordem da árvore não seja violada. Como resultado, o novo nó se torna a próxima folha da árvore. 2. Para adicionar um nó a uma árvore já existente, você pode usar o algoritmo acima. 3. Ao excluir um nó da árvore, você deve ter cuidado. Se o nó a ser removido for uma folha ou tiver apenas um filho, a operação é simples. Se o nó a ser excluído tiver dois descendentes, será necessário encontrar um nó entre seus descendentes que possa ser colocado em seu lugar. Isso é necessário devido à exigência de que a árvore seja encomendada. Você pode fazer isso: troque o nó a ser removido pelo nó com o maior valor de chave na subárvore esquerda ou com o nó com o menor valor de chave na subárvore direita e exclua o nó desejado como uma folha. II. Localizando um nó com um determinado valor de campo-chave Ao realizar esta operação, é necessário percorrer a árvore. É necessário levar em conta as diferentes formas de escrever uma árvore: prefixo, infixo e pós-fixo. Surge a pergunta: como representar os nós da árvore para que seja mais conveniente trabalhar com eles? É possível representar uma árvore usando um array, onde cada nó é descrito por um valor do tipo combinado, que possui um campo de informação do tipo caractere e dois campos do tipo referência. Mas isso não é muito conveniente, pois as árvores possuem um grande número de nós que não são pré-determinados. Portanto, é melhor usar variáveis dinâmicas ao descrever uma árvore. Em seguida, cada nó é representado por um valor do mesmo tipo, que contém uma descrição de um determinado número de campos de informação, e o número de campos correspondentes deve ser igual ao grau da árvore. É lógico determinar a ausência de descendentes com zero. Então, em Pascal, a descrição de uma árvore binária pode ser assim: TIPO TreeLink = ^Árvore; árvore = registro; Inf: <tipo de dados>; Esquerda, Direita: TreeLink; End. 3. Exemplos de implementação de operações 1. Construa uma árvore de n nós de altura mínima, ou uma árvore perfeitamente balanceada (o número de nós das subárvores esquerda e direita de tal árvore não deve diferir em mais de um). Algoritmo de construção recursiva: 1) o primeiro nó é tomado como a raiz da árvore. 2) a subárvore esquerda de nl nós é construída da mesma maneira. 3) a subárvore direita de nr nós é construída da mesma maneira; nr = n - nl - 1. Como campo de informação, tomaremos os números dos nós digitados no teclado. A função recursiva que implementa essa construção ficará assim: Árvore de Funções(n : Byte): TreeLink; Vart : TreeLink; nl,nr,x : Byte; Começar Se n = 0 então Árvore := nil Outro Começar nl := n div 2; nr = n - nl - 1; writeln('Digite o número do vértice '); leia(x); novo(t); t^.inf := x; t^.left := Árvore(nl); t^.right := Árvore(nr); Árvore := t; End; {Árvore} End. 2. Na árvore ordenada binária, encontre o nó com o valor dado do campo-chave. Se não houver tal elemento na árvore, adicione-o à árvore. Procedimento de pesquisa(x : Byte; var t : TreeLink); Começar Se t = zero então Começar Novo(t); t^inf := x; t^.esquerda := nil; t^.certo := nil; Terminar Senão se x < t^.inf então Pesquisar(x, t^.esquerda) Caso contrário, se x > t^.inf então Pesquisar(x, t^.direita) Outro Começar {processo encontrado elemento} ... End; End. 3. Escreva os procedimentos de travessia da árvore em ordem direta, simétrica e reversa, respectivamente. 3.1. Procedimento Pré-encomenda(t : TreeLink); Começar Se t <> nulo então Começar WriteIn(t^.inf); Pré-encomenda(t^.left); Pré-encomenda(t^.right); End; End; 3.2. Procedimento Inorder(t : TreeLink); Começar Se t <> nulo então Começar Inorder(t^.esquerda); WriteIn(t^.inf); Inordem(t^.direita); End; End. 3.3. Pós-ordem do procedimento(t : TreeLink); Começar Se t <> nulo então Começar postorder(t^.left); postorder(t^.right); WriteIn(t^.inf); End; End. 4. Na árvore ordenada binária, exclua o nó com o valor fornecido do campo-chave. Vamos descrever um procedimento recursivo que levará em conta a presença do elemento requerido na árvore e o número de descendentes deste nó. Se o nó a ser excluído tiver dois filhos, ele será substituído pelo maior valor de chave em sua subárvore esquerda e só então será excluído permanentemente. Procedimento Delete1(x : Byte; var t : TreeLink); Var p : TreeLink; Procedimento Delete2(var q : TreeLink); Começar Se q^.right <> nil então Delete2(q^.right) Outro Começar p^.inf := q^.inf; p:= q; q := q^.esquerda; End; End; Começar Se t = zero então Writeln('nenhum elemento encontrado') Senão se x < t^.inf então Delete1(x, t^.esquerda) Caso contrário, se x > t^.inf então Excluir1(x, t^.direita) Outro Começar P:= t; Se p^.left = nil então t := p^.direita Outro Se p^.right = nil então t := p^.esquerda Outro Delete2(p^.esquerda); End; End. Autor: Tsvetkova A.V. << Voltar: Estruturas de dados em árvore (Estruturas de dados em árvore. Operações em árvores. Exemplos de implementação de operações) >> Encaminhar: Tipo de dados do objeto (Tipo de objeto em Pascal. O conceito de objeto, sua descrição e uso. Herança. Criação de instâncias de objetos. Componentes e escopo)
▪ Resumo das obras da literatura russa da primeira metade do século XX ▪ Direito executivo penal. Notas de aula ▪ Finanças estaduais e municipais. Notas de aula
A existência de uma regra de entropia para o emaranhamento quântico foi comprovada
09.05.2024 Mini ar condicionado Sony Reon Pocket 5
09.05.2024 Energia do espaço para Starship
08.05.2024
▪ Caixa de som sem fio Beosound Balance ▪ Cílios artificiais controlados por ímã e luz ▪ Ondas gravitacionais podem ajudar a prever tsunamis ▪ Telas E Ink Mobius para smartwatches ▪ Novas e silenciosas estações de trabalho Fujitsu Celsius
▪ seção do site Comunicação móvel. Seleção de artigos ▪ artigo Caixa longa. expressão popular ▪ artigo O cacto tem muita água? Resposta detalhada ▪ artigo Maquinista de bombas de pó. Instrução padrão sobre proteção do trabalho ▪ artigo Microfone de rádio com antena de loop. Enciclopédia de rádio eletrônica e engenharia elétrica
Página principal | Biblioteca | Artigos | Mapa do Site | Revisões do site
www.diagrama.com.ua |
Recomendamos artigos interessantes seção 
Veja outros artigos seção 
Últimas notícias de ciência e tecnologia, nova eletrônica:
Todos os idiomas desta página