Classification des arbres binaires (par structure de stockage)
Classification des arbres (par structure de stockage)
Stockage séquentiel (représenté par des tableaux (arbre binaire statique))
Stockage de chaîne
Quelques racines binaires spéciales:
Arbre binaire complet, arbre binaire équilibré (AVL), arbre binaire d'indice, tri-fourche (pointeur avec père)
Arbre de recherche binaire ou arbre de recherche binaire (BST)
L'arbre binaire utilisé est illustré dans la figure suivante:
Implémentation Java de l'arbre binaire (structure de stockage de la chaîne)
classe Treenode {private int key = 0; Data de chaîne privée = null; Boolean privé isvist = false; Treenode privé Leftchild = null; Treenode privé RightChild = null; public Treenode () {} public Treenode (int key, string data) {this.key = key; this.data = data; this.leftchild = null; this.RightChild = null; } public int getkekey () {return key; } public void setKey (int key) {this.key = key; } public String getData () {return data; } public void setData (String data) {this.data = data; } public Treenode Getleftchild () {return LeftChild; } 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 isvist; } public void setVisted (boolean isvisted) {this.isvist = isvisted; }} classe publique BinaryTree {private Treenode root = null; public binaryTree () {root = new Treenode (1, "rootNode (a)"); } public void createBintree (Treenode root) {// Création manuelle (la structure est représentée sur la figure) 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 () {// Déterminez si l'arbre binaire est vide ou non root renvoie == null; } public int height () {// trouver la hauteur de retour de la hauteur de l'arborescence (root); } public int height (Treenode subTree) {if (subtree == null) return 0; // Extrémité récursive: La hauteur de l'arbre vide est 0 else {int i = height (subtree.getLeftchild ()); int j = height (subtree.getRightChild ()); retour (i <j)? J + 1: i + 1; }} public int size () {// Trouver le nombre de nœuds de retour taille (root); } public int size (Treenode subTree) {if (subtree == null) return 0; else {return 1 + size (subtree.getLeftChild ()) + size (subtree.getRightChild ()); }} public Treenode Parent (élément Treenode) {// renvoie le nœud parent return (root == null || root == élément)? NULL: parent (racine, élément); } public Treenode Parent (Treenode Subtree, Treenode Element) {if (subtree == null) return null; if (subtree.getLeftchild () == élément || subtree.getRightChild () == élément) // fini, renvoie l'adresse du nœud parent return subtree; Treenode P; // Regardez d'abord dans le sous-arbre gauche. S'il ne se trouve pas dans le sous-arbre gauche, accédez au sous-arbre droit pour trouver if ((p = parent (subtree.getLeftChild (), élément))! = Null) // Recherchez recursivement le retour p; Else // Recherchez récursivement le parent de retour (subtree.getRightChild (), élément); } public Treenode LeftChild (élément Treenode) {// Renvoie le subtree RETOUR (élément! = null)? element.getLeftChild (): null; } public Treenode RightChild (élément Treenode) {// Renvoie le return de sous-arbre droit (élément! = null)? element.getRightChild (): null; } public Treenode Getroot () {// Get the Root Node return root; } public void destrust (Treenode Subtree) {// Fonction privée: supprimez le sous-arbre avec un sous-arbre racine if (subtree! = null) {destrust (subtree.getLeftchild ()); // Supprimer le Subtree de Destreau gauche (subtree.getRightChild ()); // Supprimer le sous-arbre droit // Supprimer Subtree; // Supprimer le nœud racine subtree = null; }} public void Traverse (Treenode SubTree) {System.out.println ("key:" + subtree.getKey () + "--name:" + subtree.getData ()); Traverse (subtree.getLeftchild ()); Traverse (subtree.getRightChild ()); } public void Precommande (Treenode Subtree) {// root d'abord if (subtree! = null) {Vistred (subtree); Précommande (subtree.getLeftchild ()); Précommande (subtree.getRightChild ()); }} public void inOrder (Treenode Subtree) {// Root moyen if (subtree! = null) {inOrder (subtree.getLeftChild ()); Vistred (Subtree); InOrder (subtree.getRightChild ()); }} public void postorder (Treenode Subtree) {// post root if (subtree! = null) {postorder (subtree.getLeftchild ()); Postorder (subtree.getRightChild ()); Vistred (Subtree); }} public void levelOrder (Treenode Subtree) {// HORINGly Périphery} public Boolean Insert (élément Treenode) {// INSERT RETOUR Vrai; } public boolean find (élément Treenode) {// find return true; } public void témoin (Treenode Subtree) {subtree.setvist (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 ("La taille de l'arbre est" + bt.size ()); System.out.println ("La hauteur de l'arbre est" + bt.height ()); System.out.println ("********* Précommande (précommande) [Abdecf] transfert ****************"); Bt.Preorder (bt.root); System.out.println ("********* Root moyen (ordre intérieur) [dbeAcf] transfert ****************"); bt.inorder (bt.root); System.out.println ("********* Last Root (Post Order) [Debfca] Transfert ****************"); Bt.Postorder (bt.root); }} Sortie des résultats:
La taille de l'arbre est 6
La hauteur de l'arbre est 3
******* Première racine (précommande) [Abdecf] Traversal ****************
clé: 1 - nom: rootNode (a)
clé: 2 - nom: b
Clé: 4 - nom: D
clé: 5 - nom: e
clé: 3 - nom: c
clé: 6 - nom: f
******* Racine moyenne (ordre du milieu) [dbeacf] Traversal ******************
Clé: 4 - nom: D
clé: 2 - nom: b
clé: 5 - nom: e
clé: 1 - nom: rootNode (a)
clé: 3 - nom: c
clé: 6 - nom: f
******* Dernière racine (Post Order) [Debfca] Traversal ****************
Clé: 4 - nom: D
clé: 5 - nom: e
clé: 2 - nom: b
clé: 6 - nom: f
clé: 3 - nom: c
clé: 1 - nom: rootNode (a)
J'espère que cet article sera utile aux étudiants qui étudient la programmation Java.