付费节点推荐

免费节点

节点使用教程

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

typedef char elemtype;

/*结构体声明*/
typedef struct bitnode{
elemtype ch;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;

/*

*/
bitnode *creat(){
bitnode *t,*s,*p[30];  //t保存二叉树的根节点，s不断分配节点，数组p保存各个节点
char ch;  //二叉树节点的数据域
int i,j;
scanf("%d%c",&i,&ch);
while(i!=0)
{
s=(bitnode *)malloc(sizeof(bitnode));
s->ch=ch;    //将ch保存在节点数据域中
s->lchild=s->rchild=NULL;  //初始化左右子树为空
p[i]=s;     //将节点s保存数组
if(i==1)    //如果是第一个节点
t=s;   // 则让t保存第一个节点
else
{
j=i/2;    // 如果i不是1，则j保留左右子树在数组中位置（比如:i=2,3 则j=1，p[j]->lchild,p[j]->rchild为左右子树）

if(i%2==0)     //判断左右子树，偶数为左子树，奇数为右子树.
p[j]->lchild=s;
else
p[j]->rchild=s;

}
scanf("%d%c",&i,&ch);
}
return t;

}

void preorder(bitree T)  //栈实现二叉树的前序遍历
{
int top=-1;   //初始化栈顶指针为-1
bitree elem[30];
bitree p=T;

while(p!=NULL||top!=-1)  //遍历结束条件p为空，“并且”栈为空
if(p!=NULL)  //若p不为空
{
printf("%c ",p->ch);        //输出第节点，并且将节点入栈
top++;
elem[top]=p;   //入栈
p=p->lchild;    //继续访问p的左子树

}
else  //如果访问的p为空
{
p=elem[top];   //则（出栈）返回上一节点，并继续访问右子树
top--;
p=p->rchild;
}
}

void inorder(bitree T)
{
int top=-1;
bitree elem[30];
bitree p=T;

while(p!=NULL||top!=-1)  //基本和前序遍历原理一样
{
while(p!=NULL)   //若p不为空
{

top++;     //将节点入栈，并一直访问左子树
elem[top]=p;
p=p->lchild;
}

if(p==NULL)  //直到p节点为空
{
p=elem[top];

top--;
printf("%c ",p->ch);  //出栈，并输出p节点
p=p->rchild;  //再继续访问右节点

}
}
}

int  main()
{
bitree T;
T=creat();
printf("前序:");
preorder(T);
printf("\n中序:");
inorder(T);
return 0;
}

未经允许不得转载：Bcoder资源网 » 非递归对二叉树的遍历操作-栈实现

相关推荐