二叉树综合.cpp

二叉树所有简单的功能

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

typedef struct BiTNode{
	char str;
	struct BiTNode * lchild,* rchild;
}BiTNode ;                      



BiTNode *  CreateBiTree() 
{

	BiTNode * T;
	char ch;	
    scanf("%c",&ch);
    if (ch=='0')
	{
		T=NULL;
	}
    else 
	{
       if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
          exit (NULL);
      T->str = ch;
      T->lchild=CreateBiTree();     // 构造左子树
      T->rchild=CreateBiTree();     // 构造右子树
    }
	return (T);
	
      
} 

void visit(int e)
{
	printf("%c ",e);
}

bool Preorder(BiTNode * T)
{                    
   if (T) 
   {
      visit(T->str);             
	  Preorder(T->lchild); 	 
      Preorder(T->rchild);//中序和后序相应的算法可以实现
   }
   else 
	   return true;
}

bool zhongPreorder(BiTNode * T)
{                    
   if (T) 
   {
      zhongPreorder(T->lchild); 	
	  visit(T->str);       
      zhongPreorder(T->rchild);//中序和后序相应的算法可以实现
   }
   else 
	   return true;
}

bool houPreorder(BiTNode * T)
{                    
   if (T) 
   {
      houPreorder(T->lchild);	    
      houPreorder(T->rchild);
	  visit(T->str); 
   }
   else 
	   return true;
}

void qianinorder(BiTNode *b)//传递的参数是指向根节点的指针
{ 

	BiTNode *stack[100];//建立一个栈用来存储节点  此处用的是指针数组实现栈的功能的
	BiTNode *p;
     int top;  
     if (b!=NULL)
       {
		top=1;                   
        stack[top]=b;		      	//根结点入栈
        while (top>0)              //栈不为空时循环
             {
			   p=stack[top];         //退栈并访问该结点
               top--;
               printf("%c ",p->str);
   				if (p->rchild!=NULL)     
				{                                
					top++;
                    stack[top]=p->rchild;           //右孩子入栈
				}
               if (p->lchild!=NULL)          //左孩子入栈 
			   { 
					top++;
                    stack[top]=p->lchild;
               }
					
			}
         }
}

void zhonginorder(BiTNode * b)
 { 
	 BiTNode *stack[123],*p;
     int top=0;  
     p=b;
     do
       {
		    while (p!=NULL)                   //扫描所有左结点  找到最左的节点  并且依次进栈 然后用p去指向最左的节点
            { top++;
               stack[top]=p;
               p=p->lchild;
            }
			if (top>0) 
            {
				 p=stack[top]; 
               //p所指结点为无左子树的结点或其左子树已遍历过
                 top--;
                 printf("%c ",p->str); //访问结点
                 p=p->rchild;               //扫描右子树
            }
        } while (p!=NULL || top!=0);
}

void houinorder(BiTNode *b)
{ 
	 BiTNode *stack[123],*p;
	 stack[0]=NULL;
     int tag[123], top=0;  
     p=b;
     do
       { 
		   while (p!=NULL)    //扫描左结点 并且将扫描过的节点进栈  将其标志为0
            { 
			   top++;
               stack[top]=p;
               tag[top]=0;
               p=p->lchild;
            }
           //p所指结点为无左子树的结点或其左子树已遍历过
             while ((top>0) && tag[top]==1)  
                                                          // p的左右子树都访问过
                 { 
					printf("%c ", stack[top]->str);  //访问结点
                    top--; 
                  }
               p=stack[top]; 
               if ((top>0) && (tag[top]==0))
                 { 
				   p=p->rchild;                //扫描右子树
                   tag[top]=1;         //表示当前结点的右子树已访问过  将其标志为1   证明其的右子树访问过
                 }
// 			   else
//				   p=NULL;
        } while (p!=NULL || top!=0);
}                    

int Depth (BiTNode * T )                       // 返回二叉树的深度
{                    
   int depthval,depthLeft,depthRight;	
   if (!T)    
	   depthval = 0;
   else
   {      
	   depthLeft = Depth(T->lchild);
       depthRight= Depth(T->rchild);            //是采用后序的递归算法 
       depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);
    } 
   return depthval;
}



void translevel(BiTNode* b)//用队列来实现
{  
	struct node
    { 
		BiTNode *vec[100];
        int f,r; 
    } q;
      q.f=0;
      q.r=0;                                  //置队列为空队列
   if (b!=NULL) printf("%c ",b->str);       //先输出
     q.vec[q.r]=b;                        //结点指针进入队列
     q.r=q.r+1;



    
	 while (q.f<q.r)               //队列不为空
  { 
	b=q.vec[q.f];             //队头出队列
    q.f=q.f+1;
    if(b->lchild!=NULL)         //输出左孩子，并入队列
       { 
		printf("%c ",b->lchild->str); 
        q.vec[q.r]=b->lchild;
        q.r=q.r+1;
       }
    if(b->rchild!=NULL)         //输出右孩子，并入队列
       {
		printf("%c ",b->rchild->str);
        q.vec[q.r]=b->rchild;
        q.r=q.r+1;
       }
   }
} 

void main()
{

	BiTNode *BiTree = CreateBiTree();
	printf("二叉树的深度为：%d\n",Depth(BiTree));
	printf("\n二叉树的先序遍历递归：");
	Preorder(BiTree);

	printf("\n二叉树的中序遍历递归：");
    zhongPreorder(BiTree);

	printf("\n二叉树的后序遍历递归：");
	houPreorder(BiTree);

	printf("\n二叉树的先序遍历非递归：");
	qianinorder(BiTree);

    printf("\n二叉树的中序遍历非递归：");
	zhonginorder(BiTree);

    printf("\n二叉树的后序遍历非递归：");
	houinorder(BiTree);

	printf("\n二叉树的层次的非递归：");
	translevel(BiTree);


}