전차 역주행과 중차 역주행 결과에 따라 두 갈래 나무를 구성하다
기본 사고방식:
1. 앞의 반복 결과에서 하위 트리의 루트 찾기
2. 중차 반복 결과에서 좌우 트리의 결점 수량 찾기
3. 단계 1과 2를 차례로 수행하여 각 층자 나무를 구성한다
package com.cupid.algorithm.tree;
public class ConstructBinaryTree {
/**
* Construct a binary tree based on the pre-order traversal result and in-order traversal result
*
* @param preOrder The array which stores the pre-order traversal result
* @param inOrder The array which stores the in-order traversal result
* @param preBegin This index always refers to the location of roots of sub-trees
* @param preEnd This index always refers to where the end of a sub-tree is
* @param preLength How many elements of a sub-tree
* @param inBegin This index refers to where a left sub-tree begins
* @return
*/
public static BinaryTree construct(int[] preOrder,int[] inOrder,int preBegin,int preEnd,int preLength,int inBegin){
// If left or right sub-tree is empty
// simply return that empty tree.
BinaryTree myTree = new BinaryTree(null);
if(preBegin>preEnd){
return myTree;
}
// Plant a tree, specifying its root.
myTree.root = new BinaryTreeNode(preOrder[preBegin]);
// When preBegin equals preEnd,
// there is only one element(the root) in a tree,
// simply return that tree.
if(preBegin == preEnd){
return myTree;
}
int i = inBegin;
int leftCount = 0;
while(inOrder[i] != preOrder[preBegin]){
leftCount++;
i++;
}
int rightCount = preLength - leftCount -1;
myTree.root.left = construct(preOrder, inOrder, preBegin+1, preBegin + leftCount,leftCount,inBegin).root;
myTree.root.right = construct(preOrder,inOrder, preBegin + leftCount +1, preBegin + leftCount+ rightCount,rightCount,i+1).root;
return myTree;
}
public static void main(String[] args) {
int[] preOrder = new int[]{1,2,3,4,5};
int[] inOrder = new int[]{2,1,4,3,5};
//int[] preOrder = new int[]{12,13,9,4,2,8,1,6,7,3,15,5,10};
// int[] inOrder = new int[]{4,9,2,13,8,1,12,3,7,15,6,5,10};
BinaryTree myTree = construct(preOrder, inOrder,0,preOrder.length-1,preOrder.length,0);
myTree.preOrder(myTree.root);
System.out.println();
myTree.inOrder(myTree.root);
}
}
class BinaryTree{
public BinaryTreeNode root = null;
public BinaryTree(BinaryTreeNode root){
this.root = root;
}
public void inOrder(BinaryTreeNode root){
if(root!=null){
inOrder(root.left);
System.out.print(root.key + "-");
inOrder(root.right);
}
}
public void preOrder(BinaryTreeNode root){
if(root!=null){
System.out.print(root.key + "-");
preOrder(root.left);
preOrder(root.right);
}
}
}
class BinaryTreeNode{
public int key;
public BinaryTreeNode parent = null;
public BinaryTreeNode left = null;
public BinaryTreeNode right = null;
public BinaryTreeNode(int key){
this.key = key;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Access Request, Session and Application in Struts2If we want to use request, Session and application in JSP, what should we do? We can obtain Map type objects such as Req...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.