Java는 이진 검색 트리를 구현하고 트리의 검색, 삽입 및 삭제를 구현합니다 (병합 및 삭제, 복사 및 삭제)
우선, 우리는 대략 다음과 같이 코딩 아이디어가 필요합니다.
1. 검색 : 이진 검색 트리의 데이터 특성에 따라 노드의 값 비교를 기반으로 검색을 실현할 수 있습니다. 검색 값이 현재 노드보다 큰 경우 오른쪽으로 이동하십시오.
2. 삽입 : 삽입 된 모든 것이 리프 노드임을 알아야하므로 삽입 할 리프 노드의 위치를 찾아야하며 삽입 아이디어는 검색 아이디어와 일치합니다.
3. 삭제 :
1) 병합 및 삭제 : 일반적으로 말하면 다음 상황이 발생합니다. 삭제 된 노드에는 왼쪽 하위 트리가 있지만 오른쪽 하위 트리는 없습니다. 이때, 현재 노드의 상위 노드는 전류 노드의 왼쪽 하위 트리를 가리켜야합니다. 삭제 된 노드에 오른쪽 하위 트리가 있지만 왼쪽 하위 트리가 없으면, 현재 노드의 상위 노드는 오른쪽 하위 트리를 가리켜야합니다. 삭제 된 노드에 왼쪽 하위 트리와 오른쪽 서브 트리가 있으면 삭제 된 노드의 왼쪽 하위 트리의 가장 오른쪽 노드를 찾은 다음이 노드의 오른쪽 또는 왼쪽 "포인터"를 삭제 된 노드의 오른쪽 하위 트리로 지정할 수 있습니다.
2) 복사 및 삭제 : 복사 및 삭제는 비교적 간단한 삭제 작업이며 가장 일반적으로 사용되는 삭제 작업입니다. 대략 세 가지 상황이 있습니다 : 현재 노드에 왼쪽 하위 트리가없고 오른쪽 하위 트리가있는 경우, 현재 오른쪽 서브 트리의 루트 노드가 삭제 된 노드를 교체하도록하십시오. 현재 노드에 오른쪽 하위 트리가없고 왼쪽 하위 트리가있는 경우, 전류 왼쪽 하위 트리의 루트 노드를 놓고 삭제 된 노드를 교체하십시오. 현재 삭제 된 노드에 왼쪽 하위 트리와 오른쪽 서브 트리가 있으면 삭제 된 노드의 하위 트리를 찾아 왼쪽 하위 트리에서 가장 오른쪽 노드를 찾아이 노드의 값을 삭제 된 노드에 할당 한 다음, 하위 트리의 "포인터"를 비어있는 것을 잊지 마십시오 (사실, Java에서는 문제가되지 않습니다. 자동으로 처리). 이 프로세스를 현재 삭제 된 노드의 오른쪽 하위 트리의 가장 왼쪽 노드에서 독립형 노드로 구현할 수도 있습니다.
다음으로 코드를 추가하겠습니다.
우선, ## 이진 검색 트리 노드 클래스 ##
SearchBinaryTree 패키지; 공개 클래스 SearchBinaryTreenode <t> {T Data; 공개 SearchBinaryTreenode <T> 좌익; 공개 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 () {반환 데이터; } public void setData (t data) {this.data = data; } public searchBinaryTreenode <T> getLeftChild () {return LeftChild; } public void setleftChild (SearchBinaryTreenode <T> LeftChild) {this.leftChild = LeftChild; } 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를 반환합니다. }}이진 검색 트리 구현
패키지 SearchBinaryTree; 공개 클래스 SearchBinaryTree <t> {SearchBinaryTreenode <T> 루트; public boolean isempty () {if (root == null) {return true; } false를 반환합니다. } public void visit (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> (); } 반환 루트; } public searchBinaryTree () {this.root = null; } /** 이진 트리 생성* / public void createTree (searchBinaryTreenode <T> 노드, t 데이터) {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> (데이터); } else {createTree (node.rightchild, data); }}}}} /** 두 번째 검색 검색 트리에서 검색* / public searchBinaryTreenode <T> 검색 (searchBinaryTreenode <T> root, t value) {searchBinaryTreenode <t> current = root; while ((root! = null) && (current.getData ()! = value)) {// Java의 제네릭은 크기를 비교할 수 없다는 점에 유의해야합니다. 실제로 사용하면 공통 데이터 유형을 사용 하여이 제네릭을 대체 할 수 있으므로 오류가 없습니다. current = (value <current.getData ()? 검색 (current.leftChild, value) : 검색 (current.rightchild, value)); } 현재 반환; } public searchBinaryTreenode <t> insertNode (t value) {searchBinaryTreenode <t> p = root, pre = null; while (p! = null) {pre = p; // Java의 제네릭은 크기를 비교할 수 없다는 점에 유의해야합니다. 실제로 사용하면 공통 데이터 유형을 사용 하여이 제네릭을 대체 할 수 있으므로 (p.getData () <value) {p = p.rightchild; } else {p = p.leftChild; }} if (root == null) {root = new SearchBinaryTreenode <t> (value); } else if (pre.getData () <value) {pre.rightchild = new SearchBinaryTreenode <t> (value); } else {pre.LeftChild = New SearchBinaryTreenode <t> (value); }} /** 병합 및 삭제* / public void deleteBymerging (searchBinaryTreenode <T> 노드) {searchBinaryTreenode <T> temp = 노드; if (node! = null) {// 삭제 된 노드에 오른쪽 서브 트리가없는 경우 왼쪽 서브 트리의 루트 노드를 사용하여 삭제 된 노드를 대체하십시오 if (node.rightchild! = null) {node = node.leftChild; } else if (node.leftchild == null) {// 삭제 된 노드에 왼쪽 서브 트리가없는 경우 삭제 된 노드 노드 대신 단어 수와 함께 왼쪽 노드를 사용하십시오. } else {// 삭제 된 노드의 왼쪽 및 오른쪽 하위 트리에 temp = node.leftChild가있는 경우; while (temp.rightchild! = null) {temp = temp.rightchild; // 왼쪽 하위 트리의 오른쪽 노드를 찾으십시오} // 삭제 된 노드 템피의 오른쪽 서브 트리의 루트에 찾은 노드의 오른쪽 포인터를 지정합니다. 온도 = 노드; node = node.leftchild; } temp = null; }} / * * 복사 및 삭제 * / public void deletebycoping (searchBinaryTreenode <T> 노드) {SearchBinaryTreenode <T> pre = null; searchBinaryTreenode <t> temp = 노드; // 삭제 된 노드에 오른쪽 서브 트리가없는 경우 왼쪽 서브 트리의 루트 노드를 사용하여 삭제 된 노드를 대체합니다. if (node.rightchild == null) {node = node.leftChild; } else if (node.leftchild == null) {node = node.rightchild; } else {// 삭제 된 노드의 왼쪽 및 오른쪽 하위 트리에 temp = node.leftChild가있는 경우; pre = 노드; while (temp.rightchild! = null) {pre = temp; Temp = temp.rightchild; // 왼쪽 하위 트리의 가장 오른쪽 노드를 찾기 위해 이동} node.data = temp.data; // 할당 작업을 수행하면 (pre == 노드) {pre.leftchild = node.leftChild; } else {pre.rightchild = node.rightchild; }} temp = null; }}테스트 클래스
패키지 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.search (tree.root, 7); // tree.deleteBymerging (new SearchBinaryTreenode <integer> (8)); // tree를 복사하고 삭제합니다 .DeleteByCoping (new SearchBinaryTreenode <integer> (6)); }}좋아, 그게 다야!
위의 기사 Java는 이진 검색 트리를 생성하고 검색, 삽입 및 삭제 작업 예제는 내가 공유하는 모든 내용입니다. 나는 당신이 당신에게 참조를 줄 수 있기를 바랍니다. 그리고 당신이 wulin.com을 더 지원할 수 있기를 바랍니다.