[IT 필기시험 면접 문제 정리] 두 갈래 나무의 순서와 중간 순서를 정하고 두 갈래 나무의 귀속 알고리즘을 구축한다.

4771 단어 면접 문제
【시험문제 설명】: 두 갈래 나무의 선순 중순을 정하고 두 갈래 나무의 귀속 알고리즘을 구축한다.
그 선순위 서열의 첫 번째 요소는 루트 노드이고, 그 다음은 왼쪽 트리의 선순위 서열이며, 그 다음은 오른쪽 트리의 선순위 서열이며, 고체 루트 노드는 선순위 서열에서 분리될 수 있다.중차 서열에서 확정된 루트 노드를 찾습니다. 중차 서열 특성에 따라 수건 서열에서 루트 노드 앞의 서열은 왼쪽 트리의 중차 서열이고 루트 노드 뒤의 서열은 오른쪽 트리의 중차 서열입니다.좌우 트리의 중차 서열 길이로 이 트리의 선차 서열에서 좌우 트리의 선차 서열의 경계점을 찾아 두 갈래 트리의 좌우 트리의 선차 서열을 얻을 수 있다.
귀속 실현: 귀속 함수 입력: 두 갈래 트리의 선순 서열과 중순 서열;-, 세워진 두 갈래 나무의 뿌리 노드를 되돌려줍니다.알고리즘 사상: 1) 두 갈래 나무가 비어 있으면 되돌아온다.2) 비어 있지 않으면 첫 번째 원소를 순서대로 취하여 루트 노드를 만듭니다.3) 중간 시퀀스에서 루트 노드를 찾아 좌우 하위 트리의 우선 시퀀스와 중간 시퀀스를 확인합니다.4) 자신을 차례로 호출하여 왼쪽 나무를 짓는다.5) 자신을 차례로 호출하여 오른쪽 나무를 만든다. 
[참조 코드]
 
 1 public static TreeNode createBT(String pres, String ins)

 2     {

 3         int inpos = 0;

 4         TreeNode root;

 5         String leftPres, leftIns, rightPres, rightIns;

 6 

 7         if (pres.length() == 0 || ins.length() == 0)

 8             return null;

 9         else

10         {

11             root = new TreeNode(pres.charAt(0));

12             while (ins.charAt(inpos) != root.value)

13                 inpos++;

14             leftPres = pres.substring(1, inpos + 1);

15             leftIns = ins.substring(0, inpos);

16 

17             root.left = createBT(leftPres, leftIns);

18             rightPres = pres.substring(inpos + 1, pres.length());

19             rightIns = ins.substring(inpos + 1, ins.length());

20             root.right = createBT(rightPres, rightIns);

21         }

22         return root;

23     }

24 

25 class TreeNode

26 {

27     public char value;

28     public TreeNode left;

29     public TreeNode right;

30 

31     public TreeNode(char value)

32     {

33         this.value = value;

34     }

35 }

좋은 웹페이지 즐겨찾기