Um, definição de árvore de classificação binária
1. Definição de árvore de classificação binária <Br /> Árvore de classificação binária (árvore de classificação binária), também conhecida como árvore de pesquisa binária. É definido como: uma árvore de classificação binária ou uma árvore vazia, ou uma árvore binária que atenda às seguintes propriedades:
① Se sua subárvore esquerda não estiver vazia, os valores de todos os nós na subárvore esquerda são menores que o valor do nó raiz;
② Se sua subárvore direita não estiver vazia, os valores de todos os nós na subárvore direita são maiores que os valores do nó raiz;
③ As próprias subárvores esquerda e direita são uma árvore de classificação binária.
As propriedades acima são referidas como propriedade de árvore de classificação binária (propriedade BST), portanto a árvore de classificação binária é na verdade uma árvore binária que satisfaz a propriedade BST.
2. Propriedades da árvore de classificação binária <Br /> transferem a árvore de classificação binária na ordem média, e a sequência de travessia de ordem intermediária resultante é uma sequência ordenada incremental.
3. Insira a árvore de classificação binária <Br /> Insira um novo nó na árvore de classificação binária, para garantir que a árvore binária inserida ainda atenda à definição da árvore de classificação binária.
Inserir processo:
Se a árvore de classificação binária estiver vazia, o nó *s ser inserido na árvore vazia como nó raiz;
Quando não estiver vazio, compare a tecla Palavra-chave S-> a ser inserida com a tecla Palavra da Raiz da Árvore T->. Se s-> key = t-> chave, não há necessidade de inseri-la. Se a tecla S-> <T->, ela será inserida na subárvore esquerda da raiz. Se s-> chave> t-> tecla, ela será inserida na subárvore direita da raiz. O processo de inserção na subárvore é o mesmo que o processo de inserção na árvore. Isso continua até que o nó *s seja inserido na árvore de classificação binária como uma nova folha, ou até que a árvore tenha nós com os mesmos palavras -chave.
4. Pesquise a árvore de classificação binária <BR /> Supondo que o ponteiro raiz da árvore de classificação binária seja raiz e o valor da palavra -chave fornecido seja k, o algoritmo de pesquisa pode ser descrito como:
① Defina o valor inicial: q = root;
② Se k = q -> chave, a pesquisa será bem -sucedida e o algoritmo termina;
③ Caso contrário, se a tecla K <q －＞ e a subárvore esquerda de Q não estiverem vazias, a subárvore esquerda de Q é enviada para Q e depois a etapa ②; Caso contrário, a pesquisa falha e o algoritmo termina;
④ Caso contrário, se k ＞ q －＞ chave, e a subárvore direita de q não estiver vazia, a subárvore direita de q é enviada para Q e depois a etapa ②; Caso contrário, a pesquisa falha e o algoritmo termina.
5. A exclusão da árvore de classificação binária <BR /> suponha que o nó excluído seja *p e os pais sejam *f, que não se perde na generalidade. Suponha que *P seja o filho esquerdo de *f, o seguinte é dividido em três situações:
⑴ Se o nó *P é um nó foliar, você só precisa modificar o ponteiro do nó pai *f.
⑵ Se o nó *P tiver apenas a subárvore esquerda PL ou apenas a subárvore direita PR, basta fazer PL ou PR a subárvore esquerda de seu nó pai.
⑶ Se as subáridas esquerda e direita do nó *p não estiverem vazias, primeiro encontre o nó predecessor (ou sucessor) da ordem média *s de *p (observe que *s é o nó mais baixo direito na subárvore esquerda de *P e o domínio da cadeia direita está vazio) e, em seguida, há duas maneiras: ① ①, que *P, e o domínio da cadeia direta para a esquerda para a esquerda) e depois há duas maneiras: ① ① ①. acorrentado à cadeia direita do nó predecessor da ordem média de *P. *s. ② Substitua *P pelo nó predecessor da ordem média *s de *p (ou seja, copie os dados de *s em *p) e encorrente a subárvore esquerda de *s para a cadeia esquerda (ou direita) do nó pai *q de *s.
6. Travessal de árvores binárias <r /> Existem três maneiras de atravessar árvores binárias, como segue:
(1) Travessal de pré-encomenda (DLR), acessando primeiro o nó raiz, depois atravessando a subárvore esquerda e finalmente atravessando a subárvore direita. Raiz abreviada - esquerda - direita.
(2) Traversal na ordem (LDR), primeiro travessia a subárvore esquerda, depois acesse o nó raiz e finalmente travesal a subárvore direita. NOTA ABREVIATIVA: Right-Right à esquerda.
(3) Traversal pós-ordem (LRD), primeiro atravessando a subárvore esquerda, depois atravessando a subárvore direita e finalmente acessando o nó raiz. Raízes esquerda-direita abreviada.
2. Redação de código
1. Definição de Classe de Nó da Árvore 0
pacote com.lin; / ** * Resumo da função: */ public class Treenode {public Integer Data; /* Nó dos pais deste nó*/ Public Treenode Parent; /*Nó infantil esquerdo deste nó*/ Treenode público esquerdo; /*Nó da criança direita deste nó*/ Treenode público direito; public Treenode (dados inteiros) {this.data = data; } @Override public string tostring () {return "Treenode [data =" + data + "]"; }} 2. Definição de árvore de classificação binária
pacote com.lin; /*** Resumo da função: Sort/Balanced Binary Tree*/public class SearchTree {public Treenode Root; tamanho longo público; / ** * Adicione o nó à árvore * @param dados * @return inserção booleana retorna true */ public boolean addtreenode (dados inteiros) {if (null == root) {root = new Treenode (dados); System.out.println ("Os dados foram inseridos com sucesso na árvore binária equilibrada"); retornar true; } Treenode Treenode = new Treenode (Data); // Os dados a serem inseridos Treenode CurrentNode = root; Treenode parepinode; while (true) {parentNode = currentNode; // salve o nó pai // os dados inseridos são menores que o nó pai se (currentNode.data> data) {currentNode = currentNode.left; // O nó infantil esquerdo do nó pai atual está vazio se (null == currentNode) {parentnode.left = treenode; Treenode.parent = parentNode; System.out.println ("Os dados foram inseridos com sucesso na árvore de pesquisa binária"); tamanho ++; retornar true; } // Os dados inseridos são maiores que o nó pai} else if (currentNode.data <data) {currentNode = currentNode.right; // O nó filho certo do nó pai atual está vazio se (null == currentNode) {parelernode.right = Treenode; Treenode.parent = parentNode; System.out.println ("Os dados são inseridos com sucesso na árvore de pesquisa binária"); tamanho ++; retornar true; }} else {System.out.println ("Os dados de entrada são os mesmos que os dados do nó"); retornar falso; }}} / ** * @param dados * @return Treenode * / public treenode findtreenode (dados inteiros) {if (null == root) {return null; } Treenode Current = root; while (atual! = null) {if (current.data> data) {current = current.left; } else if (current.data <data) {current = current.right; } else {return atual; }} retornar nulo; }} Aqui está um método de adicionar e pesquisar
3. Traversal frontal, médio e traseiro
pacote com.lin; importar java.util.stack; / *** Resumo da função:*/ public Class TreeOrder {/ *** Implementação recursiva de travessia de pré -encomenda* @Author Linbingwen* @Sense 29 de agosto de 2015* @param Treenode*/ public static void (Treenode) (Treenode); if (null! = Treenode.left) {preordesMethodOne (Treenode.left); } if (null! = Treenode.right) {preordesMethodOne (Treenode.right); }}} / *** loop para implementar a pré -encomenda de pré -encomenda* @param treenode* / public static void pré -encomendmethodtwo (Treenode Treenode) {if (null! = Treenode) {Stack <reenode> Stack = new Stack <Treenode> (); Stack.push (Treenode); while (! Stack.isEmpty ()) {Treenode tempnode = stack.pop (); System.out.print (tempnode.data + ""); // O nó infantil certo não é nulo, coloque o nó infantil certo em if (null! = Tempnode.right) {Stack.push (tempnode.right); } // Depois de colocar o nó infantil certo, coloque o nó infantil esquerdo e pegue if (null! = Tempnode.left) {stack.push (tempnode.left); }}}} / *** Implemente recursivamente travessia em ordem* @param treenode* / public static void medterdordmethodona (treenode Treenode) {if (null! } System.out.print (Treenode.data + ""); if (null! = Treenode.right) {MedorderMethodOne (Treenode.right); }}} / *** Implementação de loop Traversal na ordem* @param treenode* / public static void MedorderMethodtwo (Treenode Treenode) {Stack <Treenode> Stack = new Stack <Treenode> (); Treenode Current = Treenode; while (atual! = null ||! Stack.isEmpty ()) {while (atual! = null) {Stack.push (atual); atual = current.left; } if (! stack.isempty ()) {current = pilha.pop (); System.out.print (current.data+""); atual = current.right; }}} / *** Implemente recursivamente travessia de pós-ordem* @param treenode* / public static void postorderMethodOne (Treenode Treenode) {if (null! } if (null! = Treenode.right) {postOrderMethodOne (Treenode.right); } System.out.print (Treenode.data + ""); }} / *** Looping para implementar travessias pós-ordem* @param Treenode* / public static void postorderMethodtwo (Treenode Treenode) {if (null! = Treenode) {Stack <seenode> Stack = new Stack <Treenode> (); Treenode Current = Treenode; Treenode RightNode = NULL; while (atual! = null ||! Stack.isEmpty ()) {while (atual! = null) {Stack.push (atual); atual = current.left; } current = Stack.pop (); while (atual! = null && (current.right == null || current.right == RightNode)) {System.out.print (current.data + ""); RightNode = Current; if (Stack.isEmpty ()) {System.out.println (); retornar; } current = Stack.pop (); } Stack.push (atual); atual = current.right; }}}} 4. Como usar
pacote com.lin; / ** * Resumo da função: */ public class SearchTretest {/ ** * @param args */ public static void main (string [] args) {pesquhree árvore = new SearchTree (); árvore.addtreenode (50); árvore.addtreenode (80); árvore.addtreenode (20); árvore.addtreenode (60); árvore.addtreenode (10); árvore.addtreenode (30); Tree.addtreenode (70); árvore.addtreenode (90); árvore.addtreenode (100); árvore.addtreenode (40); System.out.println("===================================================================================================== ============================================================== =============================================================== ============================================================== =============================================================== =============================================================== =============================================================== System.out.println ("============================================== ==================================================================== ==================================================================== ===================================================================== ==================================================================== ==================================================================== ==================================================================== ===================================================================== TreeOrder.PostOrderMethodOne (Tree.root); System.out.println("====================================================================================================== =============================================================== ================================================================ =============================================================== ================================================================ =============================================================== ================================================================ System.out.println ("============================================== ==================================================================== ==================================================================== ===================================================================== ==================================================================== ==================================================================== ==================================================================== ===================================================================== TreeOrder.MedOrderMethodtwo (Tree.root);Resultado da saída:
Da mesma forma, o processo de pesquisa é o seguinte:
Nó Treenode = Tree.findtreenode (100); System.out.println (nó);
O resultado está correto
O exposto acima é uma introdução detalhada à árvore de classificação binária Java. Espero que seja útil para aprender a programação Java de todos.