Klassifizierung von Binärbäumen (nach Lagerstruktur)
Klassifizierung von Bäumen (nach Lagerstruktur)
Sequentielle Speicherung (dargestellt durch Arrays (statischer Binärbaum))
Kettenspeicher
Einige besondere binäre Wurzeln:
Kompletter binärer Baum, ausgeglichener Binärbaum (AVL), Hinweis Binärbaum, Tri-Hieben (Zeiger mit Vater)
Binärer Suchbaum oder binärer Suchbaum (BST)
Der verwendete binäre Baum ist in der folgenden Abbildung dargestellt:
Java -Implementierung von Binärbaum (Kettenlagerstruktur)
Klasse Treenode {private int key = 0; private String data = null; privat boolean isvisted = false; private treenode lutchild = null; private treenode rightchild = null; public treenode () {} public treenode (int key, string data) {this.key = key; this.data = Daten; this.leftchild = null; this.rightChild = null; } public int getKey () {return key; } public void setKey (int key) {this.key = key; } public String getData () {returndaten; } public void setData (String -Daten) {this.data = data; } public treenode getleftchild () {return lutchild; } public void setLeftchild (Treenode links) {this.leftchild = linkChild; } 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; }} öffentliche Klasse BinaryTree {private treenode root = null; public binaryTree () {root = new treenode (1, "rootNode (a)"); } public void createBinTree (Treenode root) {// manuelle Erstellung (die Struktur ist in der Abbildung gezeigt) 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 () {// Bestimmen Sie, ob der binäre Baum leer ist oder nicht, Root == NULL; } public int height () {// Finden Sie die Baumhöhe zurück (Wurzel); } public int Height (Treenode subTree) {if (subree == null) return 0; // rekursives Ende: Die Höhe des leeren Baumes beträgt 0 sonst {int i = Höhe (subree.getleftchild ()); int j = Höhe (subree.getRightChild ()); Rückkehr (i <j)? J + 1: i + 1; }} public int size () {// Finden Sie die Anzahl der Return Size (root); } public int size (treenode subree) {if (subree == null) return 0; sonst {return 1 + size (subree.getLeftChild ()) + size (subree.getRightChild ()); }} public treenode übergeordnet (Treenode -Element) {// Rückgabe des übergeordneten Knotens return (root == null || root == Element)? NULL: Eltern (Root, Element); } public treenode übergeordnet (Treenode subTree, Treenode -Element) {if (subree == null) return null; if (subree.getleftChild () == Element || subree.getRightChild () == Element) // FISSEN Sie die übergeordnete Knotenadress -Rückgabe -Subree zurück; Treenode P; // Schauen Sie zuerst im linken Subtree an. Wenn es nicht im linken Subtree gefunden wird, gehen Sie zum rechten Subtree, um zu finden, ob ((p = übergeordnet) (SUBREE.GETLEFTCHILD (), Element)! = NULL) // rekursiv nach Rückgabe p; sonst // rekursiv nach Rückgabe übergeordnet (subree.getRightChild (), Element); } public treenode links (Treenode Element) {// RETURATION DER LINKS SUBREE RETORY (Element! = NULL)? element.getLeftchild (): null; } public Treenode RightChild (Treenode -Element) {// RECHT den rechten Subtree -Rückkehr (Element! = NULL)? element.getRightChild (): null; } public treenode getRoot () {// den Stammknoten return root; } public void zerstören (treenode subtree) {// private Funktion: Löschen Sie den Subtree mit root subtree if (subtree! // das linke Subtree -Zerstören löschen (subree.getRightChild ()); // das rechte Subtree löschen // Unterbaum löschen; // Löschen Sie den Stammknoten subree = null; }} public void Traverse (Treenode subTree) {System.out.println ("Schlüssel:" + subtree.getKey () + "--Name:" + subree.getData ()); Traverse (subree.getleftchild ()); Traverse (subree.getRightChild ()); } public void vorbestellt (treenode subTree) {// root zuerst if if (subTree! = null) {visted (subree); Vorbestellt (subree.getleftchild ()); Vorbestellt (subree.getRightChild ()); }} public void inOrder (treenode subTree) {// mittlere Wurzel if (subtree! VISTED (SUBREE); In Ordnung (subtree.getRightChild ()); }} public void postorder (treenode subTree) {// post root if (subree! = null) {postorder (subree.getleftChild ()); Postorder (subree.getRightChild ()); VISTED (SUBREE); }} public void LevelOrder (Treenode subTree) {// Horily Periphery} public boolean Insert (Treenode -Element) {// return true; } public boolean find (treenode element) {// find return true; } public void beobachtet (Treenode subTree) {subtree.setvisted (true); System.out.println ("Schlüssel:" + subree.getKey () + "--Name:" + subree.getData ()); } public static void main (String [] args) {binaryTree bt = new BinaryTree (); Bt.CreatebinTree (Bt.Root); System.out.println ("Die Größe des Baumes ist" + bt.size ()); System.out.println ("Die Höhe des Baumes ist" + bt.height ()); System.out.println("*********PreOrder (Preorder)[ABDECF]Transfer ****************"); bt.preorder (bt.root); System.out.println("*********Medium Root (Inner Order)[DBEACF]Transfer ****************"); bt.inorder (bt.root); System.out.println ("********* Last Root (Post Order) [Debfca] Transfer ****************); bt.postorder (bt.root); }} Ergebnisse Ausgabe:
Die Größe des Baumes beträgt 6
Die Höhe des Baumes beträgt 3
******* Erste Wurzel (Vorbestellung) [ABDECF] Traversal ****************
Schlüssel: 1-Name: RootNode (a)
Schlüssel: 2-Name: b
Schlüssel: 4-Name: d
Schlüssel: 5-Name: e
Schlüssel: 3-Name: c
Schlüssel: 6-Name: f
******* MEDEISCHE Wurzel (mittlere Ordnung) [DBEACF] Traversal ****************
Schlüssel: 4-Name: d
Schlüssel: 2-Name: b
Schlüssel: 5-Name: e
Schlüssel: 1-Name: RootNode (a)
Schlüssel: 3-Name: c
Schlüssel: 6-Name: f
******* Last Root (Post Order) [Debfca] Traversal ****************
Schlüssel: 4-Name: d
Schlüssel: 5-Name: e
Schlüssel: 2-Name: b
Schlüssel: 6-Name: f
Schlüssel: 3-Name: c
Schlüssel: 1-Name: RootNode (a)
Ich hoffe, dieser Artikel wird für Studenten, die Java -Programmierung studieren, hilfreich sein.