C++ 바이너리 검색 트리를 인쇄하십시오.

Question

크리스마스 휴가를 더 잘 처리 할 수있는 방법이 없으므로 이진 검색 트리를 만들어보기로했습니다. 인쇄 기능이 붙어 있습니다. 그것의 논리는 어떻게 작동해야합니까? 트리는 이미 다소 정렬 된 순서로 그것을 삽입하고 있으므로 가장 작은 값에서 가장 큰 값으로 트리를 인쇄하려고합니다.

그래서 첫 번째 값을 인쇄하려면 트리의 가장 먼 왼쪽 분기로 이동해야합니다. 그렇습니다. 그 후에 어떻게 백업 방식을 기억합니까? 이전 노드를 저장해야합니까? 위키 피 디아 (Wikipedia)에서 검색을하면 스택을 사용하는 해결책이 생겼습니다. 그리고 다른 솔루션을 나는 그들이 어떻게 만들 었는지 이해할 수 없었습니다. 그래서 나는 대신 누군가가 나를 밝힐 수 있기를 바라고 있습니다.

필자의 삽입 기능이 정상적으로 작동하는지 궁금합니다. 나는 다른 사람의 해결책이 더 작은 것을 보았다.

void treenode::insert(int i) 
{ 

    if(root == 0) 
    { 
     cout << "root" << endl; 
     root = new node(i,root); 
    } 
    else 
    { 
     node* travel = root; 
     node* prev; 
     while(travel) 
     { 
     if(travel->value > i) 
     { 
      cout << "travel left" << endl; 
      prev = travel; 
      travel = travel->left; 
     } 
     else 
     { 
      cout << "travel right" << endl; 
      prev = travel; 
      travel = travel->right; 
     } 
     } 
     //insert 
     if(prev->value > i) 
     { 
     cout << "left" << endl; 
     prev->left = new node(i); 
     } 
     else 
     { 
     cout << "right" << endl; 
     prev->right = new node(i); 
     } 
    } 

} 

void treenode::print() 
{ 

    node* travel = root; 
    while(travel) 
    { 
     cout << travel->value << endl; 
     travel = travel->left; 
    } 

} 

Answer 1

당신은 재귀 (의사)를 사용할 수 있습니다 :

prin-tree(node): 
    print-tree(left-subnode) if exists 
    print(node-value) 
    print-tree(right-subnode) if exists 
... 
print(root-of-tree) 

Answer 2

전통적인 CS101의 방법 (인쇄, 검색, 삽입 등) 아무것도 할 이진 트리를 탐색하는 것은 재귀를 사용하는 것입니다. (어떤 것이 든) 루틴이 현재 노드를 검사하도록하고, 그 노드가 찾고있는 루틴이 아닌 경우 왼쪽 및/또는 오른쪽 하위 트리가있는 경우 자체를 호출합니다.

좋은 토론을 원하면 psedocode와 함께 the Wikipedia article on tree traversal을 확인하십시오. 심지어 삽입하는 방법과 일치하는 회귀없이 하는 방법을 보여줍니다.

Answer 3

모두 트리의 정의에 따라 다릅니다. 노드가 부모로 돌아가는 포인터를 포함하지 않으면 스택을 사용하여 순서대로 횡단을 인쇄해야합니다. 가장 간단한 방법은 응용 프로그램의 스택을 사용하는 재귀 함수를 작성하는 것입니다. 노드가 부모에게 다시 포인터를 누르고 있으면

이

in-order(node): 
    in-order(node.left) if node.left not null 
    process(node) 
    in-order(node.right) if node.right not null 

, 당신은 반복적 인 버전을 쓸 수 있지만, 아마도 생각을위한 음식을하지만 아무것도 노력 (가치되지 않습니다 :이 알고리즘은 이미 이전에 있지만, 기본적으로 표시되었습니다)