这段代码能否遍历二叉树
请问一下这段代码能否遍历二叉树:
#define maxsize 20
struct bnode
{
int data;
bnode * lchild;
bnode * rchild;
};
struct stack
{
int top;
bnode * num[maxsize];
}
void pretravel(bnode * bt)
{
struct p;
struct *q;
q=bt;
p.top=-1;
while((q!=NULL)||(p.top!=-1))
{
if(q!=NULL)
{
printf( "%d ",q-> data);
if(p.top <maxsize)
{
p.top++;
p.num[p.top]=q;
q=q-> lchild;
}
else
{
printf( "stack over flow.\n ");
}
else if (p.top> -1)
{
q=p.num[p.top];
}
}
[解决办法]
void treeprint(struct tnode *p)
{
if(p!=NULL){
treeprint(p-> left );
printf( "%4d %s\n ",p-> count ,p-> word );
treeprint(p-> right );
}
}
这个可以遍历,递归向左,操作,向右
[解决办法]
可以采用宽度优先的方法,用循环替代递归。
1、将根节点插入队列处理根节点,并将左右子几点插入队里中
依次遍历队列的每个元素,直到队列为空。
[解决办法]
用栈来模拟递归
[解决办法]
自己搜一下有很多
#include <stdio.h>
#define MAXN 100 /*节点的最大数量,姑且定为100*/
struct Node//二叉树节点
{
int data;
Node *left,*right;
};
Node *root;
void Load(Node **p);//读取以p为根节点的子树,具体怎么写与本问题无关,省略
void Travel(Node *p)//非递归中序遍历以p为根节点的子树
{
Node *stack[MAXN];
int flag[MAXN];//标记节点的遍历状态,0表示刚遍历到,1表示已经输出该节点,2表示已遍历左子树,3表示已遍历右子树
int depth;
stack[0]=p;
flag[0]=0;
depth=0;
while (depth!=-1)
{
if (flag[depth]==0)
{
flag[depth]=1;
printf( "%d\n ",stack[depth]-> data);
}
else if (flag[depth]==1)
{
flag[depth]=2;
if (stack[depth]-> left!=NULL)
{
stack[depth+1]=stack[depth]-> left;
flag[depth+1]=0;
depth++;
}
}
else if (flag[depth]==2)
{
flag[depth]=3;
if (stack[depth]-> right!=NULL)
{
stack[depth+1]=stack[depth]-> right;
flag[depth+1]=0;
depth++;
}
}
else if (flag[depth]==3)
{
stack[depth]=NULL;
flag[depth]=-1;
depth--;
}
}
}
main()
{
Load(&root);
Travel(root);
}
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#define ELEMTYPE int
typedef struct bitreenode
{
ELEMTYPE elem;
struct bitreenode *lchild,*rchild;
}BITNODE;
void insertnode(BITNODE **bt,ELEMTYPE num) ;
BITNODE *creatnode(ELEMTYPE num) ;
BITNODE *creattree(void) ;
BITNODE *creatnode(ELEMTYPE num)
{
BITNODE *rt;
rt = (BITNODE*)malloc(sizeof(BITNODE));
rt-> elem = num;
rt-> lchild = rt-> rchild =NULL;
return rt;
}
BITNODE *creattree(void)
{
BITNODE *bt = NULL;
int num;
printf( "请输入一个大于整数字\n ") ;
scanf( "%d ",&num);
while (num!=0){
insertnode(&bt,num);
printf( "请输入一个大于整数字\n0则退出 ") ;
scanf( "%d ",&num);
}
return bt;
}
void insertnode(BITNODE **bt,ELEMTYPE num)
{
if(*bt == NULL)
*bt = creatnode(num);
else
if(num <= (*bt)-> elem)
insertnode(&((*bt)-> lchild),num);
else
insertnode(&((*bt)-> rchild),num);
}
void deletenode(){}
void intraverse(BITNODE *root)
{
if(root != NULL)
{
intraverse(root-> lchild);
printf( "%d ",root-> elem);
intraverse(root-> rchild);
}
}
void main()
{
BITNODE *root = NULL;
root = creattree();
intraverse(root);
printf( "\n ");
}