다음은 C에서의 표현 ++

empty tree ::=() 
tree ::= empty tree | (w tree tree) 
ex: 
() 
empty tree 

(99(5()())(35(-5()())())) 

    99 
    /\ 
    5 35 
    /
    -5 

class Node 
{ 
public: 
    int weight; // weight can be negative! 
    Node *left, *right; 
    Node():weight(0),left(NULL),right(NULL){} 
    Node(int d):weight(d),left(NULL),right(NULL){} 
};

이다음은 C에서의 표현 ++

은 내가, 내 프로그램이 호감 구조와 문제를 얻고 나는 그것이 일어난 이유에 대해 아무 생각이 주어진 조건에 의해 이진 트리를 구축에서 이진 트리를 구축 내 코드와 나는 디버그를위한 정보를 출력하고 테스트 케이스로 99 (5()()) (35 (-5()())))를 출력하면 99 (5 , 내가 어쩌면 문제가 어디에서 내가 NULL을 노드를 반환하는 것 같아요)하지만 문제가 찾을 수 없습니다.이 트리는 각 트리에 노드의 무리를 처리 할 것으로 예상되며 각 테스트 케이스에 최대 10 개 나무가 포함되어 있습니다.이 프로그램을 사용하여 시간이 얼마 남지 않았습니까? 아니면 무엇을해야합니까?

Node* MyBinaryTreeOps::constructTree(Node *root, std::string treeStr)const 
{ 
    int idex = 1;//always look at the treeStr[1] 
    Node *cur=NULL;//use to pass in recursive call 
    if(treeStr[idex]!='('&&treeStr[idex]!=')'){//meet number create new node 
     stringstream ss; 
     while(treeStr[idex]!='('){ 
      ss<<treeStr[idex]; 
      if(treeStr.size()>1){//if size > 1 then remove the treeStr[1],to let treeStr[1] become next char in treeStr 
       treeStr.erase(1,1); 
      } 
     } 
     int num=0; 
     ss>>num; 
     std::cout<<num<<std::endl;//print out just for debug 
     std::cout<<treeStr[idex]<<std::endl;//print out just for debug 
     root = new Node(num); 
    } 

    if(treeStr[idex]==')'){//meet ')' return subtree constructed 
     if(treeStr.size()>1){ 
     treeStr.erase(1,1); 
     } 
     return root; 
    } 
    if(treeStr[idex]=='('){//meet first '(' then construct left subtree 
     if(treeStr.size()>1){ 
      treeStr.erase(1,1); 
     } 

     root->left = constructTree(cur,treeStr); 

    } 

    if(treeStr[idex]=='('){ //meet second '(' then construct right subtree 
     if(treeStr.size()>1){ 
      treeStr.erase(1,1); 
     } 
     root->right = constructTree(cur,treeStr); 

    } 
    if(treeStr[idex]==')'){ //meet ')' return subtree constructed 
     if(treeStr.size()>1){ 
      treeStr.erase(1,1); 
     } 
     return root; 
    } 
}

출처

2016-11-18 jasmine

본인이 직접이 문제를 시도했으며이 기능은 내가 작성한 기능입니다. 알고리즘

단계 :

현재 노드의 중량을 나타내는 시퀀스의 부분을 찾는다. 그것을 int로 변환하고 노드에 할당하십시오.
무게, 시작 및 끝 중괄호를 제거하기위한 슬라이스 문자열.
시퀀스를 반복하여 자식 노드를 나눌 두 중괄호 사이의 점을 찾습니다.
두 개의 시퀀스로 문자열을 분할합니다 (시작 트리를 슬라이스하여 자식 노드 중 하나의 시퀀스로 다시 사용할 수 있음).

자식 노드의 가중치 (시퀀스 길이가 2보다 큰 경우)는 새 노드 및 반복 알고리즘을 만듭니다. http://www.tutorialspoint.com/compile_cpp11_online.php?PID=0Bw_CjBb95KQMLV9wcjBhTjdmMFU

Node* constructTree(Node* root, std::string& treeString) { 
    // Find the weight of this node. 
    auto weightLeft = treeString.find_first_of("(") + 1; 
    auto weightRight = treeString.find_first_of("()", weightLeft); 
    auto weightString = treeString.substr(weightLeft, weightRight - weightLeft); 

    // Optional, we check if there is any weight, if there is not we leave zero 
    // weight from constructor. 
    // Works for something like that: ((1)(2)) -> (0(1)(2)) 
    if (weightString.length() > 0) { 
     root->weight = std::stoi(weightString); 
    } 

    // Slice string to contain only children sequences. 
    treeString.erase(0, weightRight); 
    treeString.erase(treeString.length() - 1, 1); 

    // Looking for index in string where a left child ends and a right child starts. 
    // This point(index) is located where count of left braces and for braces 
    // is the same and the counts are not zero. 
    int splitPoint = -1; 
    int leftBraces = 0, rightBraces = 0; 
    for (int index = 0; index < treeString.length(); index++) { 
     char c = treeString[index]; 
     if (c == '(') { 
      ++leftBraces; 
     } 
     if (c == ')') { 
      ++rightBraces; 
     } 

     if (leftBraces == rightBraces) { 
      splitPoint = index + 1; 
      break; 
     } 
    } 

    // If split point has been found then it means that this node has children. 
    if (splitPoint != -1) { 
     auto leftChildString = treeString.substr(0, splitPoint); 
     auto rightChildString = treeString.erase(0, splitPoint); 

     // Check for length so construct will stop if there is no child. 
     if (leftChildString.length() > 2) { 
      root->left = new Node(); 
      constructTree(root->left, leftChildString); 
     } 

     if (rightChildString.length() > 2) { 
      root->right = new Node(); 
      constructTree(root->right, rightChildString); 
     } 
    } 

    return root; 
}

또한, 여기 내 프로그램은 몇 가지 테스트 예제와 약간 확장 된 노드 클래스입니다

출처

2016-11-18 16:25:13 Nuurek

다음은 C에서의 표현 ++

답변

관련 문제