数据结构之树操作

 本文打出了大部分树的操作 和部分知识点   还有自己编写的哈夫曼树中的select函数（看书上是直接调用便自己打出了自己理解的select函数，有错请在评论区指出）

后续会补充栈，队列，线性表操作总结。

       //二叉树树的存储结构
typedef struct BeTnode{
    char data;
    struct BeTnode*left,*right;
}BeTnode,*BeTree;       
        //        建立先序二叉树   要正好返回 
        BeTree jianlierchashu (BeTree t)
        {
            char ch;
            scanf("%c",&ch);
            if(ch=='#')
            {
                return ;
            }
            if(ch!='#')
            {
                t=(BeTree) malloc (sizeof(BeTnode));
                t->data=ch;
                t->left=NULL;
                t->right=NULL;
                jianlierchashu(t->left);
                jianlierchashu(t->right);
                return t;
            } 
                
        }
         
         //     求二叉树叶子节点的个数
int yezijiediangeshu(BeTree t)
{
    if(t==NULL)
    {
        return 0;
    }
    if(t->left==NULL&&t->right==NULL)
    {
        return 1;
    }
    int n=0,m=0;
    n=yezijiediangeshu(t->left);
    m=yezijiediangeshu(t->right);
    return m+n ;
         }         
         
//          求二叉树节点个数
int  jiediangeshu(BeTree t) 
{
        if(t==NULL)
        {
            return 0;
        }
        int n=0,m=0;
    n=jiediangeshu(t->left);//0 1
    m=jiediangeshu(t->right);//0 
    return 1+n+m;//1
}

 
              //二叉树树的深度
int shendu(BeTree t)
{
    if(t==NULL)
    return 0;
    int n=0,m=0;
    n=shendu(t->left);        
    m=shendu(t->right);
    return n>m?n+1:m+1; 
}    

           
//      中序线索二叉树 
/*
       主要是添加两个标识域
ltage=    1-则左指针域前驱       0-则左指针域左孩子     
rtage=    1-则右指针域后驱       0-则右指针域右孩子 
              物理存储结构 
*/ 
typedef struct TNode{
    char data;
    struct TNode *left;
    struct TNode *right;
    int ltage;
    int rtage;
}TNode,*BTNode; 
    void xiansuoerchashu(BTNode t)
    {
        BTNode pro=NULL;
        if(t)
        {
        xiansuoerchashu(t->left);     //因为为中序所以  要从左开始  递归调用到最左   返回
        if(t->left==NULL)
        {
        t->ltage=1;//设置标记 
        t->left=pro;    //pro为前驱    全局变量    初始值为NULL 
        } 
         else
         t->ltage=0;
         if(pro->right==NULL)    //这里为什么是pro那？因为现在操作的是t   只有t和pro的地址   所以要填充pro的右指针域 
         {
             pro->rtage=1;
             pro->right=t;
          }
          else
          pro->rtage=0; 
          pro=p;       //因为当前节点的操作完成了   所以将其赋值    递归右子树 
          xiansuoerchashu(t->right);
        }
        
         
     } 

           //树的存储 -1   双亲表示法 
    typedef struct PTNode{
        char data;
        int parent;//  双亲位置域 
    }PTNode;      //节点
    //树结构
    # define MAXSIZE 100
    typedef struct {
        PTNode node[MAXSIZE];//创建数组   可以存放MAXSIZE个节点     
        int r,n; //根节点位置个数 
    }PTree;      
    
    
    
    
       
        //树的存储 -2  孩子表示法       
    //孩子节点结构的定义     
typedef struct CTNode{
    int child;  //    int 类型    为该孩子在数组中的下标 
    struct CTNode* nexthaizi;        // 双亲节点的下一个孩子 
}*childptr;         
    //双亲节点结构
    typedef struct          
         {
             char data;
             childptr firstchild;      //孩子链表的头指针 
         }CTBox;
    //树结构
    typedef struct {
            CTBox node[MAXSIZE];
            int r,n;     //根节点的位置和节点数 
    }CTree;
     //方便找孩子  不方便找双亲    则添加一个双亲节点 
    typedef struct          
         {
             char data;
             int   pro; 
             childptr firstchild;      //孩子链表的头指针 
         }CTBox;
         //带双亲的孩子链表 
         
         
         
         //树的存储 -3   二叉链表表示法       
         /*
         左指针域    ---第一个孩子结点
         右指针域    ---向右一个  兄弟结点 
         找双亲比较困难 
         */
         typedef struct CTNode{
             char data;
             struct CTNode * lefthaizi;
                 struct CTNode *rightxdi; 
         }CTNode;
         
         
         
         
         
         
         
         //哈夫曼树
          // 结点结构     
    typedef struct Hafuman  //顺序存储  ---     1维结构数组 
    {
        //权值
        //双亲  左孩子右孩子下标
        int weight;
        int parent,left,right; 
   }Hafuman,*THafuman; //---是动态数组存储一个哈夫曼树

    //建立哈夫曼树（最优二叉树）   
    
    /*
    权值越大越靠近根
    所以找权值要从小到大  从下到上进行构造哈夫曼树 
    每个权值都是根    权值实际也是叶子节点 
    而且不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
    
    
            王卓老师的口诀 
     构造森林全是根   选用二小造新树
     删除二小添新人   重复2,3剩单根 
    */
   void creatHfm(THafuman t,int n)    //   t是哈夫曼树      n是 有权值的个数（叶子节点）    需要合并n-1次   
   {
       if(n<=1)
       return ;
/*
1.    建数组 for循环初始化  3个域均为0 
2.    选出无双亲 中权值最小的两个  组成新的二叉树
3.    组成后    权值最小的两个  消失（有双亲） 
*/        
    int m=2*n-1;
       t=(THafuman) malloc(sizeof(Hafuman)*(1+m));    //从1开始使用
    for(int i=1;i<m+1;i++)
    {
        t[i].left=0;
        t[i].parent=0;
        t[i].right=0;
    }   
    for(int i=1;i<n+1;i++)
    {
        scanf("%d",&t[i].weight);
    }    
       //-----------------------------------------------------------
  //因为要    选出无双亲 中权值最小的两个  组成新的二叉树   所以要自定义函数胡
 int s1,s2;
 
  for(i=n+1;i<m+1;i++)
  {
     select(t,&s1,&s2,i);  
          t[i].weight=s1+s2;
    t[i].right=s1;
    t[i].left=s2;           
  }     
       
       
    } 
    
    
    int cmp(int *x, int *y) {
    return *x - *y;
}
  void select(THafuman *t,int &s1,int &s2,int n)    //s1,s2是需要返回的值 
  {
      int m=sizeof(t)/sizeof(Hafuman);
    THafuman a[m];//指针数组 
      int j=0;
      
    for(int i=1;i<m;i++)
    {
    if(t[i].parent==0)
    {
     a[j]=t[i];    
        j++;
    }
    }   int i=0;
      qsort(a,j,sizeof(Hafuman),cmp);
      for(i=0;i<m;i++)
      {    int p=0;
           if(a[0]==t[i]||a[1]==t[i])
           {
                      p++;
                   t[i].parent=n;
                   if(p==1)
                *s1=i;  
                   else
                   *s2=i;
           }     
    }
  
          }        
//哈夫曼编码
//算概率大  则权大     则要靠近根
//左分支标记为0，右分支标记为1进行编码     
/*
从根到叶子进行编码 
*/         
         
         
         
         
         
         
         
         
         
         
         

                                      本篇文章主要是树的操作