알고리즘 시리즈 (7) 데이터 구조의 트 리 의 기본 구조 와 이 진 트 리 의 옮 겨 다 니 기

개술
알고리즘 시리즈 (6) 데이터 구조의 표 대기 열 과 스 택 한 글 에서 데이터 구조 중의 기본 선형 데이터 구 조 를 소개 했다.대량의 데이터 에 대해 링크 접근 시간 이 너무 느 리 고 배열 삽입 삭제 시간 이 너무 느리다.우 리 는 데이터 구조 트 리 에 대해 토론 합 시다.트 리 구조의 대부분 작업 평균 실행 시간 은 O (logN) 입 니 다.
나무 정의
나 무 는 n (n > = 1) 개의 유한 노드 로 차원 관 계 를 가 진 집합 을 구성한다.
각 노드 에 0 개 이상 의 키 노드 가 있다.부모 노드 가 없 는 노드 를 뿌리 노드 라 고 한다.모든 비 근 노드 가 있 고 부모 노드 만 있 습 니 다.뿌리 노드 를 제외 하고 모든 하위 노드 는 서로 교차 하지 않 는 여러 개의 하위 나무 로 나 눌 수 있다.
3. 나무의 구조
각 노드 마다 하나의 사슬 이 형 제 를 가리 키 고 다른 사슬 은 아들 을 가리킨다.

package com.algorithm.tree;

/**
 *    
 * 
 * @author chao
 *
 * @param <T>
 */
public class TreeNode<T> {
	public T element;
	public TreeNode<T> firstchild;
	public TreeNode<T> nextSibling;
}

나무
매우 전형 적 인 응용 장면 은 바로 운영 체제 의 디 렉 터 리 구조 이다.
디 렉 터 리 에 있 는 모든 파일 을 찾 는 것 이 트 리 를 옮 겨 다 니 는 과정 입 니 다.이 알고리즘 도 전형 적 인 재 귀 알고리즘 으로 전형 적 인 깊이 검색 이다.

package com.algorithm.tree;

import java.io.File;
import java.util.ArrayList;

public class FindAllFile {
	private ArrayList<File> files = new ArrayList<>();

	public ArrayList<File> getFiles() {
		return files;
	}

	public void findAllFiles(File file) {
		if (file == null) {
			return;
		} else if (file.isFile()) {
			files.add(file);
		} else {
			for (File curfile : file.listFiles()) {
				findAllFiles(curfile);
			}
		}
	}

	public static void main(String[] args) {
		FindAllFile filefinder = new FindAllFile();
		filefinder.findAllFiles(new File("D:\\code\\git\\simplealgorithm\\bin"));
		System.out.println(filefinder.getFiles());
	}
}

다섯, 두 갈래 나무
이 진 트 리 는 가장 기본 적 인 나무 구조 로 모든 노드 는 왼쪽 나무 하나, 오른쪽 나무 하나 밖 에 없다.만약 그것 의 좌우 자나무 노드 가 모두 비어 있다 면, 그 는 바로 이 두 갈래 나무의 잎 노드 이다.만약 이 노드 의 아버지 노드 가 비어 있다 면, 그것 은 바로 이 나무의 뿌리 노드 이다.
6. 이 진 트 리 의 실현 과 옮 겨 다 니 기

package com.algorithm.tree;

/**
 *    
 * 
 * @author chao
 *
 * @param <T>
 */
public class BinaryTree<T> {
	private BinaryTreeNode<T> root;

	public static class BinaryTreeNode<T> {
		public T element;
		public BinaryTreeNode<T> left;
		public BinaryTreeNode<T> right;
	}

	public BinaryTree(BinaryTreeNode<T> root) {
		this.root = root;
	}

	public BinaryTreeNode getRoot() {
		return root;
	}

	/**
	 *     LDR
	 */
	public void inOrderTraversal(BinaryTreeNode<T> node) {
		if (node == null) {
			return;
		} else {
			inOrderTraversal(node.left);
			System.out.println(node.element);
			inOrderTraversal(node.right);
		}
	}

	/**
	 *     DLR
	 */
	public void firstOrderTraversal(BinaryTreeNode<T> node) {
		if (node == null) {
			return;
		} else {
			System.out.println(node.element);
			firstOrderTraversal(node.left);
			firstOrderTraversal(node.right);
		}
	}

	/**
	 *     LRD
	 */
	public void lastOrderTraversal(BinaryTreeNode<T> node) {
		if (node == null) {
			return;
		} else {
			lastOrderTraversal(node.left);
			lastOrderTraversal(node.right);
			System.out.println(node.element);
		}
	}

}

이상 은 나무의 기초 입 니 다. 나무의 비 재 귀적 옮 겨 다 니 거나 층 차 를 옮 겨 다 니 며 쓰 지 않 았 습 니 다.추 후 github 에 보충 하 겠 습 니 다.
이 진 트 리 는 두 가지 라 이브 러 리 집합 류 트 리 셋 과 트 리 맵 의 기초 이 고 이 진 트 리 는 특수 한 이 진 트 리 입 니 다.나중에 설명 하 겠 습 니 다.
코드 구현 github, 주소 볼 수 있 습 니 다.https://github.com/robertjc/simplealgorithm
github 코드 도 계속 보완 되 고 있 습 니 다. 일부 부분 에 문제 가 있 을 수 있 으 니 잘 부탁드립니다.
QR 코드 스 캔 을 환영 합 니 다.