Programming Exercise: Lab #7

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Exercise #1

Problems

• Implement inOrder(), preOrder(), postOrder().
• Each function traverses the tree and generates the queue in the order it visits.

void inOrder(TreeNode* tree, QueType& inQue)
{
    if (tree != nullptr) {
        inOrder(tree->left, inQue);
        inQue.enqueue(tree);
        inOrder(tree->right, inQue);
    }
}

▶ inOrder()

void postOrder(TreeNode* tree, QueType& postQue)
{
    if (tree != nullptr) {
        postOrder(tree->left, postQue);
        postOrder(tree->right, postQue);
        postQue.enqueue(tree);
    }
}

▶ postOrder()

void preOrder(TreeNode* tree, QueType& preQue)
{
    if (tree != nullptr) {
        preQue.enqueue(tree);
        preOrder(tree->left, preQue);
        preOrder(tree->right, preQue);
    }
}

▶ preOrder()

Exercise #2

Problems

• 1) Implement Ancestors_iterative().
  • Ancestors_iterative() ITERATIVELY traverses the Binary Search Tree, finds "value", and returns the ancestors of the idenfied node (as a form of QUEUE).
  • If "value" does not exist in the tree, it returns EMPTY queue.
• 2) Implement Ancestors_Recursive().
  • Ancestors_iterative() RECURSIVELY traverses the Binary Search Tree, finds "value", and returns the ancestors of the identified node (As a form of STACK).

QueType TreeType::Anscestors_iterative(treeType value)
{
    bool found = false;
    QueType path;
    
    TreeNode* current = root;

    while (current != nullptr && !found) {
        if (value < current->info) {
            path.enqueue(current);
            current = current->left;
        }
        else if (value > current->info) {
            path.enqueue(current);
            current = current->right;
        }
        else {
            found = true;
        }
    }
    
    if (!found) {
        path.clear();
    }
    
    return path;
}

▶ Ancestors_iterative()

bool Ancestors_recursive(TreeNode* tree, treeType value, StackType& path)
{
    bool found = false;

    if (tree == nullptr) {
        return found;
    }

    if (tree->info == value) {
        found = true;
        return found;
    }

    if ((value < tree->info && Ancestors_recursive(tree->left, value, path)) ||
        (value > tree->info && Ancestors_recursive(tree->right, value, path))) {
        path.push(tree);
        found = true;
        return found;
    }

    return found;
}

▶ Ancestors_Recursive()

Exercise #3

Problems

• Implement "buildBalancedBST().
  • buildBalancedBST() generates and returns a new tree "Balanced".
  • "balanced" has the same nodes as the old one, but the shape will be different.
  • This should have the minimum height. (log N)
• HINT1: "IN_ORDER" will return the queue filled with items sorted in ascending order.
  • If we insert these values in proper order, we can create a balanced tree.
• HINT2: You can use recursion! (refer to how we performed a binay search) using recursion.

void insertBalanced(TreeType& tree, treeType* arr, int left, int right) {
    if (left > right) return;

    int mid = (left + right) / 2;
    tree.insertItem(arr[mid]);

    insertBalanced(tree, arr, left, mid - 1);  
    insertBalanced(tree, arr, mid + 1, right);
}

TreeType TreeType::buildBalancedBST(){
    TreeType balanced;
    
    traverseTree(IN_ORDER);

    const int MAX = 100;
    treeType* arr = new treeType[MAX];
    int size = 0;

    while (!inQue.isEmpty())
        arr[size++] = inQue.dequeue()->info;

    insertBalanced(balanced, arr, 0, size - 1);

    delete[] arr;
    return balanced;
}

▶ buildBalancedBST()