二叉树非递归建立及非递归遍历前中序

奥普瓯江

后序遍历我还没有整清楚

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

typedef char Elemtype;

typedef struct Node                        //建立二叉树属性
{
        Elemtype litter;
        struct Node *left;
        struct Node *right;
}Node, *Nodle;

typedef struct Diss                        //建立链表站
{
        Node *time;
        struct Diss *next;
}Diss, *Dog;

void prin_explain();
void push_stree(Dog *F, Node *Tim);
void get_stree(Nodle *T);        //创建二叉树
void prin_stree(Node *T);        //前序打印二叉树
void prin_stree_two(Node *T);        //中序打印二叉树
//void prin_stree_three(Node *T);        //后序打印二叉树
void prin_stree_foure(Node *T);        //测试打印二叉树

void push_stree(Dog *F, Node *Tim)                        //前叉建立栈
{
        Diss *temp;
        temp = (Diss *)malloc(sizeof(Diss ));
        temp->time = Tim;

        if (*F == NULL)
        {
                *F = temp;
                temp->next = NULL;
        } 
        else
        {
                temp->next = *F;
                *F = temp;
        }        
}
void prin_stree_four(Node *T)
{
        if (T != NULL)
        {
                prin_stree_four(T->left);
                prin_stree_four(T->right);
                printf("%c", T->litter);
        }
}
/*void prin_stree_three(Node *T)
{
        Diss *F, *N;
        F = (Diss *)malloc(sizeof(Diss ));
        F = NULL;
        
        while (1)
        {
                if (F == NULL && T==NULL)
                {
                        break;
                }
                while (T != NULL)
                {
                        push_stree(&F, T);
                        T = T->left;        
                }
                T = F->time->right;
                N = F;
                F = F->next;
                free(N);
        }
        
}*/
void prin_stree_two(Node *T)
{
        Diss *F, *N;
        F = (Diss *)malloc(sizeof(Diss ));
        F = NULL;
        
        
        
        while (1)
        {
                if (F == NULL && T==NULL)
                {
                        break;
                }
                while (T != NULL)
                {
                        push_stree(&F, T);
                        T = T->left;
                }
                printf("%c", F->time->litter);
                T = F->time->right;
                N = F;
                F = F->next;
                free(N);
        }

}
void prin_stree(Node *T)
{
        Diss *F, *N;
        F = (Diss *)malloc(sizeof(Diss ));
        F = NULL;

        

        while (1)
        {
                if (F == NULL && T==NULL)
                {
                        break;
                }
                while (T != NULL)
                {
                        printf("%c", T->litter);
                        push_stree(&F, T);
                        T = T->left;
                }
                T = F->time->right;
                N = F;
                F = F->next;
                free(N);
        }
}
void get_stree(Nodle *T)
{
        Diss *F = NULL, *N;
        Elemtype ch, cg;
        Node *Temp;

        while (1)
        {
                if (F == NULL && *T != NULL)                //结束本程序条件
                {
                        break;
                }
                do 
                {
                        scanf("%c", &ch);
                        
                        if (ch == ' ')
                        {
                                Temp = NULL;                                                
                        } 
                        else                                                        //获得节点并输入数据
                        {
                                Temp = (Node *)malloc(sizeof(Node ));
                                Temp->litter = ch;
                        }

                        if (*T == NULL)
                        {
                                *T = Temp;
                        } 
                        else                                                        //与头部节点连接
                        {
                                if (cg ==' ')
                                {
                                        F->time->right = Temp;                //向右变量中插入数据
                                        N = F;
                                        F = F->next;
                                        free(N);                                        //释放栈中数据；空间回收
                                } 
                                else
                                {
                                        F->time->left = Temp;                //用栈作为静态变量，节省空间
                                }
                        }
                        cg = ch;                                        //标记符用于记录上一次循环ch的状态
                        if (Temp != NULL)                        //向栈中输入变量
                        {
                                push_stree(&F, Temp);
                        }        
                } while (ch != ' ');
        }
}
void prin_explain()
{
        printf("1、非递归创建二叉树\n");
        printf("2、前序非递归打印二叉树\n");
        printf("3、中序非递归打印二叉树\n");
        printf("4、测试递归打印二叉树\n");
        printf("9、￥ 结束本程序 ￥\n");
}

int main()
{
        int number;
        Node *T = NULL;

        prin_explain();


        do
        {
                scanf("%d", &number);
                getchar();

                switch (number)
                {
                case 1:
                        {
                                get_stree(&T);                
                        }
                        break;
                case 2:
                        {
                                prin_stree(T);
                                putchar('\n');
                        }
                        break;
                case 3:
                        {
                                prin_stree_two(T);
                                putchar('\n');
                        }
                        break;
                case 4:
                        {
                                prin_stree_four(T);
                                putchar('\n');
                        }
                        break;
                case 9:
                                                                        //结束本程序
                        break;
                default:
                        printf("您所输入的数据有误请从新输入！\n");
                        break;
                        }
        }while (number != 9);

        return 0;
}

挽星

#include <stdio.h>
#include <stdlib.h>
#define StackMax 100

typedef struct Node
{
    char data;
    struct Node *LChild;
    struct Node *RChild;
} BiNode, *BiTree;

typedef struct
{
    BiTree data[StackMax];
    int top;
} Stack;

BiTree CreateTree();                //建立二叉树
void InitStack(Stack *S);           //栈的初始化
int EmptyStack(Stack S);            //栈判空
int FullStack(Stack S);             //栈判满
void PushStack(Stack *S, BiTree T); //入栈
void PopStack(Stack *S, BiTree *T); //出栈
void GetTop(Stack S, BiTree *T);    //获取栈顶端元素
void PreoderTree(BiTree T);         //前序遍历
void Preoder(BiTree T);             //迭代前序遍历
void InPrintTree(BiTree T);         //中序遍历
void InOrder(BiTree T);             //迭代中序遍历
void PostPrintTree(BiTree T);       //后序遍历
void PostOrder(BiTree T);           //迭代后序遍历

int main()
{
    BiTree T;
    T = CreateTree();
    printf("递归前序输出：\n");
    PreoderTree(T);
    printf("\n迭代前序输出：\n");
    Preoder(T);
    printf("\n递归中序输出：\n");
    InPrintTree(T); //递归中序
    printf("\n迭代中序输出：\n");
    InOrder(T); //非递归中序
    printf("\n递归后序输出：\n");
    PostPrintTree(T); //递归后序
    printf("\n迭代后续输出：\n");
    PostOrder(T); //非递归后序
    return 0;
}

//建立二叉树
BiTree CreateTree()
{
    char c;
    c = getchar();
    BiTree T;
    if (' ' == c)
    {
        return NULL;
    }
    else
    {
        T = (BiTree)malloc(sizeof(BiNode));
        T->data = c;
        T->LChild = CreateTree();
        T->RChild = CreateTree();
    }
    return T;
}

//栈的初始化
void InitStack(Stack *S)
{
    S->top = -1;
}

//栈判空
int IsEmptyStack(Stack S)
{
    if (-1 == S.top)
    {
        return 1;
    }
    return 0;
}

//栈判满
int IsFullStack(Stack S)
{
    if (S.top == StackMax - 1)
    {
        return 1;
    }
    return 0;
}

//入栈
void PushStack(Stack *S, BiTree T)
{
    if (IsFullStack(*S))
    {
        printf("栈满 ");
        return;
    }
    S->top++;
    S->data[S->top] = T;
}

//出栈
void PopStack(Stack *S, BiTree *T)
{
    if (IsEmptyStack(*S))
    {
        printf("栈满 ");
        return;
    }
    (*T) = S->data[S->top];
    S->top--;
}

//获取栈顶端元素
void GetTop(Stack S, BiTree *T)
{
    if (IsEmptyStack(S))
    {
        printf("栈满 ");
        return;
    }
    (*T) = S.data[S.top];
}

//递归前序输出
void PreoderTree(BiTree T)
{
    if (T == NULL)
    {
        return;
    }
    printf("%c", T->data);
    PreoderTree(T->LChild);
    PreoderTree(T->RChild);
}

//迭代前序输出
void Preoder(BiTree T)
{
    Stack S;
    InitStack(&S);
    BiTree tmp;
    tmp = T;
    while (tmp != NULL || !IsEmptyStack(S))
    {
        if (tmp != NULL)
        {
            PushStack(&S, tmp);
            printf("%c", tmp->data);
            tmp = tmp->LChild;
        }
        else
        {
            PopStack(&S, &tmp);
            tmp = tmp->RChild;
        }
    }
}
//递归中序输出
void InPrintTree(BiTree T)
{
    if (T == NULL)
    {
        return;
    }
    InPrintTree(T->LChild);
    printf("%c", T->data);
    InPrintTree(T->RChild);
}

//迭代中序遍历
void InOrder(BiTree T)
{
    Stack S;
    InitStack(&S);
    BiTree tmp;
    tmp = T;
    while (tmp != NULL || !IsEmptyStack(S))
    {
        if (tmp != NULL)
        {
            PushStack(&S, tmp);
            tmp = tmp->LChild;
        }
        else
        {
            PopStack(&S, &tmp);
            printf("%c", tmp->data);
            tmp = tmp->RChild;
        }
    }
}

//递归后序输出
void PostPrintTree(BiTree T)
{
    if (T == NULL)
    {
        return;
    }
    PostPrintTree(T->LChild);
    PostPrintTree(T->RChild);
    printf("%c", T->data);
}

//迭代后序遍历
void PostOrder(BiTree T)
{
    Stack S;
    InitStack(&S);
    BiTree p, q;
    p = T;
    q = NULL;
    while (p != NULL || !IsEmptyStack(S))
    {
        if (p != NULL)
        {
            PushStack(&S, p);
            p = p->LChild;
        }
        else
        {
            GetTop(S, &p);
            if (p->RChild != NULL && p->RChild != q)
            {
                p = p->RChild;
            }
            else
            {
                printf("%c", p->data);
                q = p;
                PopStack(&S, &p);
                p = NULL;
            }
        }
    }
}