Java реализует дерево бинарного поиска и реализует поиск, вставить и удалять операции на дереве (слияние и удаление, копирование и удаление)
Прежде всего, нам нужно иметь идею кодирования примерно следующим образом:
1. Поиск: в соответствии с характеристиками данных двоичного дерева поиска, мы можем реализовать поиск на основе сравнения значений узлов. Когда значение поиска больше текущего узла, перейдите вправо, и наоборот!
2. Вставка: мы должны знать, что все вставленные - это листовые узлы, поэтому нам нужно найти местоположение узела листового узла, и идея вставки согласуется с идеей поиска.
3. Удалить:
1) Слияние и удаление: вообще говоря, будут встречаться следующие ситуации. Удаленный узел имеет левый поддерек, но нет правого поддерево. В это время родительский узел текущего узла должен указывать на левый поддерек текущего узла; Когда удаленный узел имеет правую поддерею, но нет левого поддерева, родительский узел текущего узла должен указывать на правую поддерею; Когда удаленный узел имеет левое поддеревое и правое поддеревое, мы можем найти самый правый узел левого поддерева удаленного узла, а затем позволить правому или левому указателю этого узла в правую поддерею удаленного узла
2) Копировать и удаление: копия и удаление являются относительно простыми операциями удаления, а также являются наиболее часто используемыми операциями удаления. Существует примерно три ситуации: когда текущий узел не имеет левого поддерева и имеет правую поддерево, пусть корневой узел текущего правого поддерека заменит удаленный узел; Когда текущий узел не имеет правого поддерева и имеет левый поддерек, пусть корневой узел текущего левого поддерею и заменить удаленный узел; Когда в удаленном узел в настоящее время есть как левый поддерев, так и правый поддерево, нам нужно найти поддерево удаленного узла и найти самый правый узел в левом поддерею и присвоить значение этого узла удаленному узлу, а затем не забывайте, чтобы «указатель» родительского узла, указывающий на Subtree, на пустоте, он не имеет значения, и есть в джаве. это). Вы также можете реализовать этот процесс как автономный узел на самом левом узле правого поддерева в настоящее время удаленного узла.
Далее, давайте добавим код.
Прежде всего, ## Двоичный класс узлов дерева поиска ##
package searchbinarytree; public class searchbinarytreenode <t> {t data; Public SearchBinaryTreeNode <T> LeathChild; Public SearchBinaryTreeNode <T> RightChild; public searchBinaryTreenode () {this.data = null; this.leftchild = this.rightchild = null; } public searchBinaryTreeNode (t da) {this.data = da; this.leftchild = this.rightchild = null; } public searchBinaryTreeNode (t da) {this.data = da; this.leftchild = this.rightchild = null; } public searchBinaryTreeNode (t da, searchBinaryTreeNode <T> слева, searchBinaryTreenode <T> справа) {this.Data = da; this.leftchild = осталось; this.rightChild = верно; } public t getData () {return data; } public void setData (t data) {this.data = data; } public SearchBinaryTreeNode <T> getLeftChild () {return LeatHild; } public void setleftChild (searchBinaryTreeNode <T> LeathidChild) {this.leftChild = Leatschild; } public SearchBinaryTreeNode <T> getRightChild () {return rightchild; } public void setrightChild (searchBinaryTreeNode <T> rightchild) {this.rightChild = rightchild; } public boolean isleaf () {if (this.leftchild == null && this.rightchild == null) {return true; } вернуть false; }}Реализация бинарного дерева поиска
package searchbinarytree; public class searchbinarytree <t> {searchbinarytreenode <t> root; public boolean isempty () {if (root == null) {return true; } вернуть false; } public void визит (searchBinaryTreeNode <T> root) {if (root == null) {System.out.println («Это дерево пусто!»); } System.out.println (root.getData ()); } public SearchBinaryTreeNode <T> getRoot () {if (root == null) {root = new SearchBinaryTreenode <t> (); } return root; } public searchBinaryTree () {this.Root = null; } /** Создать двоичное дерево* / public void createTree (searchBinaryTreeNode <t> node, t data) {if (root == null) {root = new SearchBinaryTreeNode <t> (); } else {if (math.random ()> 0.5) {// Создать двоичное дерево случайным образом if (node.leftchild == null) {node.leftchild = new SearchBinaryTreenode <t> (data); } else {createTree (node.leftchild, data); }} else {if (node.rightchild == null) {node.rightchild = new SearchBinaryTreenode <t> (data); } else {createTree (node.rightchild, data); }}}}} /** Поиск во втором поиске while ((root! = null) && (current.getData ()! = value)) {// Следует отметить, что дженерики в Java не могут сравнивать размеры. В фактическом использовании мы можем использовать общие типы данных для замены этого общего, поэтому ошибок не будет. Current = (value <current.getData ()? Search (current.leftchild, value): search (current.rightchild, value)); } вернуть ток; } public searchBinaryTreeNode <T> insertNode (t value) {searchBinaryTreeNode <t> p = root, pre = null; while (p! = null) {pre = p; // Следует отметить, что дженерики в Java не могут сравнивать размеры. В фактическом использовании мы можем использовать общие типы данных для замены этого общего, чтобы не было никаких ошибок, если (p.getData () <значение) {p = p.rightChild; } else {p = p.leftchild; }} if (root == null) {root = new SearchBinaryTreenode <T> (значение); } else if (pre.getData () <value) {pre.rightChild = new SearchBinaryTreenode <T> (значение); } else {pre.leftchild = new SearchBinaryTreeNode <t> (значение); }} /** Merge and Delete* / public void deleteBymerging (searchBinaryTreeNode <T> node) {searchBinaryTreeNode <t> temp = node; if (node! = null) {// Если удаленный узел не имеет правого подтерека, используйте корневой узел его левого поддерею, чтобы заменить удаленный узел if (node.rightchild! = null) {node = node.leftchild; } else if (node.leftchild == null) {// Если удаленный узел не имеет левого поддерева, используйте самый левый узел с количеством слов вместо удаленного узла узла = node.rightchild; } else {// Если левые и правые подделки удаленных узлов имеют temp = node.leftchild; while (temp.rightchild! = null) {temp = temp.rightChild; // Следующим образом найти правый узел левого поддерева} // Назначьте правый указатель найденного узла на корень правого поддерева удаленного узла Temp.rightChild = node.rightChild; temp = node; node = node.leftchild; } temp = null; }} / * * Копировать и удалить * / public void deleteBycoping (searchBinaryTreenode <t> node) {searchBinaryTreeNode <t> pre = null; SearchBinaryTreeNode <t> temp = node; // Если удаленный узел не имеет правого поддерева, используйте корневой узел его левого подтерека, чтобы заменить удаленный узел if (node.rightchild == null) {node = node.leftchild; } else if (node.leftchild == null) {node = node.rightchild; } else {// Если левые и правые подделки удаленных узлов имеют temp = node.leftchild; pre = node; while (temp.rightchild! = null) {pre = temp; temp = temp.rightChild; // Путешествие, чтобы найти самый правый узел левого подне} node.data = temp.data; // выполнить операцию назначения if (pre == node) {pre.leftchild = node.leftchild; } else {pre.rightChild = node.rightChild; }} temp = null; }}Тестовый класс
package searchbinarytree; public class searchbinarytreetest {public static void main (string [] args) {searchBinaryTree <Integer> tree = new SearchBinaryTree <Integer> (); for (int i = 1; i <10; i ++) {tree.createTree (new SearchBinaryTreeNode <Integer> (), i); } // Поиск дерево .search (tree.root, 7); // слияние и удаление Tree.DeleteBymerging (новый SearchBinaryTreeNode <Integer> (8)); // Скопировать и удалить Tree.deleteBycoping (new SearchBinaryTreeNode <Integer> (6)); }}Хорошо, вот и все!
Приведенная выше статья Java создает двоичное дерево поиска и реализует поиск, вставку и примеры операции по удалению - это все контент, которым я делюсь с вами. Я надеюсь, что вы можете дать вам ссылку, и я надеюсь, что вы сможете поддержать Wulin.com больше.