求二叉树的非递归后序遍历的c语言代码？3
发布网友
发布时间：2023-10-13 12:52
共2个回答
热心网友
时间：2024-12-04 21:52
#include<stdio.h>
#define N 10
using namespace std;
char *a;
typedef struct NODE{
char data;
struct NODE *lch, *rch,*parent;
} *BINTREE,Node;
void visit(char data){
printf("%5c",data);
}
void preorder(BINTREE T){ // 先根序周游
BINTREE stack[50];
BINTREE p;
p=T;
int s=0;
if(p==NULL)return;
while(1)
{ visit(p->data);
while(p->lch!=NULL) {
stack[++s]=p;
p=p->lch;
visit(p->data); }
// cout<<" "<<s;
while(1)
{ if((p=p->rch)!=NULL)
break;
if(s==0)
return;
p=stack[s--];
}
}
}
void inorder(BINTREE T)//中根序周游
{
Node *stack[100];
int top=0;
stack[0]=T;
while(top>0 ||stack[top]!=NULL)
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch ;
}
if(top>0)
{
printf("%5c",stack[--top]->data );
stack[top]=stack[top]->rch ;
}
}
}
void posorder1(BINTREE T)//后根序周游
{
Node *stack[100];
int top=0;
int tag[100];
tag[0]=0;
stack[0]=T;
do
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch ;
tag[top]=0;
}
while(tag[top-1]==1)
printf("%5c",stack[--top]->data );
if(top>0)
{
stack[top]=stack[top-1]->rch ;
tag[top-1]=1;
tag[top]=0;
}
} while(top!=0);
}
BINTREE Create(){//先根序树的建立
BINTREE T;
char ch;
cin>>ch;
cout<<" ch="<<ch<<endl;
if(ch=='#')
T=NULL;
else{
if(!(T=(BINTREE )malloc(sizeof(Node))))
printf("Error!");
T->data=ch;
T->lch=Create();
T->rch=Create();
}
return T;
}
void main(){
freopen("D:\\input.txt","r",stdin);
BINTREE T;
T=Create();
cout<<"先根序遍历 ";
preorder(T);
cout<<endl;
cout<<"中根序遍历 ";
inorder(T);
cout<<endl;
cout<<"后根序遍历 ";
posorder1(T);
cout<<endl;
cout<<endl;
}
在D盘建立一个input.txt的文件，输入数的内容，输入顺序为先序根遍历的顺序，叶子节点的left和right用#代替即可。
热心网友
时间：2024-12-04 21:52
#include "stdlib.h"
typedef char DataType;
struct BinTreeNode
{
DataType info;
struct BinTreeNode *llink, *rlink;
};
typedef struct BinTreeNode *PBinTreeNode;
#define MAXNUM 128
typedef struct
{
PBinTreeNode ptr; /*结点地址进栈*/
int tag; /*特征位:第一次进栈时置0,第二次进栈时置1*/
}Elem;
struct SeqStack
{
Elem s[MAXNUM];
int t;
};
typedef struct SeqStack *PSeqStack;
PSeqStack createEmptyStack_seq(void)
{
PSeqStack pastack;
pastack=(PSeqStack)malloc(sizeof(struct SeqStack));
if(!pastack)
printf("内存溢出\n");
else
pastack->t=-1;
return pastack;
}
int isEmptyStack_seq(PSeqStack pastack)
{
return (pastack->t==-1);
}
void push_seq(PSeqStack pastack, Elem x)
{
if(pastack->t>=MAXNUM-1)
printf("栈发生了上溢!\n");
else
{
pastack->t=pastack->t+1;
pastack->s[pastack->t]=x;
}
}
void pop_seq(PSeqStack pastack)
{
if( isEmptyStack_seq(pastack) )
printf("栈发生了下溢!\n");
else
pastack->t=pastack->t-1;
}
Elem top_seq(PSeqStack pastack)
{
Elem temp={NULL,-1};
if( isEmptyStack_seq(pastack) )
{
printf("栈发生了下溢!\n");
return(temp);
}
else
return (pastack->s[pastack->t]);
}
/*后序周游的方法：遇到一个结点，把它推入栈中，去周游它的左子树；周游
遍它的左子树后，还不能马上访问处于栈顶的结点，而是要按照它的右指针
指示的地址去周游该结点的右子树；周游遍右子树后才能从栈顶托出该结点
并访问之。因此需要给栈中的每个元素加上一个特征位，以便当从栈顶托出
一个结点时区别是从栈顶元素左边回来的（则要继续周游右子树），还是从
右边回来的（该结点的左、右子树均已周游，则要访问该结点）。进入左子
树该结点的特征位置0；进入右子树该结点的特征位置1。返回时，特征位为
0表示从左边回来；特征位为1表示从右边回来。*/
void postOrder(PBinTreeNode root)
{
PSeqStack st;
Elem stnode;
if( !root ) /*若空二叉树，则结束算法*/
{
printf("这是一棵空二叉树!\n");
return;
}
st=createEmptyStack_seq();
do /*进入以root指示的结点为根的子树*/
{
while(root) /*进入左子树*/
{
stnode.ptr=root;
stnode.tag=0;
push_seq(st,stnode);
root=root->llink;
}
stnode=top_seq(st); /*托出栈顶元素*/
pop_seq(st);
root=stnode.ptr;
while(stnode.tag==1) /*从右子树回来，访问root所指的结点*/
{
putchar(root->info);
putchar(' ');
if( isEmptyStack_seq(st) )
return; /*若栈空，则结束*/
else
{
stnode=top_seq(st);
pop_seq(st);
root=stnode.ptr;
}
}
stnode.tag=1; /*从左子树回来，准备进入右子树*/
push_seq(st,stnode);
root=root->rlink;
}while( !isEmptyStack_seq(st) );
}
PBinTreeNode createRest_BTree(void)
{
PBinTreeNode pbnode;
char ch;
ch=getchar();
if( ch=='@' ) pbnode=NULL;
else
{
pbnode=(PBinTreeNode)malloc(sizeof(struct BinTreeNode));
if( !pbnode )
{
printf("内存空间发生溢出！\n");
return pbnode;
}
pbnode->info=ch;
pbnode->llink=createRest_BTree();
pbnode->rlink=createRest_BTree();
}
return pbnode;
}
void main()
{
PBinTreeNode root;
printf("顺序地输入扩充二叉树的先根序列(外部结点“@”用表示):\n");
root=createRest_BTree();
printf("\n二叉树的后根序列为：\n");
postOrder(root);
printf("\n");
}
