하나, 이진 분류 트리 정의
1. 이진 분류 트리의 정의 <br /> 이진 정렬 트리 (이진 정렬 트리), 이진 검색 트리라고도합니다. 이진 분류 트리 또는 빈 트리 또는 다음 속성을 충족하는 이진 트리로 정의됩니다.
extree 왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리의 모든 노드 값이 루트 노드의 값보다 작습니다.
Ormal 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리의 모든 노드 값은 루트 노드의 값보다 큽니다.
왼쪽 및 오른쪽 하위 트리 자체는 각각 이진 분류 트리입니다.
위의 특성은 이진 분류 트리 특성 (BST 특성)이라고하며, 이진 분류 트리는 실제로 BST 속성을 만족시키는 이진 트리입니다.
2. 이진 분류 트리의 특성 <br /> 이진 분류 트리를 중간 순서로 전송하고 결과 중간 주문 트래버스 시퀀스는 점진적 순서 시퀀스입니다.
3. 이진 분류 트리 <br /> 이진 분류 트리에 새 노드를 삽입하여 삽입 된 이진 트리가 여전히 이진 분류 트리의 정의를 충족하는지 확인하십시오.
프로세스 삽입 :
이진 분류 트리가 비어있는 경우 노드 *는 빈 트리에 루트 노드로 삽입됩니다.
비어 있지 않으면 트리 루트 키워드 t-> 키에 삽입 할 키워드 s-> 키를 비교하십시오. s-> key = t-> 키 인 경우 삽입 할 필요가 없습니다. s-> 키 <t-> 키 인 경우 루트의 왼쪽 하위 트리에 삽입됩니다. s-> key> t-> 키 인 경우 루트의 오른쪽 하위 트리에 삽입됩니다. 하위 트리의 삽입 과정은 트리의 삽입 과정과 동일합니다. 이것은 노드 *가 이진 분류 트리에 새 잎으로 삽입 될 때까지 또는 트리에 동일한 키워드가있는 노드가있는 것으로 밝혀 질 때까지 계속됩니다.
4. 이진 분류 트리 검색 <br /> 이진 분류 트리의 루트 포인터가 루트이고 주어진 키워드 값이 K라고 가정하면 검색 알고리즘은 다음과 같이 설명 할 수 있습니다.
① 초기 값 설정 : Q = 루트;
c = k = q-> 키면 검색이 성공하고 알고리즘이 종료됩니다.
그렇지 않으면, k <q －＞ 키와 Q의 왼쪽 하위 트리가 비어 있지 않으면 q의 왼쪽 하위 트리가 Q로 전송되고 단계 ②; 그렇지 않으면 검색이 실패하고 알고리즘이 종료됩니다.
④ 그렇지 않으면, k, q －＞ 키이고 q의 오른쪽 서브 트리가 비어 있지 않으면 q의 오른쪽 하위 트리가 q로 전송 된 다음 단계 ②; 그렇지 않으면 검색이 실패하고 알고리즘이 종료됩니다.
5. 이진 분류 트리의 삭제 <br /> 삭제 된 노드가 *p이고 부모가 *f라고 가정 해 봅시다. *p가 *f의 왼쪽 자식이라고 가정하고 다음은 세 가지 상황으로 나뉩니다.
node *p가 리프 노드 인 경우, 부모 노드의 포인터 만 수정하면됩니다.
node *p에 왼쪽 하위 트리 Pl 또는 오른쪽 하위 트리 PR 만 있으면 PL 또는 PR을 부모 노드의 왼쪽 하위 트리로 만듭니다.
⑶ 노드 *P의 왼쪽과 오른쪽 서브 트리가 비어 있지 않으면 먼저 *p의 중간 순서 이전 모델 (또는 후속) 노드 *s를 찾으십시오 ( *s는 *p의 왼쪽 하위 트리에서 가장 낮은 노드이며 오른쪽 체인 도메인이 비어 있음), 두 가지 방법이 있습니다. *p의 중간 순서 전임 노드 *의 오른쪽 체인에 묶여 있습니다. *p를 *p의 중간 순서 이전 노드 *s로 대체하고 (즉, *s의 데이터를 *p로 복사하고, *s의 왼쪽 하위 트리를 *s of *s의 왼쪽 (또는 오른쪽) 체인으로 체인하십시오.
6. 이진 나무의 횡단 <br /> 다음과 같이 이진 나무를 가로 지르는 세 가지 방법이 있습니다.
(1) 사전 주문 트래버스 (DLR), 먼저 루트 노드에 액세스 한 다음 왼쪽 하위 트리를 가로 지르고 마침내 오른쪽 하위 트리를 가로 지릅니다. 약어 뿌리 - 왼쪽 - 오른쪽.
(2) 순서의 순서 (LDR), 먼저 왼쪽 하위 트리를 트래버스 한 다음 루트 노드에 액세스 한 다음 결국 오른쪽 하위 트리를 가로 질러옵니다. 약어 노트 : 왼쪽 root-right.
(3) 먼저 왼쪽 하위 트리를 통과 한 다음 오른쪽 하위 트리를 가로 지르고 마침내 루트 노드에 액세스합니다. 약식 왼쪽 뿌리.
2. 코드 쓰기
1. 트리 노드 클래스의 정의 0
패키지 com.lin; / ** * 함수 요약 : */ public class treenode {공개 정수 데이터; /*이 노드의 상위 노드*/ public treenode 부모; /*이 노드의 왼쪽 자식 노드*/ public treenode 왼쪽; /*이 노드의 오른쪽 자식 노드*/ 공개 트린 노드 오른쪽; public treenode (정수 데이터) {this.data = data; } @override public String toString () {return "treenode [data =" + data + "]; }} 2. 이진 분류 트리의 정의
패키지 com.lin; /*** 함수 요약 : 정렬/밸런스 바이너리 트리*/public class searchTree {public treenode root; 대중의 긴 크기; / ** * 트리에 노드를 추가 * @param data * @return boolean 삽입을 반환합니다 */ public boolean addtreenode (정수 데이터) {if (null == root) {root = new Treenode (data); System.out.println ( "데이터가 균형 바이너리 트리에 성공적으로 삽입되었습니다"); 진실을 반환하십시오. } Treenode Treenode = New Treenode (데이터); // 삽입 될 데이터가 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 treenode * / public treenode findtreenode (정수 데이터) {if (null == root) {return null; } treenode current = 루트; 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 가져 오기; / *** 함수 요약 :*/ public class treeOrder {/ *** 사전 주문 트래버스의 재귀 구현* @Author LinbingWen* @Since 2015 년 8 월 29 일* @param treenode*/ public static void preordermethodone (treenode treenode) {if (null! = treenode) {treenode.data.data.data. if (null! = treenode.left) {preordermethodone (treenode.left); } if (ull! = treenode.right) {preorderMethodone (Treenode.right); }}}} / *** 선주문 트래버스를 구현하기위한 루핑* @param treenode* / public static void preordermethodtwo (treenode treenode) {if (null! = treenode) {stack <treenode> stack = new stack <treenode> (); stack.push (Treenode); while (! stack.isempty ()) {Treenode tempnode = stack.pop (); System.out.print (tempnode.data + ""); // 오른쪽 하위 노드는 NULL이 아닙니다. 오른쪽 하위 노드를 if (null! = tempnode.right) {stack.push (tempnode.right); } // 오른쪽 하위 노드를 넣은 후 왼쪽 하위 노드를 넣고 if (null! = tempnode.left) {stack.push (tempnode.left); }}}}} / *** 반복적으로 트래버스를 재귀 적으로 구현* @param treenode* / public static void medordermethodone (treenode treenode) {if (null! = treenode) {if (null! = treenode.left) {MedorderMethodone (treenode.left); } system.out.print (treenode.data + ""); if (null! = treenode.right) {MedorderMethodone (Treenode.right); }}}} / *** 루프 구현 내에서 주문 트래버스* @param treenode* / public static void medorderMethodtwo (Treenode Treenode) {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 = current.right; }}}} / *** 후 주문 후 트래버스 (@param treenode* / public static void postordermethodone) {if (null! = treenode) {if (null! = treenode.left) {postorderMethodone (treenode.left); } if (ull! = treenode.right) {postordermethodone (treenode.right); } system.out.print (treenode.data + ""); }} / *** 포스트 주문 트래버스를 구현하기위한 루핑* @param treenode* / public static void postordermethodtwo (treenode treenode) {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 (노드);
결과가 정확합니다
위의 것은 Java 이진 분류 트리에 대한 자세한 소개입니다. 모든 사람의 학습 Java 프로그래밍에 도움이되기를 바랍니다.