Classificação de árvores binárias (por estrutura de armazenamento)
Classificação de árvores (por estrutura de armazenamento)
Armazenamento seqüencial (representado por matrizes (árvore binária estática))
Armazenamento em cadeia
Algumas raízes binárias especiais:
Árvore binária completa, árvore binária equilibrada (AVL), árvore binária da pista, Tri-Fork (ponteiro com pai)
Árvore de pesquisa binária ou árvore de pesquisa binária (BST)
A árvore binária usada é mostrada na figura a seguir:
Implementação de Java da árvore binária (estrutura de armazenamento em cadeia)
classe Treenode {private int key = 0; Dados de sequência privada = null; private boolean isvisted = false; Treenode privado esquerdfild = null; Treenode privado RightChild = NULL; public Treenode () {} public Treenode (tecla int, dados da string) {this.key = key; this.data = dados; this.leftchild = null; this.rightChild = null; } public int getKey () {return Key; } public void setKey (int key) {this.key = key; } public string getData () {return data; } public void setData (dados da string) {this.data = data; } public Treenode getLeftchild () {return leffertchild; } public void SetLeftChild (Treenode LeftChild) {this.leftchild = leftChild; } public Treenode getRightChild () {return RightChild; } public void SetrightChild (Treenode RightChild) {this.rightChild = RightChild; } public boolean isvisted () {return isvisted; } public void setvisted (boolean isvisted) {this.isvisted = isvisted; }} classe pública binarytree {private Treenode root = null; public binarytree () {root = new Treenode (1, "rootnode (a)"); } public void CreateBintree (raiz Treenode) {// criação manual (a estrutura é mostrada na figura) Treenode newNodeB = new Treenode (2, "B"); Treenode newnodec = new Treenode (3, "C"); Treenode newNODED = new Treenode (4, "D"); Treenode newnodee = new Treenode (5, "E"); Treenode newNodef = new Treenode (6, "F"); root.setLeftChild (newNodeB); root.setrightChild (newnodec); root.getLeftChild (). SetleftChild (newnoded); root.getLeftChild (). SetrightChild (newnodee); root.getrightChild (). SetrightChild (newNodeF); } public boolean isEmpty () {// Determine se a árvore binária está vazia ou não retorna root == null; } public int Hight () {// Encontre a altura da altura da árvore altura de retorno (raiz); } public int Hight (subtree Treenode) {if (subtree == null) retornar 0; // Fim recursivo: a altura da árvore vazia é 0 mais {int i = altura (subtree.getLeftChild ()); int j = altura (subtree.getrightchild ()); retornar (i <j)? j + 1: i + 1; }} public int size () {// Encontre o número de nós de retorno de nós (root); } public int size (subtree Treenode) {if (subtree == null) retorna 0; else {return 1 + size (subtree.getleftchild ()) + size (subtree.getrightChild ()); }} public Treenode Parent (elemento Treenode) {// retorna o nó pai retorno (root == null || root == elemento)? nulo: pai (raiz, elemento); } public Treenode Parent (subárvore Treenode, elemento Treenode) {if (subtree == null) retorna null; if (subtree.getLeftChild () == element || subtree.getrightChild () == element) // termina, retorne o endereço do nó pai subtree; Treenode p; // Primeiro olhar na subárvore esquerda. Se não for encontrado na subárvore esquerda, vá para a subárvore direita para descobrir se ((p = pai (subtree.getleftChild (), elemento))! = Null) // pesquise recursivamente pelo retorno p; else // pesquisar recursivamente por Return Parent (subtree.getrightChild (), elemento); } public Treenode LeftChild (elemento Treenode) {// Retorna a subárvore esquerda Return (Element! = NULL)? element.getLeftChild (): null; } public Treenode RightChild (elemento Treenode) {// Retorna a subárvore direita Return (Element! = NULL)? element.getrightChild (): null; } public Treenode getRoot () {// Obtenha o nó raiz RETROT ROOT; } public void Destroy (Treenode subtree) {// Função privada: exclua a subárvore com a subárvore root if (subtree! = null) {Destroy (subtree.getLeftChild ()); // Exclua a subárvore esquerda Destroy (subtree.getrightChild ()); // exclua a subárvore direita // excluir subárvore; // excluir o nó raiz subárrue = null; }} public void Traverse (Treenode subtree) {System.out.println ("Key:" + subtree.getKey () + "--name:" + subtree.getData ()); Traverse (subtree.getLeftChild ()); Traverse (subtree.getRightChild ()); } public void pré -encomenda (subtree Treenode) {// root primeiro if (subtree! = null) {visted (subtree); Pré -encomenda (subtree.getleftchild ()); Pré -encomenda (subtree.getrightChild ()); }} public void inOrder (subtree Treenode) {// raiz média if (subtree! = null) {inOrder (subtree.getLeftChild ()); Vistorado (subárvore); InOrder (subtree.getrightChild ()); }} public void Postorder (subtree Treenode) {// Publique root if (subtree! = null) {postorder (subtree.getleftchild ()); PROTORMA (Subtree.getRightChild ()); Vistorado (subárvore); }} public void LevelOrder (subtree Treenode) {// periferia horrivelmente} public boolean Insert (elemento Treenode) {// inserir retorno true; } public boolean find (elemento Treenode) {// encontre retorno true; } public void testemunhado (subtree Treenode) {subtree.setvisted (true); System.out.println ("key:" + subtree.getKey () + "--name:" + subtree.getData ()); } public static void main (string [] args) {binarytree bt = new binarytree (); bt.createbintree (bt.root); System.out.println ("O tamanho da árvore é" + bt.size ()); System.out.println ("A altura da árvore é" + bt.Height ()); System.out.println ("********* FELIZAÇÃO (pré -encomenda) [abdecf] transferência ****************"); bt.reorder (bt.root); System.out.println ("********* ROOT MEDIO (ORDEM INTERNO) [DBEACF] transferência ****************"); Bt.inOrder (Bt.root); System.out.println ("********* Last Root (Ordem de postagem) [Debfca] Transfer ****************"); Bt.PostOrder (Bt.root); }} Resultados Saída:
O tamanho da árvore é 6
A altura da árvore é 3
******* Primeira raiz (pré -encomenda) [abdecf] Traversal ******************
Chave: 1-Nome: RootNode (a)
Chave: 2-Nome: b
Chave: 4-Nome: d
Chave: 5-Nome: e
Chave: 3-Nome: c
Chave: 6-Nome: f
******* raiz média (ordem do meio) [dbeacf] Traversal ********************
Chave: 4-Nome: d
Chave: 2-Nome: b
Chave: 5-Nome: e
Chave: 1-Nome: RootNode (a)
Chave: 3-Nome: c
Chave: 6-Nome: f
******* Última raiz (ordem postal) [Debfca] Traversal ******************
Chave: 4-Nome: d
Chave: 5-Nome: e
Chave: 2-Nome: b
Chave: 6-Nome: f
Chave: 3-Nome: c
Chave: 1-Nome: RootNode (a)
Espero que este artigo seja útil para os alunos que estudam a programação Java.