이진 트리 삽입 (순서대로 정렬)

Question

인터넷에서이 문제에 대한 도움을 얻었지만 도움이 필요합니다. 이것은 트리 구조 자체로 직접 작업하지 않기 때문에 이진 트리에 대한 일반적인 삽입 문제는 아닙니다. 내 교수는 그 자신을 썼고 우리에게 이진 트리에 관련된 함수를 작성하는 데 사용할 수있는 함수를 제공했습니다. 따라서 노드와 포인터 등을 사용할 수 없습니다. 또한이 C++ 있습니다.

어쨌든 여기에 내가 작성해야하는 재귀 함수에 대한 설명이 나와 있습니다 (문제를 해결하기위한 시작 시도와 함께). 새로운 트리를 완전히 반환한다는 것을 주목하십시오. 실제로는 기존 트리에 무언가를 추가하지는 않습니다.

tree_t insert_tree(int elt, tree_t tree) 
{ 
    /* 
    // REQUIRES; tree is a sorted binary tree 
    // EFFECTS: returns a new tree with elt inserted at a leaf such that 
    //   the resulting tree is also a sorted binary tree. 
    // 
    //   for example, inserting 1 into the tree: 
    // 
    //       4 
    //      / \ 
    //      / \ 
    //      2  5 
    //     /\ /\ 
    //       3 
    //      /\ 
    // 
    // would yield 
    //       4 
    //      / \ 
    //      / \ 
    //      2  5 
    //     /\ /\ 
    //      1 3 
    //     /\/\ 
    // 
    // Hint: an in-order traversal of a sorted binary tree is always a 
    //  sorted list, and there is only one unique location for 
    //  any element to be inserted. 
    */ 

if (elt < elt(tree_left(tree)){ 
    return insert_tree(tree_left(left)); 
} else { 
    return insert_tree(tree_right(right)); 
} 
} 

그리고 여기에 우리가 사용할 수있는 기능은 다음과 같습니다

extern bool tree_isEmpty(tree_t tree); 
    // EFFECTS: returns true if tree is empty, false otherwise 

extern tree_t tree_make(); 
    // EFFECTS: creates an empty tree. 

extern tree_t tree_make(int elt, tree_t left, tree_t right); 
    // EFFECTS: creates a new tree, with elt as it's element, left as 
    //   its left subtree, and right as its right subtree 

extern int tree_elt(tree_t tree); 
    // REQUIRES: tree is not empty 
    // EFFECTS: returns the element at the top of tree. 

extern tree_t tree_left(tree_t tree); 
    // REQUIRES: tree is not empty 
    // EFFECTS: returns the left subtree of tree 

extern tree_t tree_right(tree_t tree); 
    // REQUIRES: tree is not empty 
    // EFFECTS: returns the right subtree of tree 

extern void tree_print(tree_t tree); 
    // MODIFIES: cout 
    // EFFECTS: prints tree to cout. 

Answer 1

을 제로 요소 트리에 삽입하면 쉽게 : 한 요소 트리에 삽입

return tree_make(elt, tree_make(), tree_make()); 

도 쉽게 :

tree_t new_node = tree_make(elt, tree_make(), tree_make()); 
if(elt < tree_elt(tree)) 
    return tree_make(tree_elt(tree), new_node, tree_right(tree)); 
else 
    return tree_make(tree_elt(tree), tree_left(tree), new_node); 

새 요소를 삽입하려면이 방법으로 모든 부모를 다시 만들어야합니다.

---

2 부 : 재귀

우리는 우리의 기본 케이스 (제로 요소 트리)가 있습니다. 새로운 트리를 기존 트리의 루트에 연결하는 방법을 알고 있습니다.

그래서 새 하위 트리를 가져 오는 방법은 무엇입니까? 자, 요소를 현재의 서브 트리에 삽입하는 것은 어떨까요?

다음 코드는 항상 멀리 나무의 왼쪽에 새 요소를 연결합니다,하지만 당신이 그것을 이해하고 나면 수정 하찮은해야한다 : 나는 나의 첫 해에 유래에 대해 알고 싶어

tree_t tree_insert(int elt, tree_t tree) 
{ 
    if(tree_empty(tree)) //base case 
     return tree_make(elt, tree_make(), tree_make()); 
    else 
     return tree_make(// make a new node 
      tree_elt(tree) // with the same value as the current one 
      tree_insert(elt, tree_left(tree)) //insert into the left subtree 
      tree_right(tree) // keep the right subtree the same 
      ); 
}