首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

这段代码能否遍历二叉树,该如何处理

2012-03-08 
这段代码能否遍历二叉树请问一下这段代码能否遍历二叉树:#definemaxsize20structbnode{intdatabnode*lchi

这段代码能否遍历二叉树
请问一下这段代码能否遍历二叉树:

#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 ");
}

热点排行