二叉树非递归建立及非递归遍历前中序
后序遍历我还没有整清楚#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;
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 = T;
}
//出栈
void PopStack(Stack *S, BiTree *T)
{
if (IsEmptyStack(*S))
{
printf("栈满 ");
return;
}
(*T) = S->data;
S->top--;
}
//获取栈顶端元素
void GetTop(Stack S, BiTree *T)
{
if (IsEmptyStack(S))
{
printf("栈满 ");
return;
}
(*T) = S.data;
}
//递归前序输出
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;
}
}
}
}
页:
[1]