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

奥普瓯江 · 发表于 2021-1-22 18:16:33

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

后序遍历我还没有整清楚

#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;
}

挽星 · 发表于 2022-4-23 11:02:17

#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;
         }
      }
}
}

账号		自动登录	找回密码
密码			立即注册

[技术交流] 二叉树非递归建立及非递归遍历前中序

马上注册，结交更多好友，享用更多功能^_^