数据结构-二叉树操作（创建、先序、中序、后序遍历、计算叶子节点数目、计算二叉树深度、左右子树交换、随机数列产生排序树、查找结点、删除节点、广度遍历、非递归先序遍历）C语言源码（全）

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define null 0
#define ElemType int
#define STACK_SIZE 100    //栈初始长度 
#define STACK_RE_SIZE 10  //栈再分配增加长度
#define nothing 0



typedef struct Binode{               //二叉树结构定义 
	ElemType data;
	struct Binode *lchild,*rchild,*parent;
}Binode,*Bitree;
int deep;
int node;
int tree[12][50];   //打印树形状
int troot;


void init(Bitree &T) //初始化 
{
  T=null;
}
void great(Bitree &T,Bitree &I)  //创建 
{
  int n;
  scanf("%d",&n);
  if(n==nothing)
     T==null;
  else
  {
     T=(Bitree)malloc(sizeof(Binode));
     T->lchild=null;
	 T->rchild=null;
     T->data=n;
	 T->parent=I;
     great(T->lchild,T);
     great(T->rchild,T);
  }
} 

void destory(Bitree &T)
{
  if(T)
  {
    if(T->lchild)
       destory(T->lchild);
    if(T->rchild)
       destory(T->rchild);
    free(T);
  }
}
  
void pre_tra(Bitree T) //先序遍历 
{
  if(T)
  {
     printf("%d ",T->data);
     pre_tra(T->lchild);
     pre_tra(T->rchild);
  }
}
void in_tra(Bitree T)//中序遍历 
{
  if(T)
  {
     in_tra(T->lchild);
     printf("%d ",T->data);
     in_tra(T->rchild);
  }
}
void pos_tra(Bitree T)  //后序遍历 
{
  if(T)
  {
     pos_tra(T->lchild);
     pos_tra(T->rchild);
     printf("%d ",T->data);
  }
}
int pre_node(Bitree T)  //求叶节点 
{
  if(T)
  {
     if(T->lchild==null&&T->rchild==null) node++;
     pre_node(T->lchild);
     pre_node(T->rchild);
  }
    return node;
}

int pre_deep(Bitree T)  //求深度 
{
  if(T)
 {   
     pre_deep(T->lchild);
     pre_deep(T->rchild);
     deep++;
 }
 return deep;
}

void exchange(Bitree T)  //左右交换 
{ 
  if(T)
  {
     Bitree t;
     t=T->lchild;
     T->lchild=T->rchild;
     T->rchild=t;
     exchange(T->lchild);
     exchange(T->rchild);
  }
}
void bisort(Bitree &root,Bitree &pa,Bitree &T,int elem[],int i)  //建立二叉排序树 
{
  if(elem[i]!=0)
  {  
     if(root==null)   //空树 
     {
         root=(Bitree)malloc(sizeof(Binode));
         root->data=elem[i];root->lchild=null;root->rchild=null;root->parent=null;
         if(elem[i+1]>root->data) 
	         bisort(root,root,root->rchild,elem,i+1);
         else 
	         bisort(root,root,root->lchild,elem,i+1);
     }
   else if(!T)
   {   
      T=(Bitree)malloc(sizeof(Binode));
      T->data=elem[i];T->lchild=null;T->rchild=null;T->parent=pa;
      if(pa->data<T->data) pa->rchild=T;
      else 
	      pa->lchild=T;
       T->parent=pa;
       bisort(root,root->parent,root,elem,i+1);
   }
   else
   {
    if(elem[i]>T->data)
      bisort(root,T,T->rchild,elem,i);
    else
      bisort(root,T,T->lchild,elem,i);
   }
  }
}
void biseach(Bitree T,int i,int j)  //二叉查找 
{
  if(T) 
  {   
    if(T->data==i)
    {
      printf("已找到,比较次数为%d\n",j);
      return;
    }
  else if(i>T->data)
     biseach(T->rchild,i,j+1);
  else 
     biseach(T->lchild,i,j+1); 
  }
  else
  {
     printf("未找到,比较次数为%d\n",j);
     return; 
  }	
} 
int bidel(Bitree &T,int e) //删除二叉树里面的元素
{
  if(T)
  {  
     if(T->data==e)
     {
         if(T->parent==null)          //根节点 
         {
             if(T->lchild==null&&T->rchild==null)    //只有一个根
                 T=null;
             else if(T->lchild==null)  //只有右子树 
             {
                  T->rchild->parent=null;
                  T=T->rchild;
             }
             else if(T->rchild==null)//只有左子树 
             {
                  T->lchild->parent=null;
                  T=T->lchild; 
             }
             else 
             {
                  Bitree p;
                  p=T->lchild;
                 if(p->rchild)
                {
                  while(p->rchild) p=p->rchild;
                  T->data=p->data;
                  p->parent->rchild=null;
                }
                 else
                {
                  T->data=p->data;
                  T->lchild=null;
                }
        free(p);
             }
   }
  else if(T->lchild==null&&T->rchild==null)  //叶节点 
  { 
    if(T->parent->lchild==T&&T->parent!=null) 
    {
         T->parent->lchild=null;
         free(T); 
    }
    else 
    {
         T->parent->rchild=null;
          free(T);
    }
  }
  else if(T->lchild==null)   //单 
  { 
     if(T->parent->lchild==T) 
     {
         Bitree p;
         p=T->rchild;
         p->parent=T->parent;
         T->parent->lchild=p;
     }
     else
     {
         Bitree p;
         p=T->rchild;
         p->parent=T->parent;
         T->parent->rchild=p;
     }
  }
  else if(T->rchild==null)  //单 
  {
      if(T->parent->lchild==T) 
      {
         Bitree p;
         p=T->lchild;
         p->parent=T->parent;
         T->parent->lchild=p;
      }
      else
      {
          Bitree p;
          p=T->lchild;
          p->parent=T->parent;
          T->parent->rchild=p;
      }
  }
  else                                  //双孩子 
  {
     Bitree p;
     p=T->lchild;
     if(p->rchild!=null)              //左子树有右子树 
     {
         while(p->rchild!=null) p=p->rchild;
         p->parent->rchild=null;
         T->data=p->data;    //覆盖 
         free(p);
     }
     else       //左结点为左子树中最大的;
     {
         T->data=p->data;
         T->lchild=null;
         free(p); 
     } 
  } 
 }
   else if(e>T->data)
         bidel(T->rchild,e); 
   else 
         bidel(T->lchild,e);  
  }
 else
 { 
     printf("未找到\n"); 
     return 0; 
 }
}
int choice()
{ 
  printf("二叉树操作选项\n"); 
  printf("1.创建二叉树\n2.先序遍历\n3.中序遍历\n4.后序遍历\n5.计算叶节点数目\n");
  printf("6.计算二叉树深度\n7.左右子树交换\n8.随机序列生成排序树\n9.排序树查找结点\n10.排序树删除节点\n");
  printf("11.显示树\n12.广度遍历\n13.非递归先序遍历\n"); 
  printf("0.退出\n");
  int c;
  scanf("%d",&c);
  return c;
} 
int display(Bitree T,int i,int j) //打印树 
{  
  if(i>12||j>50||i<0||j<0)
  {
     printf("树太大打印不了\n");
     return 0;
  }
  if(T)
  {
  
    if(troot==0)
    {   
	     troot++;
     	tree[i][j]=T->data;
  	     if(T->lchild)
  	     {
  	     	tree[i+1][j-1]=-101;
  	    	tree[i+2][j-2]=-101;
  	    	display(T->lchild,i+3,j-3);
	     }
	     if(T->rchild)
	     {
	     	tree[i+1][j+1]=-102;
		     tree[i+2][j+2]=-102;
	     	display(T->rchild,i+3,j+3);
	}
  }
   else
   {
         tree[i][j]=T->data;
         if(T->lchild)
         {
             tree[i+1][j-1]=-101;
             display(T->lchild,i+2,j-2);
         }
         if(T->rchild)
         {
             tree[i+1][j+1]=-102;
             display(T->rchild,i+2,j+2);
         }
   }
   return 1;
 }
}
void spa_tra(Bitree T)
{
  if(T)
  {
     Bitree a[60];
     int i=0,j=0;
     Bitree p;
     a[i]=T; i++;
    while(j<i)
   {
     p=a[j];
     printf("%d ",p->data);
     j++;
      if(p->lchild) 
      {
         a[i]=p->lchild;
         i++;
      }
      if(p->rchild)
      {
         a[i]=p->rchild;
         i++;
      }
		
   }
  }
}
void tra(Bitree T)//非递归遍历
{
  Bitree p,tree[60];
  int i=0;
  tree[i]=T;
   i++;
   while(i)
   {
   	 p=tree[i-1];
   	 i--;
   	 printf("%d ",p->data);
   	 if(p->rchild) {
		tree[i]=p->rchild;
		i++;
		}
	 if(p->lchild){
	 	tree[i]=p->lchild;
	 	i++;
	   }
   }
} 


int main()
{   
  Bitree T,pt=null;
  init(T);
  srand((int)time(NULL));
  int i,j,n;
  int *elem;
  while(1)
  {
     switch(choice())
     {
         case 1:destory(T);init(T);
         printf("请输入树的先序遍历序列:");great(T,pt);printf("创建成功\n");break;
         case 2:pre_tra(T);break;
         case 3:in_tra(T);break;
         case 4:pos_tra(T);break;
         case 5:node=0;printf("叶节点数为%d\n",pre_node(T));break;
         case 6:deep=0;printf("深度为%d\n",pre_deep(T));break;
         case 7:exchange(T);break;
         case 8:destory(T);init(T);printf("请输入随机数个数:");scanf("%d",&n);
	  	        if(n<=0){ printf("个数不合法\n");break;}
	  	        elem=(int*)malloc((n+1)*sizeof(int));
	  	        for(i=0;i<n;i++) elem[i]=rand()%100+1; elem[i]=0;
		        bisort(T,pt,T,elem,0);break;
         case 9:printf("请输入要查找的元素:");scanf("%d",&n);biseach(T,n,0);break;
         case 10:printf("请输入要删除的元素:");scanf("%d",&n);bidel(T,n);break;
         case 11:for(i=0;i<12;i++) for(j=0;j<50;j++) tree[i][j]=-103;troot=0;
		         if(display(T,0,24))
		         {
		          for(i=0;i<12;i++) 
		          {
		             for(j=0;j<50;j++) 
		             { 
		                 if(tree[i][j]>=-100)
		                     printf("%d",tree[i][j]);
		                 else if(tree[i][j]==-101)
		                     printf("/");
		                 else if(tree[i][j]==-102)
		                     printf("\\");
		                 else
		                     printf(" ");
		             }
		             printf("\n");
		          }
		         }break;
         case 12:spa_tra(T);break; 
         case 13:tra(T);break; 
         case 0:return 0;
     } 
  } 
} 

快看，这才是重点！我想能看到这里的同学，无外乎两种人：来拷贝代码的人 和 来拷贝代码的人。

但，在拷贝走的时候，你要想清楚一件事，把代码拷走之后有个蛋用，搞明白对你来说才是最重要的。

好了，就酱紫。

老铁，这要是都不赞，说不过去吧！！！哦，对了，你这么好看，关注一下呗。。。

最后对自己说：
你现在所遭遇的每一个不幸，都来自一个不肯努力的曾经。