Одно, определение бинарной сортировки
1. Определение двоичного дерева сортировки <br /> двоичное дерево сортировки (двоичное дерево сортировки), также известное как двоичное дерево поиска. Он определяется как: двоичное дерево сортировки или пустое дерево, или двоичное дерево, которое соответствует следующим свойствам:
① Если его левый поддерек не является пустым, значения всех узлов на левом поддерее меньше значения корневого узла;
② Если его правый поддерек не является пустым, значения всех узлов на правом поддерее больше, чем значения корневого узла;
③ Левые и правые подтерей сами - это бинарное сортировочное дерево.
Приведенные выше свойства называются свойством двоичного дерева сортировки (свойство BST), поэтому двоичное дерево сортировки на самом деле является бинарным деревом, которое удовлетворяет свойству BST.
2. Свойства бинарного дерева сортировки <Br /> Передача бинарной сортировки в середине порядка, а результирующая последовательность промежуточного оказания промежуточного порядка является последовательной последовательности.
3. Вставьте двоичное дерево сортировки <br /> вставить новый узел в двоичное дерево сортировки, чтобы убедиться, что вставленное двоичное дерево все еще соответствует определению бинарного дерева сортировки.
Вставьте процесс:
Если двоичное дерево сортировки пустое, узел *S должен быть вставлен в пустое дерево в качестве корневого узла;
Когда он не пуст, сравните ключевой слов S->, который будет вставлен с ключевым словом корня дерева T->. Если s-> key = t-> ключ, нет необходимости вставлять его. Если клавиша S-> Key <T->, он вставлен в левое поддеревание корня. Если s-> key> t-> клавиша, он вставлен в правую поддерево корня. Процесс вставки в поддерево такой же, как процесс вставки в дереве. Это продолжается до тех пор, пока узел не будет вставлен в бинарное дерево сортировки в виде нового листа, или до тех пор, пока дерево не будет обнаружена узлами с одинаковыми ключевыми словами.
4. Поиск двоичного дерева сортировки <br /> Предполагая, что корневой указатель двоичного дерева сортировки является корнем, а заданное значение ключевого слова - k, алгоритм поиска может быть описан как:
① Установите начальное значение: q = root;
② Если k = q -> ключ, поиск успешна, а алгоритм заканчивается;
③ В противном случае, если k <q －＞ клавиша и левый поддерек Q не пусты, левое поддеревание Q отправляется в Q, а затем на шаг ②; В противном случае поиск не удается, а алгоритм заканчивается;
④ В противном случае, если k ＞ q －＞ клавиша, и правая поддерево Q не является пустым, правая поддерево Q отправляется в Q, а затем на шаг ②; В противном случае поиск терпит неудачу, а алгоритм заканчивается.
5. Удаление бинарного дерева сортировки <br /> Предположим, что удаленный узел - *P, а родители - *F, что не теряется в общности. Предположим, что *P - левый ребенок *F, следующее разделено на три ситуации:
⑴ Если узел *p - листовой узел, вам нужно только изменить указатель его родительского узла *f.
⑵ Если узел *P имеет только левый поддерек PL или только правый PR -PR, то просто сделайте PL или PR левый поддерек его родительского узла.
⑶ Если левые и правые подделки узла *P не являются пустыми, сначала найдите предшественник среднего порядка (или преемник) узел *S *P (обратите внимание, что *S - самый нижний правый узел в левом подтере *P, а его правая цепь - пуст), а затем есть два способа: ① Left Subtree *P -непосредственно на левой цепи родитель -Node *F -Plee -Preme -Subtre - Pright -Subtre *P -Ply -Subtre - Pright Prostre -Subtree - правый подчинен, и Pry -Subtre - Pright -Subtree *P -Plestre *P -Ply -SubTre в правую цепочку *P предшественника среднего порядка. ② Замените *P на предшественник среднего порядка *S *P (то есть копировать данные *S в *P) и подключить левое поддеревание *S в левую (или правую) цепь родительского узла *Q of *s.
6. Переход бинарных деревьев <br /> Есть три способа пройти бинарные деревья следующим образом:
(1) Переоборудование предварительного заказа (DLR), сначала доступ к корневому узлу, затем пересекает левый поддерек и, наконец, пересекает правый поддерек. Сокращенный корень - слева - справа.
(2) Тонверс в порядке (LDR), сначала пересекайте левый поддерек, затем получите доступ к корневому узлу и, наконец, пройдите правый поддерек. Сокращенная примечание: лево-правом.
(3) Пост-заказ обход (LRD), сначала пересекающий левый поддерек, затем пройдя правый поддерев и, наконец, доступ к корневому узлу. Сокращенный левый правый корень.
2. Запись кода
1. Определение класса узлов деревьев 0 класс 0
пакет com.lin; / ** * Функция Сводка: */ public class triEnode {public Integer Data; /* Родительский узел этого узла*/ public treeNode parent; /*Left Child Node этого узла*/ public TreeNode Love; /*Правый детский узел этого узла*/ public treeNode справа; public TriEnode (Integer Data) {this.Data = data; } @Override public String toString () {return "triEnode [data =" + data + "]"; }} 2. Определение бинарного дерева сортировки
пакет com.lin; /*** Функция Сводка: сортировка/сбалансированное двоичное дерево*/public class searchtree {public treeNode root; общественный больший размер; / ** * Добавить узел в дерево * @param Data * @return Boolean Insertion Возвращает true */ public boolean AddTreeNode (Integer Data) {if (null == root) {root = new TreeNode (data); System.out.println («Данные были успешно вставлены в сбалансированное двоичное дерево»); вернуть истину; } TreeNode triEnode = new TreeNode (data); // Данные, которые должны быть вставлены TreeNode currentNode = root; TreeNode ParentNode; while (true) {parentnode = currentNode; // Сохранить родительский узел // Вставленные данные меньше родительского узла if (currentNode.data> data) {currentNode = currentNode.left; // Левый дочерний узел текущего родительского узла пуст, если (null == currentnode) {parentnode.left = treeNode; treeNode.parent = parentnode; System.out.println («Данные были успешно вставлены в двоичное дерево поиска»); размер ++; вернуть истину; } // Вставленные данные больше родительского узла} else if (currentNode.data <data) {currentNode = currentNode.right; // Правильный дочерний узел текущего родительского узла пуст, если (null == currentnode) {parentnode.right = treeNode; treeNode.parent = parentnode; System.out.println («Данные успешно вставлены в двоичное дерево поиска»); размер ++; вернуть истину; }} else {System.out.println («Входные данные такие же, как данные узла»); вернуть ложь; }}} / ** * @param data * @return trienode * / public treeNode findTreeNode (Integer Data) {if (null == root) {return null; } TreeNode current = root; while (current! = null) {if (current.data> data) {current = current.left; } else if (current.data <data) {current = current.right; } else {return current; }} return null; }} Вот метод добавления и поиска
3. Передняя, средняя и спина
пакет com.lin; импортировать java.util.stack; / *** Функциональная сумма:*/ открытый класс Treeorder {/ *** Рекурсивная реализация предварительного заказа Traversal* @author linbingwen* @since 29 августа 2015 г.* @param trieNode*/ public void -preordermethodone (triEnode) {if (null! if (null! = treenode.left) {предварительный заказметодон (treeNode.left); } if (null! = treeNode.right) {предварительный заказметодон (treeNode.right); }}} / *** Целью для реализации предварительного заказа Traversal* @param treeNode* / public static void preordermethodtwo (treeNode trieNode) {if (null! = TreeNode) {Stack <treeNode> Stack = new Stack <TreeNode> (); stack.push (treenode); while (! Stack.isempty ()) {treeNode tempnode = Stack.pop (); System.out.print (tempnode.data + ""); // Правильный дочерний узел не является нулевым, поместите правильный дочерний узел в if (null! = Tempnode.right) {Stack.push (tempnode.right); } // После помесщения правильного дочернего узла поместите левый детский узел и возьмите if (null! }}}} / *** Рекурсивно реализовать обход на заказ* @param trienode* / public void medordermethodone (treenode trieNode) {if (null! = TreeNode) {if (null! = TreeNode.left) {medoromeMethodone (treeNode.left); } System.out.print (treeNode.data + ""); if (null! = treeNode.right) {medOrderMethodone (treeNode.right); }}} / *** Реализация цикла in Order Traversal* @param trieNode* / public static void medoromemethodtwo (treeNode triEnode) {Stack <TreeNode> Stack = new Stack <treeNode> (); TreeNode Current = TreeNode; while (current! = null ||! Stack.isempty ()) {while (current! = null) {Stack.push (current); current = current.left; } if (! Stack.isempty ()) {current = Stack.pop (); System.out.print (current.data+""); ток = current.right; }}} / *** Рекурсивно реализовать пост-порядковый обход* @param trieNode* / public static void postordermethodone (treeNode triEnode) {if (null! = TreeNode) {if (null! = TreeNode.left) {postordermethodone (treeNode.left); } if (null! = treeNode.right) {postordermethodone (treeNode.right); } System.out.print (treeNode.data + ""); }} / *** Цикл для реализации пост-порядка Traversal* @param trirenode* / public static void postermethodtwo (treeNode triEnode) {if (null! = TreeNode) {Stack <TreeNode> Stack = new Stack <treenode> (); TreeNode Current = TreeNode; TreeNode RightNode = null; while (current! = null ||! Stack.isempty ()) {while (current! = null) {Stack.push (current); current = current.left; } current = Stack.pop (); while (current! = null && (current.right == null || current.right == rightnode)) {System.out.print (current.data + ""); rightnode = current; if (stack.isempty ()) {System.out.println (); возвращаться; } current = Stack.pop (); } stack.push (current); ток = current.right; }}}} 4. Как использовать
пакет com.lin; / ** * Функция Сводка: */ public class searchtreetest {/ ** * @param args */ public static void main (string [] args) {searchtree tree = new SearchTree (); Tree.addtreeNode (50); Tree.AddTreeNode (80); Tree.AddTreeNode (20); Tree.addtreeNode (60); Tree.addtreeNode (10); Tree.addtreeNode (30); Tree.addtreeNode (70); Tree.addtreeNode (90); Tree.addtreeNode (100); Tree.addtreeNode (40); System.out.println ("========================================================================================================== ===================================================================== ====================================================================== ===================================================================== ====================================================================== ====================================================================== ====================================================================== System.out.println ("========================================================================= ======================================================================= ======================================================================= ======================================================================== ======================================================================= ======================================================================= ======================================================================= ======================================================================== Treeorder.postordermethodone (Tree.root); System.out.println ("====================================================================================== ====================================================================== ===================================================================== ====================================================================== ===================================================================== ====================================================================== ===================================================================== System.out.println ("========================================================================= ======================================================================= ======================================================================= ======================================================================== ======================================================================= ======================================================================= ======================================================================= ======================================================================== Treeorder.medordermethodtwo (tree.root);Результат вывода:
Точно так же процесс поиска выглядит следующим образом:
TREENODE NODE = TREE.FINDTREENODE (100); System.out.println (Node);
Результат верен
Выше приведено подробное введение в бинарное дерево сортировки Java. Я надеюсь, что это будет полезно для изучения программирования Java каждого.