Tree....

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。采取非递归方法输出这棵二叉树的先序、中序遍历序列。

/*************************************************************************
        > File Name: 非递归先序中序遍历序列.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月21日 星期一 10时12分38秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

typedef struct 
{
    BiTree da[1000];
    int top;
}SeqStack;

SeqStack  *InitStack()
{
    SeqStack *s;
    s = (SeqStack *)malloc(sizeof(SeqStack));
    s->top = -1;
    return s;
}

//判断栈是否为空
int IsEmpty(SeqStack *s)
{
    if(s->top == -1)
    return 1;
    else 
    return 0;
}

int push(SeqStack *s,BiTree root)
{
    if(s->top == 999)
    return 0;
    else {
        s->top++;
        s->da[s->top];
        return 1;
    }
}

int pop(SeqStack *s, BiTree *root)
{
    if(IsEmpty(s))
    return 0;
    else {
        *root=s->da[s->top];
        s->top--;
        return 1;
    }
}

void push(SeqStack *s, BiTree root) 
{
    BiTree p;
    p = root;
    if(s->top == 999) 
        return;
    else {
        s->top++;
        s->da[s->top]=p;
    }
}

void pop(SeqStack *s, BiTree *root) 
{
    BiTree p;
    p = *root;
    if(IsEmpty(s))
        return;
    else {
        *root = s-> da[s->top];
        s->top--;
    }
}

//先序创建二叉树
void creat(BiTree *root) 
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree)malloc(sizeof(BiTNode));
        (*root)->data = ch;
        creat(&(*root)->lchild);
        creat(&(*root)->rchild);
    }
}


void PreOrder(BiTree root)
{
    SeqStack *s;
    BiTree p;
    s=InitStack();
    p = root;
    while(p != NULL || !IsEmpty(s)) {
        while(p != NULL) {
            printf("%c", p->data);
            push(s,p);
            p = p -> lchild;
        }
        if(!IsEmpty(s)) {
            pop(s,&p);
            p = p -> rchild;
        }
    }
}

void InOrder(BiTree root) 
{
    SeqStack *s;
    BiTree p;
    s=InitStack();
    p = root;
    while(p != NULL || !IsEmpty(s)) {
        while(p!=NULL) {
            push(s,p);
            p = p -> lchild;
        }
        if(!IsEmpty(s)) {
            pop(s,&p);
            printf("%c",p->data);
            p = p-> rchild;
        }
    }    
}

int main()
{
    BiTree root;
    creat(&root);
    PreOrder(root);
    printf("\n");
    InOrder(root);

    return 0;
}

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。采取非递归方法输出这棵二叉树的后序遍历序列。

/*************************************************************************
        > File Name: 非递归先序中序遍历序列.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月21日 星期一 10时12分38秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

typedef struct 
{
    BiTree da[1000];
    int top;
}SeqStack;

SeqStack  *InitStack()
{
    SeqStack *s;
    s=(SeqStack *)malloc(sizeof(SeqStack));
    s->top = -1;
    return s;
}

int IsEmpty(SeqStack *s)
{
    if(s->top == -1)
    return 1;
    else 
    return 0;
}

void push(SeqStack *s, BiTree root) 
{
    BiTree p;
    p = root;
    if(s->top == 999) 
        return;
    else {
        s->top++;
        s->da[s->top]=p;
    }
}

void pop(SeqStack *s, BiTree *root) 
{
    BiTree p;
    p = *root;
    if(IsEmpty(s))
        return;
    else {
        *root = s-> da[s->top];
        s->top--;
    }
}

void getTop(SeqStack *s, BiTree *p)
{
    if(IsEmpty(s))
    return ;
    else
    *p = s->da[s->top];
}

void creat(BiTree *root) 
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree)malloc(sizeof(BiTNode));
        (*root)->data = ch;
        creat(&(*root)->lchild);
        creat(&(*root)->rchild);
    }
}

void PostOrder(BiTree root)
{
    SeqStack *s;
    BiTree p,q;
    s=InitStack();
    p = root;
    q = NULL;
    while(p != NULL || !IsEmpty(s)) {
        while(p != NULL) {
            push(s,p);
            p = p -> lchild;
        }
        if(!IsEmpty(s)) {
            getTop(s,&p);
            if(p->rchild==NULL || p->rchild == q) {
                 pop(s,&p);
                 printf("%c",p->data);
                 q=p;
                 p=NULL;
            }
            else
                p = p -> rchild;
        }
    }
}

int main()
{
    BiTree root;
    creat(&root);
    PostOrder(root);

    return 0;
}

从键盘接收扩展先序序列，以二叉链表作为存储结构，建立二叉树。输出这棵二叉树的层次遍历序列。

/*************************************************************************
        > File Name: 非递归先序中序遍历序列.c
      > Author: dongmengyuan
      > Mail: 1322762504@qq.com
      > Created Time: 2016年11月21日 星期一 10时12分38秒
 ************************************************************************/

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

typedef char datatype;
typedef struct Node
{
    datatype data;
    struct Node *lchild;
    struct Node *rchild;
}BiTNode, *BiTree;

#define max 1000
typedef struct 
{
    BiTree da[max];
    int front;
    int rear;
}SeqQueue;

SeqQueue *InitQueue()
{
    SeqQueue *q;
    q = (SeqQueue *)malloc(sizeof(SeqQueue));
    q->front = q->rear = max-1;
    return q;
}

int IsEmpty(SeqQueue *q)
{
    if(q->front == q->rear) 
    return 1;
    else
    return 0;
}

void EnterQueue(SeqQueue *q,BiTree root)
{
    BiTree p;
    p = root;
    if((q->rear+1) % max == q->front) {
        return ;
    }
    else {
        q -> rear = (q->rear+1) % max;
        q->da[q->rear] = p;
    }
}

void out(SeqQueue *q, BiTree *root)
{
    if(q->front == q->rear) 
    return ;
    else {
        q->front = (q->front+1)%max;
        *root = q->da[q->front];
    }
}

void creat(BiTree *root) 
{
    char ch;
    ch = getchar();
    if(ch == '#') {
        *root = NULL;
    }
    else {
        *root = (BiTree)malloc(sizeof(BiTNode));
        (*root)->data = ch;
        creat(&(*root)->lchild);
        creat(&(*root)->rchild);
    }
}

void cengci(BiTree root) 
{
    SeqQueue *s;
    BiTree p;
    s=InitQueue();
    EnterQueue(s,root);
    while(!IsEmpty(s)) {
        out(s,&p);
        printf("%c",p->data);
        if(p->lchild != NULL) 
        EnterQueue(s,p->lchild);
        if(p->rchild != NULL)
        EnterQueue(s,p->rchild);
    }   
}

int main()
{
    BiTree root;
    creat(&root);
    cengci(root);

    return 0;
}