재귀 적으로 정의 된 문자열 표기법을 사용하여 이진 트리를 작성합니다.

Question

저는 몇 시간 동안이 문제에 고심하고 있습니다. 그래서 계속해서 인터넷 검색을하고 조금만 찾은 후에, 결국 어떤 종류의 도움이 필요 할지를 알기로 결정했습니다. 내 최신 CS 한 조각. 은 ((루트) (left_subtree) (right_subtree가))

일치하는 괄호의 각 세트는 나무를 나타냅니다

우리의 과제는이 같은 형식으로 우리에게 주어진 이진 나무에서 읽고 저장하는 것입니다 , 가장 먼저 루트이고, 다음은 왼쪽 하위 트리이고, 그 다음 오른쪽 하위 트리입니다. 하위 트리는 꺾인 경우 괄호로 묶을 필요는 없지만 될 수는 있습니다. 그 의미를 명확히하기 위해 다음 예제를 참조하십시오.이 예제는 코드 블록 아래에 그려진 트리의 모든 유효한 표현입니다. 정의 조금 더 나은의 재귀 적 특성을 설명하는 더 복잡한 예를 들어

a tree http://faculty.otterbein.edu/psanderson/csc205/notes/binaryTreeABC.jpg

(A B C) 
(A (B) C) 
(A B (C)) 
((A) (B) (C)) 

다음 트리에 대한 하나의 가능한 문자열은 다음과 같습니다

(F(B A (D C E)) (G() (I (H)))) 

주에 그 F [즉 "(G() (I (H)))"], G 뒤에 빈 왼쪽 자식을 나타 내기 위해 "()"가 필요하다. 그러나 G [ "(I) 더 단순하게 "(IH)"로 표현 될 수도있다.

나는 (과의 TreeNode 클래스 일치)이 입력에서 트리의 구축에 필수적인 기능을 제외하고 완료 이진 트리 클래스를 가지고,하지만 난 얼마나 정확하게에 주위에 내 머리를 정리하고 수없는 것 문자열을 파싱합니다. 나는 그것을하는 방법에 대한 일반적인 생각을 가지고있다 - 최소한 재귀가 어떻게 작동하는지 - 문제를 작은 부분으로 나누는 것이 정확히 내 머리 위로 가고 있는지.

//pseudocode musings 
TreeNode* Tree::buildFromString(string s){ 
TreeNode* temp = NULL 
if (the string doesn't represent an empty tree) 
    temp = new TreeNode 
    temp->data = part of s representing root 
    temp->leftChild = buildFromString(part of s representing left subtree) 
    temp->rightChild = same as above, but with right subtree  
} 
return temp; 

재귀 자체에 문제가 없습니다. 머리 속에 대략 추적하기가 어렵지 않습니다. 기본 케이스가 작동합니다 - 재귀에서 벗어나서 잎 노드에 도달하면 호출을 백업하고 다시 돌아갈 때 하위 트리를 연결합니다.

하지만 분명히 재귀의 전체 지점 인 코드에서 문제를 작은 조각으로 나누는 방법을 알 수는 없습니다. 재귀 호출에 전달할 원본의 하위 문자열을 만들고 싶지만 적절한 조각을 얻는 방법에 대해 머리를 감싸는 것처럼 보이지 않습니다.

어떤 아이디어가 있습니까?

Answer 1

당신은 어떤 누락 된 것은, 바로 수 있습니다, 그것은 루트 'A'되는 다음, 나무를 시작합니다 '('

• 문자열로 시작하면
• 이 경우, 예를 들어, ' B는 ('다음 인 경우
• 를 재귀') '가있는 경우, 그 잎
• 이다' '봉쇄 노드는 위의