자바 일반 이 진 트 리 만 드 는 방법
그동안 데이터 구조의 지식 을 복습 해 왔 다.
가장 기본 적 인 것 부터 일반적인 이 진 트 리 를 실현 한다.하지만 발견 도 쉽 지 않 았 다.그동안 데이터 구 조 를 배 울 때 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;
}
}
이상 은 개인 적 인 경험 이 므 로 여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.