자바 일반 이 진 트 리 만 드 는 방법

자바 이 진 트 리 만 들 기
그동안 데이터 구조의 지식 을 복습 해 왔 다.
가장 기본 적 인 것 부터 일반적인 이 진 트 리 를 실현 한다.하지만 발견 도 쉽 지 않 았 다.그동안 데이터 구 조 를 배 울 때 C 언어 로 썼 기 때문이다.
지침 은 구조 체 의 값 조작 에 대해 비교적 이해 하기 쉽다.자바 에는 지침 이 없습니다.
노드 노드 는 방법 에서 주 소 를 전달한다.
형 삼 에 대해 직접 new 작업 을 하 는 것 은 잘못된 것 입 니 다.실제 인삼 의 값 을 바 꿀 수 없습니다.이 점 은 나 를 오랫동안 함정 에 빠 뜨 린 후에 한바탕 자 료 를 찾 았 다.
오 랜 만 에 이 구 덩이 를 메 웠 다.
다음은 재 귀적 으로 만 든 이 진 트 리 입 니 다.흔히 볼 수 있 는 트 리 의 높이 와 나무의 최대 너비 도 있 습 니 다.
4.567917.한 방법 으로 기본 데이터 형식의 매개 변 수 를 수정 할 수 없습니다4.567917.한 가지 방법 으로 대상 매개 변수의 상 태 를 수정 할 수 있다
  • 한 가지 방법 으로 대상 매개 변수 가 새로운 대상 을 인용 하 는 것 을 실현 하지 못 한다(이 말 은 여기 서 특히 적용 된다)
  • 코드 의 이 진 트 리 는 아래 그림 과 같 습 니 다.
    二叉树
    다음은 아주 간단 한 실현 입 니 다.
    여기 에는 다음 출력 형식 을 위해 JDK 의 동적 프 록 시 를 사 용 했 습 니 다.인 터 페 이 스 를 하나 썼어 요.
    
    package test.tree; 
    public interface AbstractBinaryTree {
     void printPostOder(); 
     void printPostOderByRecursion(); 
     void printPreOder(); 
     void printPreOderByRecursion(); 
     void printInOderByRecursion(); 
     void printInOder(); 
     void printHeight(); 
     void printMaxWidth(); 
     void printLevelOrder();
    }
    주요 코드
    
    package test.tree; 
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
     
    /**
     *       ,    Node    
     */
     
    class Node { 
    	public String data;
    	public Node left = null;
    	public Node right = null;
    	public boolean flag;
     
    	Node(String data) {
    		this.data = data;
    	}
     
    	Node() {
    	} 
    	@Override
    	public String toString() { 
    		return this.data;
    	} 
    }
     
    public class BinaryTree implements AbstractBinaryTree{ 
    	private Node root = new Node(); 
    	public Node getRoot() {
    		return root;
    	}
     
    	public void printNode(Node node) {
     
    		if (node.data == null) {
    			System.out.print("");
    		} else {
    			System.out.print(node.data);
    		}
    	}
     
    	public BinaryTree(String tree) {
    		String[] treeNodes = tree.split(",");
    		createTreeByRecursion(treeNodes);
    	}
     
    	private int createTreeByRecursion(Node node, String[] treeNodes, int n) { 
    		if ("#".equals(treeNodes[n]))
    			return n + 1; 
    		node.data = treeNodes[n]; 
    		node.left = new Node();
    		int left = createTreeByRecursion(node.left, treeNodes, n + 1); 
    		node.right = new Node();
    		int right = createTreeByRecursion(node.right, treeNodes, left); 
    		return right;
    	}
     
    	public void createTreeByRecursion(String[] treeNodes) {
    		createTreeByRecursion(root, treeNodes, 0);
    	}
     
    	/**
    	 *        
    	 */
    	public void createTree(String[] treeNodes) { 
    		Stack<Node> stack = new Stack<>(); 
    		int index = 0; 
    		Node node = root; 
    		while (index < treeNodes.length) { 
    			while (true) {
     
    				if ("#".equals(treeNodes[index])) {
     
    					node = stack.pop();
     
    					if (node.flag == false) {
    						node.left = null;
    						node.flag = true;
    						stack.push(node);
    					} else {
    						node.right = null;
    					}
     
    					//    1
    					index++;
    					break;
    				}
     
    				if (node.flag == true) {
    					node.right = new Node();
    					node = node.right;
    				}
     
    				node.data = treeNodes[index];
    				stack.push(node);
    				node.left = new Node();
    				node = node.left;
    				index++;
    			}
     
    			if (node.flag == false) {
    				stack.push(node);
    				node.flag = true;
    				node = node.right;
    			} else {
    				node = stack.peek();
    				node.flag = true;
    			} 
    		} 
    	}
     
    	//        ,   root    
    	private void printPreOderByRecursion(Node node) { 
    		if (node == null)
    			return; 
    		printNode(node);
    		printPreOderByRecursion(node.left);
    		printPreOderByRecursion(node.right); 
    	}
     
    	public void printPreOderByRecursion() { 
    		printPreOderByRecursion(root);
    	}
     
    	private void printInOderByRecursion(Node node) {
     
    		if (node == null)
    			return;
     
    		printInOderByRecursion(node.left);
    		printNode(node);
    		printInOderByRecursion(node.right); 
    	}
     
    	public void printInOderByRecursion() {
    		printInOderByRecursion(root);
    	}
     
    	private void printPostOderByRecursion(Node node) {
     
    		if (node == null)
    			return; 
    		printPostOderByRecursion(node.left);
    		printPostOderByRecursion(node.right);
    		printNode(node); 
    	}
     
    	public void printPostOderByRecursion() { 
    		printPostOderByRecursion(root);
    	}
     
    	//         
     
    	//     
    	public void printPreOder() { 
    		Stack<Node> stack = new Stack<>(); 
    		Node tempNode = root; 
    		while (true) { 
    			while (tempNode != null) {
    				printNode(tempNode);
    				stack.push(tempNode);
    				tempNode = tempNode.left;
    			}
     
    			if (stack.isEmpty()) {
    				break;
    			} 
    			tempNode = stack.pop();
    			tempNode = tempNode.right; 
    		} 
    	}
     
    	//     
    	public void printInOder() { 
    		Stack<Node> stack = new Stack<>(); 
    		Node tempNode = root;
     		while (true) { 
    			while (tempNode != null) {
    				stack.push(tempNode);
    				tempNode = tempNode.left;
    			}
     
    			if (stack.isEmpty()) {
    				break;
    			}
    			tempNode = stack.pop();
    			printNode(tempNode);
    			tempNode = tempNode.right; 
    		} 
    	}
     
    	//     
    	public void printPostOder() { 
    		Stack<Node> stack = new Stack<>(); 
    		Node tempNode = root; 
    		while (true) {
     
    			while (tempNode != null) {
    				if (tempNode.flag == true) {
    					tempNode = tempNode.right;
    				} else {
    					stack.push(tempNode);
    					tempNode = tempNode.left;
    				} 
    			}
     
    			tempNode = stack.pop(); 
    			if (tempNode.flag == false) {
    				stack.push(tempNode);
    				tempNode.flag = true;
    				tempNode = tempNode.right;
    			} else {
    				printNode(tempNode);
    				if (stack.isEmpty()) {
    					break;
    				}
    				tempNode = stack.peek();
    				tempNode.flag = true;
    			} 
    		} 
    	}
     
    	//          
    	public void printLevelOrder() { 
    		Queue<Node> queue = new LinkedList<>(); 
    		Node tempNode = root; 
    		queue.offer(tempNode); 
    		while (!queue.isEmpty()) { 
    			Node topNode = queue.poll(); 
    			if (topNode == null)
    				continue; 
    			printNode(topNode);
    			queue.offer(topNode.left);
    			queue.offer(topNode.right); 
    		} 
    	}
     
    	//      ,          、      ,        +1
    	public int getHeightByRecursion(Node node) { 
    		if (node == null) {
    			return 0;
    		}
    		int left = getHeightByRecursion(node.left);
    		int right = getHeightByRecursion(node.right);
    		return 1 + Math.max(left, right); 
    	}
     
    	/**
    	 *            root,               ,       root,             
    	 *             ,          
    	 */
     
    	public void printHeight() { 
    		int height = getHeightByRecursion(root); 
    		System.out.print(height);
    	}
     
    	//       ,        
    	public void printMaxWidth() { 
    		Queue<Node> queue = new LinkedList<>();
    		Queue<Node> queueTemp = new LinkedList<>();
     
    		int maxWidth = 1; 
    		Node tempNode = root; 
    		queue.offer(tempNode); 
    		while (!queue.isEmpty()) { 
    			while (!queue.isEmpty()) { 
    				Node topNode = queue.poll(); 
    				if (topNode == null)
    					continue; 
    				if (topNode.left.data != null) { 
    					queueTemp.offer(topNode.left);
    				}
     
    				if (topNode.right.data != null) { 
    					queueTemp.offer(topNode.right);
    				} 
    			}
     
    			maxWidth = Math.max(maxWidth, queueTemp.size());
    			queue = queueTemp;
    			queueTemp = new LinkedList<>();
    		} 
    		System.out.print(maxWidth);
    	} 
    }
    다음은 테스트 클래스 입 니 다.
    
    package test.tree; 
    import java.lang.reflect.Proxy; 
    public class BinaryTreeTest {
     
    	public static void main(String[] args) {
    		String treeStr = "A,B,D,#,#,#,C,#,E,#,#";
    		// String treeStr = "A,#,#";
    		AbstractBinaryTree binaryTree =  BinaryTreeTest.proxyBinaryTree(treeStr); 
    		binaryTree.printPostOder();
    		binaryTree.printPostOderByRecursion();
    		binaryTree.printPreOder();
    		binaryTree.printPreOderByRecursion();
    		binaryTree.printInOderByRecursion();
    		binaryTree.printInOder();
    		binaryTree.printLevelOrder();
    		binaryTree.printHeight();
    		binaryTree.printMaxWidth();
    	}
     
    	public static AbstractBinaryTree proxyBinaryTree(String treeStr) {		
    		AbstractBinaryTree binaryTree = new BinaryTree(treeStr); 
    		Object newProxyInstance = Proxy.newProxyInstance(binaryTree.getClass().getClassLoader(),
    				binaryTree.getClass().getInterfaces(), (proxy, method, args) -> {
    					System.out.println(method.getName());
    					Object invoke = method.invoke(binaryTree, args);
    					System.out.println();
    					return invoke;
    				});
    		
    		return (AbstractBinaryTree) newProxyInstance;
    	} 
    }
    이상 은 개인 적 인 경험 이 므 로 여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.

    좋은 웹페이지 즐겨찾기