이진 분류 트리를 이진 검색 트리라고도합니다. 빈 나무 또는 다음 특성이있는 이진 트리입니다.
왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리의 모든 노드 값이 루트 노드 값보다 작습니다.
오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리의 모든 노드의 값이 루트 노드의 값보다 큽니다.
왼쪽 및 오른쪽 하위 트리는 각각 이진 분류 트리입니다.
다음 코드 구현 :
import java.util.linkedList; import java.util.queue; 클래스 노드 {public int data; 공개 노드 왼쪽; 공개 노드 오른쪽; 공개 intmaxdistance; 대중의 옳은 일관성; public node (int data) {this.data = data; this.left = null; this.right = null; }}/*** @author ty* 삽입, 내선 순서, 선주문 트래버스, 우편 주문 후 트래버스 및 모든 노드의 최대 거리 계산을 포함하여 이진 분류 트리 구현*/public class binarytree {private node root; public binarytree () {root = null; } public void insert (int data) {node newnode = 새 노드 (data); if (root == null) root = newnode; else {노드 전류 = 루트; 노드 부모; while (true) {// 삽입 위치 position parent = current; if (data <current.data) {current = current.left; if (current == null) {parent.left = newnode; 반품; }} else {current = current.right; if (current == null) {parent.right = newnode; 반품; }}}}}}} // 이진 트리 공개 void buildTree (int [] data) {for (int i = 0; i <data.length; i ++) {insert (data [i]); }}} // 내 주문형 트래버스 메소드는 공개 무효 인더 (node localRoot) {if (localRoot! = null) {inorder (localRoot.Left); System.out.print (localRoot.Data+""); 내부 (LocalRoot.right); }} public void inorder () {this.inorder (this.root); } // 선주문 트래버스 메소드는 공개 void preorder (node localRoot) {if (localRoot! = null) {System.out.print (localRoot.Data+"")를 재귀 적으로 구현합니다. 선주문 (localRoot.Left); 선주문 (LocalRoot.right); }} public void preorder () {this.preorder (this.root); } // 우편 주문형 Traversal 메소드는 공개 void postorder (node localRoot) {if (localRoot! = null) {postOrder (localRoot.Left); 우체류 (LocalRoot.right); System.out.print (localRoot.Data+""); }} public void postorder () {this.postorder (this.root); } /*** 레이어 시퀀스 트래버스 바이너리 트리 : 이제 루트 노드를 큐에 넣은 다음 매번 큐에서 노드를 가져와 노드 값을 인쇄합니다. *이 노드가 하위 노드가있는 경우 큐가 비어있을 때까지 하위 노드를 큐의 꼬리에 넣으십시오*/ public void layertranverse () {if (this.root == null) return; 큐 <NODE> Q = NEW LINKEDLIST <NODE> (); Q.add (this.root); while (! q.isempty ()) {node n = q.poll (); System.out.print (n.data+""); if (n.left! = null) q.add (n.left); if (n.right! = null) q.add (n.right); }} private int maxlen = 0; 개인 int max (int a, int b) {return a> b? a : b; } public void findmaxDistance (노드 루트) {if (root == null) return; if (root.left == null) root.leftMaxDistance = 0; if (root.right == null) root.rightMaxDistance = 0; if (root.left! = null) findMaxDistance (root.left); if (root.right! = null) findMaxDistance (root.right); // 왼쪽 단어 트리의 루트 노드에서 최대 거리는 (root.left! = null) root.leftMaxDistance = max (root.left.leftmaxdistance, root.left.rightmaxdistance) +1; // 오른쪽 단어 트리의 루트 노드에서 최대 거리를 계산하면 (root.right! = null) root.rightMaxDistance = max (right.right.leftmaxdistance, root.right.rightmaxdistance) +1; // 이진 트리의 모든 노드의 최대 거리는 if (root.leftMaxDistance+root.rightMaxDistance> maxlen) {maxlen = root.leftMaxDistance+root.rightMaxDistance; }} public static void main (String [] args) {binarytree bitree = new BinaryTree (); int [] data = {2,8,7,4,9,3,1,6,7,5}; bitree.buildtree (데이터); System.out.print ( "이진 트리의 순차 순관 :"); bitree.inorder (); System.out.println (); System.out.print ( "이진 트리의 선주문 순서 :"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ( "이진 트리의 우편 순서 트래버스 :"); bitree.postorder (); System.out.println (); System.out.print ( "이진 트리의 레이어 주문 트래버스 :"); bitree.layertranverse (); System.out.println (); bitree.findmaxdistance (bitree.root); System.out.println ( "이진 트리의 노드의 최대 거리 :"+bitree.maxlen); }}위는이 기사의 모든 내용입니다. 이 기사의 내용이 모든 사람의 연구 나 업무에 도움이되기를 바랍니다. 또한 wulin.com을 더 지원하기를 바랍니다!