데이터 구조 (복습) --- 이 진 트 리 에 대한 기본 조작

4268 단어
// //               Coding
//            ,    (  ,   )        
#include <cstdio>
#include <cstdlib>
//#define _OJ_
typedef struct tree
{
    char data;
    struct tree *left;
    struct tree *right;
} tree, *Bitree;

typedef struct Stack1
{
    int top, base;
    Bitree *elem;
} Stack1, *Stack;

Stack
Init_Stack(void)
{
    Stack s;
    s = (Stack) malloc (sizeof(Stack1));
    s->elem = (Bitree*) malloc (100 * sizeof(Bitree));
    s->top = s->base = 0;
    return s;
}

Bitree
Init_Bitree(Bitree T)
{
    char ch;
    scanf("%c", &ch);
    if(ch == '#')    T = NULL;

    else {
     T = (Bitree) malloc (sizeof(tree));
     T->data = ch;
     T->left = Init_Bitree(T->left);
     T->right = Init_Bitree(T->right);
    }
    return T;
}


void
push(Stack s, Bitree data)
{
    s->elem[s->top++] = data;
}

Bitree
pop(Stack s)
{
    return s->elem[--s->top];
}

Bitree
get_top(Stack s)
{
    return s->elem[s->top - 1];
}

int
isempty(Stack s)
{
    if(s->base == s->top)
        return 1;
    else
        return 0;
}

void
preoder_travers(Bitree T)
{
    if(T != NULL) {
        preoder_travers(T->left);
        printf("%c ", T->data);            //         
        preoder_travers(T->right);
    }
}

void
preoder_traver(Bitree T)
{
    Stack s;
    s = Init_Stack();

    while (T != NULL || isempty(s) != 1) {            //               
        while (T) {
            push(s, T);  printf("%c
", T->data); T = T->left; } if(isempty(s) != 1) { T = pop(s);// printf("%c
", T->data); T = T->right; } } } // ------------------------------------------------------------------------------------ // void postoder_traver(Bitree T) { Stack s; s = Init_Stack(); Bitree T1, pre; T1 = T; pre = NULL; //T1 , pre while (T1 != NULL || isempty(s) != 1) { while (T1) { push(s, T1); T1 = T1->left; // } T1 = get_top(s); if(T1->right == NULL || T1->right == pre) { //T1 printf("%c
", T1->data); pre = T1; T1 = NULL; pop(s); // } else T1 = T1->right; } } int dept_tree(Bitree T) { int dept = 0, dept1 = 0, deep = 0; if(T) { dept = dept_tree(T->left); dept1 = dept_tree(T->right); // deep = dept > dept1 ? dept + 1 : dept1 + 1; } return deep; } int main(int argc, char const *argv[]) { #ifndef _OJ_ //ONLINE JUDGE freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif int deep; Bitree T; T = Init_Bitree(T); // // preoder_travers(T); // // preoder_traver(T); // // postoder_traver(T); // deep = dept_tree(T); // printf(" :%d
", deep); return 0; } // --------------------------------------------------------------------------------------- // // , leftchild , rightchild

좋은 웹페이지 즐겨찾기