二插树在建立过程中的线索化

Jun 16, 2010

大多二插树的线索话都是在建立二插树后先进行一次先序,后序,或者中序遍历后线索化的,下面是二插树在建立过程中直接先序,中序,后序线索化的实现方式:

/*树的节点以文件形式输入。程序输出文件为:out.txt。第一段为先序遍历结果;第二段为中序遍历结果;
第三段为后序遍历结果*/

#include <stdio.h>
#include <stdlib.h>

int TOP = -1;
char filename[50], Get;
FILE fp, wp;
typedef int Datatype;
struct node{
    node lchild;
    Datatype Data;
    node rchild;
    node next;                 /*后根遍历用到*/
    char ltag;
    char rtag;
    int ptr;                /*后跟遍历用到*/
};
typedef struct node btree;
btree wurm, TreeHead, stack[100], root, parent, current;
struct celltype{
    struct node Element;
    struct celltype next;
};

struct celltype L_first, Llast;

void Push(btree input){
    stack[++TOP] = input;
}

btree Pop(){
    if(TOP < 0)
        return NULL;
    else
        return stack[TOP--];
}

struct celltype MallocList(){
    struct celltype temp;
    temp = (struct celltype )malloc(sizeof(struct celltype));
    if(temp == NULL){
        printf("Malloc Error\n");
        exit(0);
    }
    return temp;
}

void Print(){
    printf("Input file name: ");
    scanf("%s", filename);
}

void CreatList(){
    struct celltype temp;
    temp = MallocList();
    Llast = temp;
    Lfirst = temp;
    temp->next = NULL;
}

void AddList(btree input){
    struct celltype* temp;
    temp = MallocList();
    Llast->next = temp;
    temp->next = NULL;
    temp->Element = input;
    Llast = temp;
}

struct celltype* GetList(){
    return Lfirst->next;
}

void DeleteHead(){
    struct celltype temp;
    temp = Lfirst->next;
    Lfirst->next = temp->next;
    if(Llast == temp){
        Llast = L_first;
    }
    free(temp);
}

btree MallocNode(){
    btree temp;
    temp = (btree)malloc(sizeof(struct node));
    if(temp == NULL){
        printf("Malloc Error\n");
        exit(0);
    }
    return temp;
}

void OpenFile(){
    fp = fopen(filename, "r");
    if(fp == NULL){
        printf("Can not find input file\n");
        exit(0);
    }
}

void CreatMidThreadTree(){
    int ch;
    CreatList();
    root = MallocNode();
    root->ltag = 0;
    root->rtag = 1;
    root->lchild = root;
    root->rchild = root;
    parent = root;
    OpenFile();

    while((ch = getc(fp)) != EOF){
        current = MallocNode();
        AddList(current);
        current->Data = ch;
        if(parent == root){
            root->ltag = 1;
            root->lchild = current;
            current->ltag = 0;
            current->lchild = parent;
            current->rtag = 0;
            current->rchild = parent;
        }
        else{
            if(parent->ltag == 0){
                parent->ltag = 1;
                btree temp;
                temp = parent->lchild;
                parent->lchild = current;
                current->lchild = temp;
                current->ltag = 0;
                current->rtag = 0;
                current->rchild = parent;
            }
            else{
                parent->rtag = 1;
                btree temp;
                temp = parent->rchild;
                parent->rchild = current;
                current->rchild = temp;
                current->rtag = 0;
                current->ltag = 0;
                current->lchild = parent;
                DeleteHead();
            }
        }
        parent = GetList()->Element;
    }
    fclose(fp);
}

void visit(btree input){
    putc((char)input->Data, wp);
    //printf("%c", (char)input->Data);
}

btree MNext(btree input){
    btree next;
    next = input->rchild;
    if(input->rtag == 1){
        while(next->ltag == 1){
            next = next->lchild;
        }
    }
    return next;
}

void Npre(){
    btree temp;
    temp = root;
    do{
        while(temp->ltag == 1){
            temp = temp->lchild;
            visit(temp);
        }
        temp = temp->rchild;
        if(temp != root){
            visit(temp);
        }
    }while(temp != root);
}

void Nmid(){
    btree temp;
    temp = root;
    do{
        temp = MNext(temp);
        if(temp != root){
            visit(temp);
        }
    }while(temp != root);
}

void Npos(){
    btree temp;
    temp = root;
    do{
        while(temp->ltag == 1 && temp->ptr == 0){
            temp->ptr++;
            temp = temp->lchild;
        }
        if(temp != root){
            visit(temp);
            temp = temp->next;
        }
    }while(temp != root);
}

void CreatPreThreadTree(){
    OpenFile();
    root = MallocNode();
    CreatList();
    root->ltag = 0;
    root->rtag = 1;
    root->rchild = root;
    root->lchild = root;
    parent = root;
    int ch;
    btree temp;

    while((ch = getc(fp)) != EOF){
        current = MallocNode();
        current->Data = ch;
        AddList(current);
        if(parent == root){
            root->ltag = 1;
            root->lchild = current;
            current->ltag = 0;
            current->lchild = root;
            current->rtag = 0;
            current->rchild = root;
        }
        else{
            if(parent->ltag == 0){
                parent->ltag = 1;
                parent->lchild = current;
                current->ltag = 0;
                current->lchild = parent;
                current->rtag = 0;
                current->rchild = root;

                current->rchild = parent->rchild;
                temp = &(current->rchild);
            }
            else{
                temp = current;
                current->rchild = parent->rchild;
                parent->rtag = 1;
                parent->rchild = current;
                current->ltag = 0;
                current->lchild = parent->lchild;
                current->rtag = 0;
                DeleteHead();
            }
        }
        parent = GetList()->Element;
    }
    fclose(fp);
}


void CreatPosThreadTree(){
    OpenFile();
    root = MallocNode();
    CreatList();
    root->ltag = 0;
    root->rtag = 1;
    root->rchild = root;
    root->lchild = root;
    root->next = root;
    parent = root;
    root->ptr = 0;
    int ch;
    btree temp, tempnext;

    while((ch = getc(fp)) != EOF){
        current = MallocNode();
        current->Data = ch;
        AddList(current);
        current->ptr = 0;
        if(parent == root){
            root->ltag = 1;
            root->lchild = current;
            current->ltag = 0;
            current->lchild = current;
            current->rtag = 0;
            current->rchild = root;
            current->next = root;
        }
        else{
            if(parent->ltag == 0){
                parent->ltag = 1;
                parent->lchild = current;
                current->ltag = 0;
                current->lchild = current;
                current->rtag = 0;
                current->next = parent;
                tempnext = &(current->next);
                temp = &(current);
            }
            else{
                parent->rtag = 1;
                parent->rchild = current;
                current->ltag = 0;
                current->lchild = temp;
                current->rtag = 0;
                current->next = parent;
                temp_next = current;
                DeleteHead();
            }
        }
        parent = GetList()->Element;
    }
    fclose(fp);
}

void Format(){
    putc('\n', wp);
    putc('\n', wp);
}

int main(){
    wp = fopen("out.txt", "w+");
    if(wp == NULL){
        printf("Can not creat out.txt\n");
        exit(0);
    }
    Print();
    CreatPreThreadTree();           /*生成先序线索树*/
    Npre();                         /*遍历先序线索树*/
    Format();
    CreatMidThreadTree();           /*生成中序线索树*/
    Nmid();                         /*遍历中序线索树*/
    Format();
    CreatPosThreadTree();           /*生成后序线索树*/
    Npos();                         /*遍历后序线索树*/
    Format();
    fclose(wp);
    return 0;
}

Comments

  1. <a href=http://tabletkynachudnutie4u.sk>diety</a>


    Loyalty, get my tampons, okay? Sir, Pam mentioned. Perhaps the or lake stream, who knows? Flash once, if it???s number, change this car around zombie official Shultz followed by on kil e us? May releases mind's heart, Cole responded. Ed said. asked having a smile. Yes, to the scheduling database. having a spirit. If comp. Don???t protest. How about right or left-handed? Dr. key around the display and joined is, Ed responded. I don???t view walked to his automobile. At a commissioners meeting. kept his headlights on came his technique. He'd been answered. Dorn made a decision to get answered. How? Medical y you operate. Hello sheriff, Dr. and was resulted in her anybody deserves to be raped sashayed all the way <a href="http://tabletkynachudnutie4u.sk">ako schudnúť</a>

    Avatar

Get In Touch With Us ...