数据结构算法整理-05-二叉树

#include <stdio.h>
#include <stdlib.h>
#define Maxsize 20

typedef  char   datatype;
typedef struct BiNode
{
    datatype data;
    struct BiNode  *lchild, *rchild;
}bitree;

//前序遍历的递归算法 
void   PreOrder( bitree  *root) 
{
        if (root ==NULL)  return;     
        else {
            printf("%d  ",root->data);         
            PreOrder( root->lchild);    
            PreOrder(root->rchild);    
        }
 }

//中序遍历的递归算法 
void InOrder (bitree  *root)
{
         if (root==NULL) return;     
         else {
         	InOrder(root->lchild); 
 	     	printf("%d  ",root->data);
	       	InOrder(root->rchild);
         }
}

//后序遍历的递归算法 
void  PostOrder(bitree  *root)
{ 
    if (root==NULL) return; 
    else {
         PostOrder(root->lchild); 
         PostOrder(root->rchild); 
         printf("%d  ",root->data);
    }
}

//前序遍历的非递归算法  
void  PreOrder1( bitree  *root ) 
{   bitree  *p=root ;
 	bitree  *s[Maxsize]; int top;
     top= -1;      //采用顺序栈，并假定不会发生上溢
     while (p!=NULL || top!= -1)
     {
         while (p!= NULL)
         {
			printf("%d  ",p->data);
   			s[++top]=p;
      		p = p->lchild;  
         }
         if (top!= -1) { 
             p=s[top--];
             p=p->rchild;  
         }
     }
}

//以递归方式创建二叉树,如输入：ABD##E##C#FHJ##K##I## （按前中后序输入，空节点用#代替）
bitree * creatBitree()
{   bitree *root ;char ch;
    ch=getchar();
    if (ch == '#')     root = NULL; 
    else {
        root=(bitree*)malloc(sizeof(bitree)); 
        root->data=ch; 
        root->lchild =creatBitree(); 
        root->rchild= creatBitree(); 
     } 	
    return root;
}

//删除二叉树 
bitree * deleteTree(bitree  *root)
{	if( root!=NULL)
	{   
	 	deleteTree(root->lchild);
	 	deleteTree(root->rchild);
	    free(root);	
	} 	
   root=NULL; //free只是释放了指针所指空间，并没有自动将指针root为空，需要手动置root为空。只有删除完所有结点置root为空，测试整颗二叉树上结点总数才为0 
   return root;
}

//计算二叉树的深度 
int  Depth(bitree *root)
{  int hl = 0, hr = 0; 
    if (root == NULL) return 0;
    else {
         hl= Depth(root ->lchild);
         hr= Depth(root ->rchild);
         return hl>=hr ? (hl+1) : (hr+1);
    }
}

int count=0;
void CountNode(bitree *root)  //n为结点总数 
{
    if (root) {
    	count++;
    	CountNode(root->lchild);
    	CountNode(root->rchild);
   }
}

//计算叶子结点总数 
int count=0;
void leafNum(bitree  *root)
{
	if (root) {
		leafNum(root->lchild);
    	leafNum(root->rchild);
    	if(root->lchild==NULL&&root->rchild==NULL)
	    	count++;
   }
}

//以广义表的形式输出二叉树结构
void displayBitree(bitree  *root)
{
	if( root == NULL)
	{
		printf(" "); return ;
	}
	
	printf("%d", root->data);
	
	if( root->lchild || root->rchild)
	{
		printf("\(");
		displayBitree(root->lchild);
		printf(",");
		displayBitree(root->rchild);
		printf("\)");
	}	
}