Java는 트리 구조 데이터의 귀속과 비귀속을 실현한다

1513 단어 Java 기반

트리 구조의 귀속과 비귀속의 두루


귀환은 많은 상황에서 우리가 사용한다. 예를 들어 유명한 한노타 문제, 이분 찾기 등이다. 때때로 우리가 나무 데이터 구조를 두루 훑어본 데이터도 귀환에 필요하지만 절대적인 것은 아니다.원인은 한 그루의 나무 구조를 반복하는 데이터를 예로 들면 반복은 현재의 방법을 끊임없이 사용하고 깊이 있게 반복하는 방식으로 한 갈래 길을 따라 끝까지 가다가 다음 갈래 길을 다시 집행하기 때문이다.이런 상황에서 현재 방법을 호출한 후에 컴파일러는 이 방법의 모든 매개 변수와 되돌아오는 주소를 창고에 압입한다. 이런 상황에서 현재 라인이 현재 방법을 다시 한 번 호출하면 이 브랜치가 충분하게 깊어지면 축적된 창고의 내용이 점점 많아지고 메모리가 넘칠 때까지 계속된다.
따라서 트리 데이터의 구조가 충분할 때 우리는 다른 방법으로 이 데이터를 훑어보아야 한다. 이런 방법은 너비를 통해 나무의 꼭대기부터 훑어보고 이 층을 훑어본 다음에 다음 층을 훑어보고 현재 층을 훑어본 다음에 다음 층을 훑어보고 순서대로 아래로 훑어보는 것이다. 이런 방식은while 순환으로 실현할 수 있다.
트리 구조의 데이터를 반복하는 Java 유사 코드:
//  
TreeNode parent; //  
public void traverse(TreeNode parent) {
	List childs = getChilds(parent); // parent 
	if (childs != null) {
		for (child : childs) {
			// ------------
			//  child ， 
			// ------------
			traverse(child);
		}	
	}
}
private List getChilds(TreeNode parent) {
	//  
}

다음은 트리 구조의 데이터에 대한 반복되지 않는 Java 유사 코드입니다.
//  
TreeNode parent; //  
List childs = getChilds(parent); // parent 
while (childs != null) {
	List tempChilds;
	for (child : childs) { //  
		// ------------
		//  child ， 
		// ------------
		if (getChilds(child) != null) {
			tempChilds.add(child);
		}
	}
	childs = tempChilds;
}
private List getChilds(TreeNode parent) {
	//  
}

이상의 내용은 참고만 제공할 뿐, 만약 의문이나 착오가 있으면, 모두가 함께 진보하기를 바랍니다.

leetcode 문제집 894-가능한 모든 두 갈래 나무
[Rails] where의 반환값에 대한 이야기를 주의하세요.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage