두 갈래 나무가 두루 다니고 재건되다
1, 두 갈래 나무
컴퓨터 과학에서 두 갈래 나무는 매 결점마다 최대 두 개의 자목이 있는 나무 구조이다.보통 서브트리는'왼쪽 서브트리'(left subtree)와'오른쪽 서브트리'(right subtree)라고 불린다.두 갈래 나무는 두 갈래 찾기 나무와 두 갈래 더미를 실현하는 데 자주 쓰인다.
깊이가 k이고 2^k-1개의 노드가 있는 두 갈래 나무를 만 갈래 나무라고 부른다.이런 나무의 특징은 각 층의 노드 수가 최대 노드 수라는 것이다.그러나 한 그루의 두 갈래 나무 중에서 마지막 층을 제외하고 나머지 층이 모두 가득 차고 마지막 층이나 가득 차거나 오른쪽에 연속적인 몇 개의 노드가 부족하면 이 두 갈래 나무는 완전한 두 갈래 나무이다.n개의 노드가 있는 완전한 두 갈래 나무의 깊이는log2(n+1)이다.깊이가 k인 완전 두 갈래 나무는 적어도 2k-1개의 노드가 있고 많게는 2k-1개의 노드가 있다.
2 두 갈래 나무의 두루 다니기
아래 링크는 상세하게 적혀 있다
http://blog.csdn.net/xiaotan2011929/article/details/61427919 http://blog.csdn.net/Dean_Deng/article/details/47053231 http://blog.csdn.net/u014744118/article/details/50983826
3 두 갈래 나무의 재건
아래 링크는 상세하게 쓰여 있습니다.https://www.jianshu.com/p/07ac60fd2e5c http://blog.csdn.net/lemon_tree12138/article/details/49798221
중차순 + 후차순 재구성https://blog.csdn.net/wu2304211/article/details/54709205
4 코드 구현
4.1 알고리즘 사고방식: 먼저 중차적 반복과 선차적 반복이 같은 값을 찾고 이 값의 좌표는 왼쪽 트리이고 오른쪽은 오른쪽 트리이며 순환은 이 알고리즘에 귀속되면 구축을 완성할 수 있다.
단계는 다음과 같습니다.
아래 링크는 상세하게 적혀 있다
http://blog.csdn.net/xiaotan2011929/article/details/61427919 http://blog.csdn.net/Dean_Deng/article/details/47053231 http://blog.csdn.net/u014744118/article/details/50983826
3 두 갈래 나무의 재건
아래 링크는 상세하게 쓰여 있습니다.https://www.jianshu.com/p/07ac60fd2e5c http://blog.csdn.net/lemon_tree12138/article/details/49798221
중차순 + 후차순 재구성https://blog.csdn.net/wu2304211/article/details/54709205
4 코드 구현
4.1 알고리즘 사고방식: 먼저 중차적 반복과 선차적 반복이 같은 값을 찾고 이 값의 좌표는 왼쪽 트리이고 오른쪽은 오른쪽 트리이며 순환은 이 알고리즘에 귀속되면 구축을 완성할 수 있다.
단계는 다음과 같습니다.
4.1 알고리즘 사고방식: 먼저 중차적 반복과 선차적 반복이 같은 값을 찾고 이 값의 좌표는 왼쪽 트리이고 오른쪽은 오른쪽 트리이며 순환은 이 알고리즘에 귀속되면 구축을 완성할 수 있다.
단계는 다음과 같습니다.
private static TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn)
return null;
TreeNode root = new TreeNode(pre[startPre]);
for (int i = startIn; i <= endIn; i++)
if (in[i] == pre[startPre]) {
root.left = reConstructBinaryTree(pre, startPre + 1, i - startIn + startPre, in, startIn, i - 1);
root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
break;
}
return root;
}
END
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
