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

奥普瓯江 · 发表于 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;
         }
      }
}
}

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

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

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