Классификация бинарных деревьев (по структуре хранения)
Классификация деревьев (по структуре хранения)
Последовательное хранение (представлено массивами (статическое двоичное дерево))
Цепочка хранения
Некоторые специальные бинарные корни:
Полное двоичное дерево, сбалансированное бинарное дерево (AVL), Бинарное дерево подсказка, трифорк (указатель с отцом)
Дерево бинарного поиска или бинарное дерево поиска (BST)
Используемое двоичное дерево показано на следующем рисунке:
Java реализация двоичного дерева (структура хранения цепи)
Класс TREENODE {private int key = 0; Private String Data = null; Частный логический Isvisted = false; Частный TreeNode LeftChild = null; Частный TreeNode RightChild = NULL; public triEnode () {} public treeNode (int key, string data) {this.key = key; this.data = data; 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 (String Data) {this.Data = data; } public treeNode getleftChild () {return Leatschild; } public void setleftChild (TreeNode LeftChild) {this.leftChild = LeftChild; } public triEnode getrightChild () {return rightchild; } public void setrightChild (treeNode rightchild) {this.rightChild = RightChild; } public Boolean Isvisted () {return Isvisted; } public void setVisted (boolean Isvisted) {this.isvisted = iSvisted; }} public class binarytree {private treeNode root = null; public binarytree () {root = new TreeNode (1, "rootnode (a)"); } public void createBintree (root treeNode) {// Ручное создание (структура показана на рисунке) 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 () {// определить, является ли двоичное дерево пустым или не возвращает root == null; } public int height () {// Найти высоту высоты дерева (корень); } public int height (TreeNode Subtree) {if (subtree == null) return 0; // рекурсивный конец: высота пустого дерева равна 0 else {int i = высота (subtree.getleftchild ()); int j = высота (subtree.getrightchild ()); Вернуться (я <j)? J + 1: i + 1; }} public int size () {// Найти количество узлов возвращаемого размера (root); } public int size (treeNode subtree) {if (subtree == null) return 0; else {return 1 + size (subtree.getleftchild ()) + size (subtree.getrightchild ()); }} public treeNode parent (элемент TreeNode) {// возвращать родительский узел return (root == null || root == element)? NULL: родитель (корень, элемент); } public treeNode parent (подтереж TreeNode, элемент TreeNode) {if (subtree == null) return null; if (subtree.getleftchild () == element || subtree.getrightChild () == element) // Завершите, верните адрес родительского узла возвращаемого подтеж; TreeNode P; // Сначала посмотрите в левом поддерево. Если это не найдено в левом поддерею, перейдите в правую поддерею, чтобы найти if (p = parent (subtree.getleftchild (), element))! = NULL) // Рекурсивно ищите возврат p; else // Рекурсивно искать возвращающийся родитель (subtree.getrightchild (), element); } public TreeNode Leatschild (Element TreeNode) {// возвращать левый поддерек return (element! = null)? element.getleftchild (): null; } public treeNode rightchild (leenode element) {// return правый подборе return (element! = null)? element.getrightChild (): null; } public triEnode getRoot () {// Получить корневой узел return root; } public void Drouse (TreeNode Subtree) {// Приватная функция: Удалить подтерек с помощью корневого подтерея if (подтере! // Удалить левый поддерек Destroy (subtree.getrightChild ()); // удалить правую поддерево // Удалить поддерек; // Удалить корневой узел subtree = null; }} public void Traverse (TreeNode Subtree) {System.out.println ("key:" + subtree.getKey () + "-name:" + subtree.getData ()); Traverse (subtree.getleftChild ()); Traverse (subtree.getrightchild ()); } public void предварительный заказ (подтереж TreeNode) {// root первой if (subtree! = null) {visted (subtree); Предварительный заказ (subtree.getleftchild ()); Предварительный заказ (subtree.getrightchild ()); }} public void inorder (TreeNode subtree) {// Medium root if (subtree! = null) {inorder (subtree.getleftchild ()); визит (поддерево); Inorder (subtree.getrightchild ()); }} public void postord (treeNode subtree) {// post root if (subtree! = null) {postorder (subtree.getleftchild ()); Postorder (subtree.getRightChild ()); визит (поддерево); }} public void -уровни (TreeNode subtree) {// horily periphery} public boolean insert (leenode element) {// invation return true; } public boolean find (element treeNode) {// Найти return true; } public void свидетельствует (TreeNode subtree) {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 («Размер дерева равен» + bt.size ()); System.out.println («Высота дерева: + bt.height ()); System.out.println ("********* предварительный заказ (предварительный заказ) [abdecf] передача ***************"); bt.preorder (bt.root); System.out.println ("********* Средний корень (внутренний заказ) [DBEACF] TRANSFER **************** '); Bt.InOrder (Bt.Root); System.out.println ("********* bt.postorder (bt.root); }} Результаты вывод:
Размер дерева 6
Высота дерева 3
******* Первый корень (предварительный заказ) [abdecf] Traversal ********************
Ключ: 1-name: rootnode (a)
КЛЮЧ: 2-name: b
Ключ: 4-name: d
Ключ: 5-name: e
КЛЮЧ: 3-name: c
Ключ: 6-name: f
******* Средний корень (средний порядок) [DBEACF] Traversal ********************
Ключ: 4-name: d
КЛЮЧ: 2-name: b
Ключ: 5-name: e
Ключ: 1-name: rootnode (a)
КЛЮЧ: 3-name: c
Ключ: 6-name: f
******* Последний корень (пост -заказ) [debfca] Traversal **********************
Ключ: 4-name: d
Ключ: 5-name: e
КЛЮЧ: 2-name: b
Ключ: 6-name: f
КЛЮЧ: 3-name: c
Ключ: 1-name: rootnode (a)
Я надеюсь, что эта статья будет полезна для студентов, которые изучают программы Java.