二叉树深度+建树+查找+遍历二叉树

按先序扩展序列建立二叉树 先序、中序、后序遍历的递归算法 中序遍历的非递归算法 先序遍历的非递归算法 后序遍历的非递归算法 层次的非递归算法 求二叉树的深度(后序遍历)

#include
#include
#include
#define NULL 0
#define OVERFLOW 0
#define MAXLEN 1000

typedef struct BiTNode{
	char data;
	struct BiTNode * lchild * rchild;		//左右孩子指针
}BiTNode * BiTree;



struct node{ 
	BiTree vec[MAXLEN];
    int fr; 
        
} q;
 

int count=0;



//按先序输入二叉树结点的值
bool CreateBiTree（BiTree &T） {
	char ch;
    scanf（“%c“&ch）;
    
	if （ch==‘ ‘） 	
		T = NULL;
		
    else {
       if （!（T = （BiTNode *）malloc（sizeof（BiTNode））））
          exit（OVERFLOW）;
      T->data = ch;                       // 生成根结点
	 
      CreateBiTree（T->lchild）;		// 构造左子树
      CreateBiTree（T->rchild）;		// 构造右子树
    }
  return true;
} 




void Preorder （BiTree T）
                  
{                    // 先序遍历二叉树 
   if （T） {
      printf（“%c  “T->data ）;          // 访问根结点
      Preorder（T->lchild）; // 遍历左子树
      Preorder（T->rchild）;// 遍历右子树
   }
}


void Inorder （BiTree T）
                  
{                    // 中序遍历二叉树 
   if （T） {
      
     Inorder（T->lchild）; // 遍历左子树
	 printf（“%c  “T->data ）;          // 访问根结点
     Inorder（T->rchild）;// 遍历右子树
   }
}

void Postorder （BiTree T）
                  
{                    // 后序遍历二叉树 
   if （T） {
      
     Postorder（T->lchild）; // 遍历左子树
     Postorder（T->rchild）;// 遍历右子树 
	 printf（“%c  “T->data ）;          // 访问根结点
   }
}





//先序非递归算法
void preorder（ BiTree  b）
  { 
	BiTree stack[1000];
	BiTree p;
    

	int top;  
    if （b!=NULL）
     {
		 top=1;						//根结点入栈
         stack[top]=b;
         while （top>0）				 //栈不为空时循环
         {
			  p=stack[top];			//退栈并访问该结点
              top--;
              printf（“%c  “p->data）;
			  if （p->rchild!=NULL）     //右孩子入栈
              { 
				  top++;
                  stack[top]=p->rchild;
			  }
              if （p->lchild!=NULL）    //左孩子入栈 
              {
				  top++;
                  stack[top]=p->lchild;
              }
         }
     }
}


//中序非递归算法
void inorder（ BiTree  b）
  { 
	BiTree stack[1000]p;
     int top=0;  
     p=b;
     do
       { 
		   while （p!=NULL）        //扫描所有左结点，并入栈
            { 
			   top++;
               stack[top]=p;
               p=p->lchild;
            }
			if （top>0） 
            { 
				p=stack[top]; 
								//p所指结点为无左子树的结点或其左子树已遍历过
                 top--;
                 printf（“%c  “p->data）;		//访问结点
                 p=p->rchild;               //扫描右子树
             }
        } while （p!=NULL||top!=0）;
   }



//后序非递归算法
void postorder（ BiTree b）
  { 
	BiTree stack[1000]p;
    int tag[1000] top=0;  
    p=b;
    do
     { 
		 while（p!=NULL）        //扫描所有左结点，并入栈
           { 
			   top++;
			   tag[top]=0;
               stack[top]=p;
               p=p->lchild;
           }
								//p所指结点为无左子树的结点或其左子树已遍历过
          while （（top>0） && tag[top]==1）  
															// p的左右子树都访问过
          { 
		        printf（“%c  “ stack[top] ->dat

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4405  2008-11-15 20:20  建树&遍历&深度&查找\Debug\depth.obj

    .......    168049  2004-11-24 10:57  建树&遍历&深度&查找\Debug\PrInPoOrder.exe

    .......    194360  2004-11-24 10:57  建树&遍历&深度&查找\Debug\PrInPoOrder.ilk

    .......     14204  2004-11-24 10:57  建树&遍历&深度&查找\Debug\PrInPoOrder.obj

    .......    222380  2004-11-24 10:14  建树&遍历&深度&查找\Debug\PrInPoOrder.pch

    .......    435200  2004-11-24 10:57  建树&遍历&深度&查找\Debug\PrInPoOrder.pdb

    .......     41984  2004-11-24 10:57  建树&遍历&深度&查找\Debug\vc60.idb

    .......     53248  2004-11-24 10:57  建树&遍历&深度&查找\Debug\vc60.pdb

    .......    163904  2008-11-09 16:42  建树&遍历&深度&查找\Debug\递归遍历.exe

     文件     172160  2008-11-09 16:42  建树&遍历&深度&查找\Debug\递归遍历.ilk

    .......    222348  2008-11-09 16:42  建树&遍历&深度&查找\Debug\递归遍历.pch

    .......    345088  2008-11-09 16:42  建树&遍历&深度&查找\Debug\递归遍历.pdb

     文件       5797  2008-11-23 00:14  建树&遍历&深度&查找\PrInPoOrder.cpp

     文件       3461  2004-11-24 10:57  建树&遍历&深度&查找\PrInPoOrder.dsp

     文件        547  2004-11-24 10:58  建树&遍历&深度&查找\PrInPoOrder.dsw

     文件      50176  2004-11-24 10:58  建树&遍历&深度&查找\PrInPoOrder.ncb

    .......     48640  2004-11-24 10:58  建树&遍历&深度&查找\PrInPoOrder.opt

     文件       1216  2004-11-24 10:57  建树&遍历&深度&查找\PrInPoOrder.plg

    .......      4311  2008-11-09 16:43  建树&遍历&深度&查找\递归遍历.dsp

     文件        541  2008-11-09 16:41  建树&遍历&深度&查找\递归遍历.dsw

    .......     33792  2008-11-09 16:43  建树&遍历&深度&查找\递归遍历.ncb

     文件      48640  2008-11-09 16:43  建树&遍历&深度&查找\递归遍历.opt

     文件       1294  2008-11-09 16:42  建树&遍历&深度&查找\递归遍历.plg

     目录          0  2009-04-03 01:04  建树&遍历&深度&查找\Debug

     目录          0  2009-04-03 01:04  建树&遍历&深度&查找

----------- ---------  ---------- -----  ----

              2235745                    25