d.cpp

2叉树的 非递归与递归遍历~~~~~~~~~~~~~~~~ 求2叉树的深度

# include <stdio.h>
# include <stdlib.h>
#define M 50
  typedef int Etype;
  typedef struct BiTNode  // 树结点结构 
      {  Etype data;
	     struct BiTNode *lch,*rch;
      }BiTNode,*bitree;
/* 函数原形声明 */
BiTNode *creat_bt();
void PreOrderTraverse(bitree bt);
//int preOrdTr1(bitree bt);
int print(bitree bt);
int TreeDepth(BiTNode *t);
/*  主函数 */
 void main()
{ 
	 
	int T_Depth;
	printf("说明:\n 只有当结点数据为0时不再产生左右孩子\n\n\n 输入数据：\n") ;
    bitree O;
	O=creat_bt();
	PreOrderTraverse(O);
   //preOrdTr1(O);

   T_Depth= TreeDepth(O);
    printf("\n二叉树的深度：%d\n", T_Depth);
 } /* main */  

 /* 模仿先序递归遍历方法，建立二叉树 */
 BiTNode *creat_bt()
  { BiTNode *t; 
int e;
     printf("\n data="); scanf("%d",&e);
     if(e==0) t=NULL;                  /* 对于0值，不分配新结点 */
       else { t=(BiTNode *)malloc(sizeof(BiTNode));
	          t->data=e;
	          t->lch=creat_bt();  /* 左孩子获得新指针值  */
	          t->rch=creat_bt();  /* 右孩子获得新指针值  */
	         }
     return(t);
  } /* creat_bt*/

void PreOrderTraverse(bitree bt)
{int top=0;
bitree p,s[M];
p=bt;
do
{while (p!=NULL)
{printf("%d \n",p->data);
if(p->rch!=NULL)
s[top++]=p->rch;
p=p->lch;
}
if(top>=0)
p=s[--top];

}while(top>=0);
}
/* int preOrdTr1(bitree bt){
    //T为非空树才进行遍历
      if(bt){//以下三个if语句部分，只有每个部分都处理成功才返回1也即遍历成功
            if(print(bt))
                if(preOrdTr1(bt->lch))
                    if(preOrdTr1(bt->rch))
                        return 1;
            return 0;
    }else
        return 1;
}*/
int print(bitree bt){
      printf("%d",bt->data);
      return 1;
      }


int TreeDepth(BiTNode *t)
{int h,rh,lh;
  if(t==NULL) 
     h=0;
  else
  {lh=TreeDepth(t->lch);
   rh=TreeDepth(t->rch);
   if(lh>=rh)
   h=lh+1;
   else 
	   h=rh+1;
  }
return h;
}