[C / 자료구조] 8주차 과제 - 트리

main

#include "treenode.h"
#include "stack.h"

/*
구현해야 하는 내용들
inoder
preoder
print_tree
eval
*/
int eval(TreeNode* root);
void print_tree(TreeNode* root, int level);
void inorder(TreeNode* root);
void preorder(TreeNode* root);
TreeNode* new_node(char ch);
int is_op(char ch);

TreeNode* construct_tree(char* input)
{
    TreeNode* lnode, * rnode, * parent;
    char ch;
    int index = 0;
    StackType* stack = (StackType*)malloc(sizeof(StackType));
    init_stack(stack);
    while ((ch = input[index++]) != '\0') {  // "94-385%+*435+2*++";
        if (ch >= '0' && ch <= '9')
            parent = new_node(ch);
        else {
            parent = new_node(ch);
            rnode = pop(stack);
            lnode = pop(stack);
            add_child(parent, lnode);
            add_child(parent, rnode);
            parent->data = eval(parent);    //후기 표현식의 이점 응용
        }
        push(stack, parent);
        //print_tree(parent, 0);
    }
    return pop(stack);
}
int main()
{
    char input[50] = "94-385%+*435+2*++";
    TreeNode* root = construct_tree(input);
    printf("입력: %s\n\n트리 출력\n", input);
    // eval(root);
    print_tree(root, 0);
    printf("\n중위표기식: ");
    inorder(root, 3);
    printf("\n전위표기식: ");
    preorder(root, 3);
    printf("\n");
    system("pause");
}

TreeNode* new_node(char ch)
{
    int data = 0;
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (isdigit(ch))
        data = ch - '0';
    set(node, ch, data, NULL, NULL);
    return node;
}

int is_op(char ch)
{
    char ops[] = "+-*/%";
    for (int i = 0; i < 5; i++)
        if (ch == ops[i])
            return 1;
    return 0;
}

/*
숫자인지 연산자인지는 쉽게 비교가 가능하다.
그러나 왼쪽인지 오른쪽인지 구분하기 위해서는 추가 변수가 필요하다.
그게 way

*/
void preorder(TreeNode* root, int way) {
    if (!root == NULL) {
        if (is_op(root->name)) printf("(");
        printf("%c ", root->name);
        preorder(root->left, 0);
        preorder(root->right, 1);
        if (way == 1) printf(")");
    }
}

void inorder(TreeNode* root, int way) {
    if (!root == NULL) {
        if (way == 0) printf("(");
        inorder(root->left, 0);
        printf("%c ", root->name);
        inorder(root->right, 1);
        if (way == 1) printf(")");
    }
}

void print_tree(TreeNode* root, int level) {
    if (root == NULL) return;
    for (int i = 0; i < level; i++) {
        printf("... ");
    }
    level++;
    printf("%c", root->name);
    if (is_op(root->name)) printf("(%d)", root->data);
    printf("\n");
    print_tree(root->left, level);
    print_tree(root->right, level);
}

// 후기 표현식으로 들어오는 거 아니면 트리 다 만들고 순회하면서 계산
int eval(TreeNode* root) {
    if (root == NULL) return 0;
    if (is_op(root->name)) {
        int op1 = root->left->data;
        int op2 = root->right->data;
        switch (root->name) {
        case '+': return op1 + op2;
        case '-': return op1 - op2;
        case '*': return op1 * op2;
        case '/': return op1 / op2;
        case '%': return op1 % op2;
        }
    }
    return 0;
}

 

 

tree head.h

 

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
    char name;
    int data;
    struct TreeNode* left, * right;
} TreeNode;

void set(TreeNode* node, char name, int data, TreeNode* lch, TreeNode* rch);
void add_child(TreeNode* node, TreeNode* child);
void print_tree(TreeNode* root, int level);
void print_node(TreeNode* node, int level);

 

 

tree node.c

#include "treenode.h"

void set(TreeNode* node, char name, int data, TreeNode* lch, TreeNode* rch)
{
    node->name = name;
    node->data = data;
    node->left = lch;
    node->right = rch;
}

void add_child(TreeNode* node, TreeNode* child)
{
    if (node == NULL) {
        printf("ERROR can't add to NULL");
        exit(1);
    }
    if (node->left == NULL) {
        node->left = child;
    }
    else if (node->right == NULL) {
        node->right = child;
    }
    else {
        printf("ERROR tree nodes %c %c", node->name, child->name);
        exit(1);
    }
}