데이터 구조 기반 의 이 진 트 리 깊이 우선 옮 겨 다 니 기, 넓이 우선 옮 겨 다 니 기
1552 단어 데이터 구조
이 진 트 리 는 무엇 입 니까?
나무의 각 노드 에는 최대 두 개의 아이 노드 가 있다.
주의 하 세 요. 최대 2 개, 1 개 또는 0 개 일 수도 있 습 니 다.
모든 비 잎 노드 는 좌우 아이 가 존재 하고 모든 잎 노드 는 같은 등급 에 있다 (이곳 의 잎 노드 는 특정한 나무의 뿌리, 즉 이 나무의 마지막 층 이 되 지 않 았 다).
이 진 트 리 의 모든 가지 가 가득 하 다.
마지막 잎 사 귀 노드 앞 에 있 는 모든 노드 가 꽉 찼 다.
나 무 는 비 선형 데이터 구조 로 이 진 트 리 는 링크 와 배열 로 표현 할 수 있다.
체인 메모리 구조:
각 노드 는 세 부분 을 포함한다.
층계 순서에 따라 이 진 트 리 의 노드 를 배열 에 대응 하 는 위치 에 놓 아 라.한 노드 의 왼쪽 아이 나 오른쪽 아이 가 비어 있 으 면 배열 의 해당 위치 도 비어 있다.
부모 노드 아래 표 시 를 parent 라 고 가정 하면 왼쪽 아이 아래 표 시 는 2 입 니 다.×parent + 1, 오른쪽 아이 아래 표 시 는 2 입 니 다.×parent+2
Note: 희소 한 이 진 트 리 에 있어 서 배열 표현 법 을 사용 하 는 것 은 공간 을 낭비 하 는 것 입 니 다.
이 진 트 리 의 일반적인 동작: 찾기, 상대 순서 유지
이 진 트 리 찾기 (): 이 나무의 왼쪽 트 리 는 부모 노드 보다 작고 오른쪽 트 리 는 부모 노드 보다 크 며 이 진 트 리 의 질서 성 을 확보 합 니 다.
이 진 트 리 자체 균형 방식: 붉 은 검 은 나무, AVL 나무, 나무 더미 등
깊이 우선 순위:
1. 앞 순 서 를 옮 겨 다 니 기: 출력 순 서 는 뿌리 노드, 왼쪽 트 리, 오른쪽 트 리 입 니 다.
2. 중간 순서 옮 겨 다 니 기: 출력 순 서 는 왼쪽 하위 트 리, 뿌리 노드, 오른쪽 하위 트 리 입 니 다.
3. 후 순 옮 겨 다 니 기: 출력 순 서 는 왼쪽 하위 트 리, 오른쪽 하위 트 리, 뿌리 노드
/**
*
*@param inputList
*/
public static TreeNode createBinaryTree(LinkedListinputList){
TreeNode node=null;
if(inputList==null || inputList.isEmpty()){
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.