이진 트리의 분류 (저장 구조 별)
나무 분류 (저장 구조 별)
순차적 스토리지 (배열로 표시 (정적 바이너리 트리))
체인 저장
일부 특별한 이진 뿌리 :
완전한 이진 트리, 균형 이진 트리 (AVL), 단서 바이너리 트리, 트리 포크 (아버지와의 포인터)
이진 검색 트리 또는 이진 검색 트리 (BST)
사용 된 이진 트리는 다음 그림에 나와 있습니다.
이진 트리의 Java 구현 (체인 저장 구조)
클래스 Treenode {private int key = 0; 개인 문자열 데이터 = null; 개인 부울 isvisted = false; Private Treenode LeftChild = NULL; Private Treenode RightChild = NULL; public treenode () {} public treenode (int 키, 문자열 데이터) {this.key = key; this.data = 데이터; this.leftchild = null; this.rightchild = null; } public int getkey () {반환 키; } public void setkey (int key) {this.key = 키; } public String getData () {return data; } public void setData (문자열 데이터) {this.data = data; } public treenode getleftchild () {return leftchild; } public void setleftChild (Treenode LeftChild) {this.leftChild = LeftChild; } public treenode getrightchild () {Return Rightchild; } public void setrightchild (Treenode Rightchild) {this.rightchild = Rightchild; } public boolean isvisted () {return isvisted; } public void setVisted (boolean isvisted) {this.isvisted = isvisted; }} public class binarytree {private treenode root = null; public binarytree () {root = new Treenode (1, "rootnode (a)"); } public void createBintree (Treenode Root) {// 수동 생성 (구조는 그림에 표시됩니다) TREENODE NEWNODEB = NEW TREENODE (2, "B"); Treenode NewNodec = New Treenode (3, "C"); Treenode NewNoded = New Treenode (4, "D"); Treenode NewNodee = New Treenode (5, "E"); Treenode NewNodef = New Treenode (6, "F"); root.setleftchild (Newnodeb); root.setrightchild (Newnodec); root.getleftChild (). SetleftChild (NewNoded); root.getLeftChild (). SetrightChild (Newnodee); root.getrightChild (). SetrightChild (NewNodef); } public boolean isempty () {// 바이너리 트리가 비어 있는지 또는 반환되지 않은지 뿌리 == null; } public int height () {// 트리 높이 리턴 높이 (루트)를 찾습니다. } public int height (treenode subtree) {if (subtree == null) 반환 0; // 재귀 끝 : 빈 나무의 높이는 0입니다. {int i = height (subtree.getleftChild ()); int j = 높이 (subtree.getrightchild ()); 반환 (i <j)? J + 1 : i + 1; }} public int size () {// 노드 수를 찾습니다. 반환 크기 (루트); } public int size (treenode subtree) {if (subtree == null) 반환 0; else {return 1 + size (subtree.getleftchild ()) + size (subtree.getrightchild ()); }} public treenode parent (treenode element) {// 상위 노드 return (root == null || root == 요소)을 반환합니까? null : 부모 (root, element); } public treenode parent (Treenode subtree, treenode element) {if (subtree == null) return null; if (subtree.getLeftChild () == element || subtree.getrightchild () == element) // 마무리, 부모 노드 주소를 반환합니다. Treenode P; // 먼저 왼쪽 하위 트리를 봅니다. 왼쪽 하위 트리에서 찾을 수없는 경우 오른쪽 하위 트리로 이동하여 ((p = parent (subtree.getleftchild ())! = null) // return p를 재귀 적으로 검색하십시오. else // return parent (subtree.getrightchild (), element)를 재귀 적으로 검색합니다. } public Treenode LeftChild (Treenode element) {// 왼쪽 하위 트리 리턴을 반환합니다 (요소! = null)? 요소 .getleftChild () : null; } public treenode rightchild (treenode element) {// 오른쪽 하위 트리 return (element! = null)을 반환합니까? 요소 .getrightchild () : null; } public treenode getRoot () {// 루트 노드 리턴 루트를 가져옵니다. } public void destrove (treenode subtree) {// private function : root subtree (subtree! = null)로 하위 트리를 삭제합니다 (destrofe (subtree.getleftChild ()); // 왼쪽 하위 트리 삭제 (subtree.getrightchild ()); // 오른쪽 하위 트리 삭제 // 하위 트리 삭제; // 루트 노드 하위 트리 = null을 삭제합니다. }} public void traverse (treenode subtree) {system.out.println ( "key :" + subtree.getKey () + "---- name :" + subtree.getData ()); 트래버스 (subtree.getleftChild ()); 트래버스 (subtree.getrightchild ()); } public void preorder (treenode subtree) {// root first if (subtree! = null) {visted (subtree); 선주문 (subtree.getleftChild ()); 선주문 (subtree.getrightchild ()); }} public void inorder (treenode subtree) {// medium root if (subtree! = null) {inorder (subtree.getleftChild ()); Visted (subtree); 내부 (subtree.getrightchild ()); }} public void postorder (treenode subtree) {// post root if (subtree! = null) {postorder (subtree.getleftchild ()); postorder (subtree.getrightchild ()); Visted (subtree); }} public void levelorder (treenode subtree) {// Horily Periphery} public boolean insert (treenode element) {// return true; } public boolean find (treenode element) {// return true 찾기; } public void witnesed (Treenode subtree) {subtree.setVisted (true); System.out.println ( "키 :" + subtree.getKey () + "--- 나임 :" + subtree.getData ()); } public static void main (String [] args) {binarytree bt = new BinaryTree (); Bt.CreateBintree (Bt.Root); System.out.println ( "나무의 크기는" + bt.size ()); System.out.println ( "나무의 높이는" + bt.height ()); System.out.println ( "********* preorder (선주문) [ABDECF] 전송 ****************"); Bt.preorder (bt.Root); System.out.println ( "********* 중간 루트 (내수 순서) [dbeacf] 전송 ****************"); Bt.inorder (bt.Root); System.out.println ( "********* Last Root (Post Order) [Debfca] 전송 *****************"); Bt.postorder (bt.Root); }} 결과 출력 :
나무의 크기는 6입니다
나무의 높이는 3입니다
******* 첫 루트 (선주문) [abdecf] Traversal ****************
키 : 1- 이름 : 루트 노드 (a)
키 : 2- 이름 : b
키 : 4-- 이름 : d
키 : 5-- 이름 : e
키 : 3- 이름 : c
키 : 6- 이름 : f
******* 중간 뿌리 (중간 주문) [dbeacf] Traversal ******************
키 : 4-- 이름 : d
키 : 2- 이름 : b
키 : 5-- 이름 : e
키 : 1- 이름 : 루트 노드 (a)
키 : 3- 이름 : c
키 : 6- 이름 : f
******* Last Root (Post Order) [Debfca] Traversal ****************
키 : 4-- 이름 : d
키 : 5-- 이름 : e
키 : 2- 이름 : b
키 : 6- 이름 : f
키 : 3- 이름 : c
키 : 1- 이름 : 루트 노드 (a)
이 기사가 Java 프로그래밍을 공부하는 학생들에게 도움이되기를 바랍니다.