Data structure C language implementation - binary tree

This article records the binary tree implementation code and Huffman tree implementation of my own learning data structure and algorithm course

tree.h

#ifndef TREE_H_
#define TREE_H_
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdbool.h>
typedef char NodeType;
#define MAX_NODE 1000
//*****二叉树*****//
typedef struct Node{
    NodeType data;
    struct Node * Lchild;
    struct Node * Rchild;
}BTnode,*BTree;

void  Creat_BT_Pre ( BTree * root ) ;  //Create binary tree in pre-order 
void  Traverse_Pre ( BTree root ) ;   // Traverse binary tree in pre-order 
void  Traverse_Mid ( BTree root ) ;   // Traverse binary tree in in-order 
void  Traverse_End ( BTree root ) ;   //After Order traversal of the binary tree 
int  Get_TreeDepth ( BTree T ) ;      //return the depth of the tree 
int  Get_Leafnode ( BTree T ) ;       //return the number of leaf nodes 
BTree pre_mid_CreatBtree (char  * pre , char  * mid , int len ) ; //Create binary tree BTree according to preorder 
midorder mid_end_CreatBtree ( char  * last , char  * mid , int len ) ; //Create binary tree according to midorder and postorder 
bool Find_Elem ( BTree T , NodeType node ) ; 
BTree Find_Common_Ancestor ( BTree T , NodeType node1 , NodeType node2 ) ; //Find the nearest common ancestor of two nodes
void  Change_Left_Right ( BTree * T ) ; //Swap left and right subtrees 
//***************//

//*****Huffman Tree*****// 
typedef  struct { 
    int Weight ; 
    int Parent ; 
    int Lchild ; 
    int Rchild ; 
} HuffmanNode , HuffmanTree [ MAX_NODE + 1 ] ; // Unit 0 does not need 
typedef  char  * HuffmanCode [ MAX_NODE + 1 ] ;

void  Get_two_Min ( HuffmanTree ht , int len , int  * min_1_tag , int  * min_2_tag ) ;   //Get two minimum nodes 
void  Init_HuffmanTree ( HuffmanTree ht , int i , int Weight , int Parent , int Lchild , int Rchild ) ;   //Initialization 
void  CreatHuffmanTree ( HuffmanTree ht , int w [ ], int n ) ;   //Create Huffman Tree 
int  Node_LengthWeight ( HuffmanTree ht , int i ) ;   //Get the depth of the current node 
int  Calculate_LengthWeight ( HuffmanTree ht , int n ) ;  //Calculate the weighted path length 
//** *************// 
# endif
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
#include"tree.h"

//Create binary tree in preorder 
void  Creat_BT_Pre ( BTree * root ) 
{ 
    NodeType c ; 
    scanf ( "%c" , & c ) ; 
    if ( c !=  '#' ) 
    { 
        ( * root )  =  ( BTree ) malloc ( sizeof ( BTnode ) ) ; 
        ( * root ) -> data = c ; 
        Creat_BT_Pre ( &( * root ) -> Lchild ) ; 
        Creat_BT_Pre ( & ( * root ) -> Rchild ) ; 
    } else 
    { 
        ( * root )  =  NULL ; 
    } 
} 
// recursive traversal method 
void  Traverse_Pre ( BTree root ) // preorder traversal of binary tree 
{ 
    if ( root !=  NULL ) 
    { 
        printf ( "%c " , root -> data ); 
        Traverse_Pre ( root -> Lchild ) ; 
        Traverse_Pre ( root -> Rchild ) ; 
    } 
} 
void  Traverse_Mid ( BTree root ) //Inorder traversal of binary tree 
{ 
    if ( ( root )  !=  NULL ) 
    { 
        Traverse_Mid ( root -> Lchild ) ; 
        printf ( "%c " , root -> data ) ; 
        Traverse_Mid ( root-> Rchild ) ; 
    } 
} 
void  Traverse_End ( BTree root ) //Post-order traversal of binary tree 
{ 
    if ( ( root )  !=  NULL ) 
    { 
        Traverse_End ( root -> Lchild ) ; 
        Traverse_End ( root -> Rchild ) ; 
        printf ( "% c " , root -> data ) ; 
    } 
} 
//returns the depth of the tree 
int  Get_TreeDepth ( BTree T)
{
    int m,n;
    if(T == NULL)
    {
        return 0;
    }else
    {
        m = Get_TreeDepth(T->Lchild);
        n = Get_TreeDepth(T->Rchild);
        return m>n?(m+1):(n+1);
    } 
}

//返回叶子结点数
int Get_Leafnode(BTree T)
{
    if(T == NULL)
    {
        return 0;
    }else
    {
        if(T->Lchild == NULL && T->Rchild == NULL)
        {
            return 1;
        }else
        {
            return Get_Leafnode(T->Lchild)+Get_Leafnode(T->Rchild);
        }
    }
}


//Create binary tree BTree according to preorder 
midorder pre_mid_CreatBtree ( char  * pre , char  * mid , int len ) 
{ 
    BTree T ; 
    int index = 0 ; 
    char ch = pre [ 0 ] ; 
    if ( len ==  0 ) 
    { 
        return  NULL ; 
    } 
    while ( mid [ index ]  != ch ) 
    { 
        index++;
    }
    T = (BTnode*)malloc(sizeof(BTnode));
    T->data = ch;
    T->Lchild = pre_mid_CreatBtree(pre+1,mid,index);
    T->Rchild = pre_mid_CreatBtree(pre+index+1,mid+index+1 , len - index - 1 ) ; _

    return T ; 
}
 //Create a binary tree 
BTree according to inorder and postorder mid_end_CreatBtree ( char  * last , char  * mid , int len ) 
{ 
    BTree T ; 
    if ( len ==  0 ) 
    { 
        return  NULL ; 
    } 
    char ch = last [ len - 1 ] ; 
    int index =  0 ; 
    while ( mid [ index] != ch)
    {
        index++;
    }
    T =(BTnode*)malloc(sizeof(BTnode));
    T->data = ch;
    T->Lchild = mid_end_CreatBtree(last,mid,index);
    T->Rchild = mid_end_CreatBtree(last+index,mid+index+1,len-index-1);

    return T;
}

//find the nearest common ancestor of two nodes 
bool Find_Elem ( BTree T , NodeType node ) 
{ 
    if ( T ==  NULL ) 
    { 
        return  0 ; 
    } 
    if ( T -> data == node ) 
    { 
        return  1 ; 
    } else 
    { 
        return  Find_Elem ( T -> Lchild , node )  ||  Find_Elem ( T -> Rchild , node ); 
    }

} 
BTree Find_Common_Ancestor ( BTree T , NodeType node1 , NodeType node2 ) 
{ 
    if ( T ==  NULL  || T -> data == node1 || T -> data == node2 ) 
    { 
        return  NULL ; 
    } 
    int label_left =  Find_Elem ( T -> Lchild , node1 ) ; //Find node 1 in the left subtree, if not found, it must be in the right subtree, if found is 1, if not found is 0 
    int label_right=  Find_Elem ( T -> Lchild , node2 ) ; //Find node 2 in the left subtree, if not found, it must be in the right subtree, if found is 1, if not found is 0 
    if ( label_left != label_right ) //two If the data is in the left and right subtrees of the node, the node must be its nearest ancestor 
    { 
        return T ; 
    } else //The two are equal, both are on the left or both are on the right 
    { 
        if ( label_left ==  1 ) 
        { 
            return  Find_Common_Ancestor ( T -> Lchild , node1 , node2 ) ; 
        } 
        if (label_right == 0)
        {
            return Find_Common_Ancestor(T->Rchild,node1,node2);
        }
    }
}

//交换左右子树
void Change_Left_Right(BTree *T)
{
    BTnode *temp;
    if((*T) != NULL)
    {
        temp = (*T)->Lchild;
        (*T)->Lchild = (*T)->Rchild;
        (*T)->Rchild = temp;
        Change_Left_Right(&(*T)->Lchild);
        Change_Left_Right(&(*T)->Rchild);
    }
}

Huffman tree---- weighted path length // 
void  Get_two_Min ( HuffmanTree ht , int len , int  * min_1_tag , int  * min_2_tag ) 
{ 
    int m1 , m2 , i ; //m1 stores the smallest, m2 stores the second smallest 
    int m1_index , m2_index , temp ; 
    m1 = INT_MAX ; 
    m2 = INT_MAX - 1 ; 
    m1_index = m2_index =  - 1 ; _
    for(i=1;i<=len;i++)
    {
        if(ht[i].Parent == 0)//没有父节点
        {
            if(ht[i].Weight < m1 || ht[i].Weight < m2)
            {
                if(ht[i].Weight <m1 && ht [ i ] . Weight >= m2 ) // less than m1, greater than or equal to m2, replace m1 
                { 
                    m1 = ht [ i ] . Weight ; 
                    m1_index = i ; 
                    if ( m1 == m2 ) //because m2 is in Before encounter 
                    { 
                       temp = m1_index ; 
                       m1_index = m2_index ; 
                       m2_index = temp; 
                    } 
                } else  if ( ht [ i ] . Weight < m2 && ht [ i ] . Weight >= m1 ) // less than m2, greater than or equal to m1, replace m2 
                { 
                     m2 = ht [ i ] . Weight ; 
                     m2_index = i ; 
                } else  if ( ht [ i ] . Weight < m2 &&ht [ i ] . Weight < m1 ) // replace the larger one 
                { 
                    if ( m1 > m2 ) 
                    { 
                        m1 = ht [ i ] . Weight ; 
                        m1_index = i ; 
                    } else 
                    { 
                        m2 = ht [ i ] . Weight ; 
                        m2_index = i ; 
                    } 
                } 
            }
        }

    }
    if(ht[m1_index].Weight > ht[m2_index].Weight)
    {
        temp = m1_index;
        m1_index = m2_index;
        m2_index = temp;
    }
    *min_1_tag = m1_index;
    *min_2_tag = m2_index;
}

void Init_HuffmanTree(HuffmanTree ht,int i,int Weight,int Parent,int Lchild,int Rchild)
{
    ht[i].Weight = Weight;
    ht[i].Parent = Parent;
    ht[i].Lchild = Lchild;
    ht[i].Rchild = Rchild;
}

void CreatHuffmanTree(HuffmanTree ht,int w[],int n)
{
    int i,m,min_1,min_2;
    for(i=1;i<=n;i++)//从1开始
    {
        Init_HuffmanTree(ht,i,w[i],0,0,0);
    }
    m = 2*n-1;
    for(i=n+1;i<=m;i++)
    {
        Init_HuffmanTree(ht,i,0,0,0,0);
    }
    for(i=n+1;i<=m;i++)
    {
        Get_two_Min(ht,i-1,&min_1,&min_2);
        //cout<<min_1<<" "<<min_2<<endl;
        ht[i].Weight = ht[min_1].Weight + ht[min_2].Weight;
        ht[i].Lchild = min_1;
        ht[i].Rchild =min_2 ; 
        ht [ min_1 ] . Parent = ht [ min_2 ] . Parent = i ; 
    } 
}

int Node_LengthWeight(HuffmanTree ht,int i)
{
    HuffmanNode *node;
    int count = 0;
    node = &ht[i];
    while(node->Parent != 0)
    {
        count++;
        node = &ht[node->Parent];
    }
    return count; 
}

int Calculate_LengthWeight(HuffmanTree ht,int n)
{
    int sum = 0;//带权乘积
    int i,value;
    for(i=1;i<=n;i++)
    {
        value = Node_LengthWeight(ht,i);
        sum += value * ht[i].Weight; 
    } 
    return sum ; 
} 
/************************Huffman tree----length of path with weights ********* ************/

Huffman tree----Huffman coding // 
void  Creat_HuffmanCode ( HuffmanTree ht , HuffmanCode hc , int n ) 
{ 
    char  * cd ; 
    int i , c , p , start ; 
    //HuffmanNode *node; 
    cd =  ( char  * ) malloc ( sizeof ( char ) * n + 1 ) ; 
    cd [ n - 1 ]  =  '\0';
    for(i=1;i<=n;i++)
    {
        start = n-1;
        c = i;
        p = ht[i].Parent;
        while(p != 0 )
        {
            start --;
            if(ht[p].Lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';

            c = p;
            p = ht[p].Parent;
        }
        hc[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy(hc[i],&cd[start]);
    }
    free(cd) ; 
}

void  Printf_Code ( HuffmanCode hc , int n ) 
{ 
    int i ; 
    for ( i = 1 ; i <= n ; i ++ ) 
    { 
        printf ( "%s\n" , hc [ i ] ) ; 
    } 
} 
/*** ********************Huffman Tree----Huffman Coding ******************** ***/
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327

Related: Data structure C language implementation - binary tree