C数据结构的通用树结构和二进制排序树的基本操作

二叉树: 二叉树是每个节点最多具有两个子树的树结构. 二叉树可以是一个空集；根可以有一个空的左或右子树；或左右子树都为空.

完整的二叉树: 高度为h且由2 {h} – 1个节点组成的二叉树称为完整的二叉树.

完整的二叉树: 在二叉树中，只有最低的两个节点的度数可以小于2，最低层的叶节点集中在左侧的几个位置. 这样的二叉树称为完整二叉树. 完整的二叉树必须是完整的二叉树，完整的二叉树可能不是完整的二叉树.

二进制搜索树: 二进制排序树也称为二进制搜索树，也称为二进制搜索树

二进制排序树是具有以下属性的空树或二进制树:

B树: B树是一种多路搜索树（不是二进制）数据结构二叉排序树，主要用于提高硬盘上数据的存储和读取速度，从而可以减少访问磁盘的次数.

B +树: B +树将所有存储值的节点放入叶节点中，以便叶节点最终形成一个有序的链表. 进一步提高阅读速度.

B *树: 它是B +树的一种变体，同级的指针被添加到B +树的非根节点和非叶节点.

平衡二进制搜索树: 平衡二进制搜索树（自平衡二进制搜索树）也称为AVL树（与AVL算法不同），并且具有以下属性: 它是空树或其绝对值左右子树之间的高度差之和不超过1，左右子树均为平衡二叉树. 平衡二叉树的常用方法是红色树和黑色树.

二叉树遍历

二进制排序树的基本操作

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;
}Tree, *PTree;//定义树节点的结构体
//创建只有一个根结点的二叉树
PTree create(int value){
    PTree pt = (PTree)malloc(sizeof(Tree));
    pt->data=value;
    pt->left=pt->right=NULL;
    return pt;
}
 
//在二叉树中插入结点， 需要使用二级指针
void createBiTree(PTree *p, int value){
    if(*p == NULL){
        *p = (PTree)malloc(sizeof(Tree));
        (*p) -> data = value;
        (*p) -> left = (*p)-> right =NULL;
        return;
    }
    if((*p)->data == value){
        return;
    }
    else{
        if((*p)->data > value){
            return createBiTree(&(*p) -> left,value);
        }
        else{
            return createBiTree(&(*p) -> right,value);
        }
    }    
}
//前序打印
void pre_read_tree(PTree p){
    if(p==NULL){return;}
    else{
        printf("%d\n",p->data);
        pre_read_tree(p->left);
        pre_read_tree(p->right);
    }
}
//中序打印
void mid_read_tree(PTree p){
    if(p==NULL){return;}
    else{
        pre_read_tree(p->left);
        printf("%d\n",p->data);        
        pre_read_tree(p->right);
    }
}
//后序打印
void rear_read_tree(PTree p){
    if(p==NULL){return;}
    else{
        pre_read_tree(p->left);                
        pre_read_tree(p->right);
        printf("%d\n",p->data);
    }
}
//查找元素
PTree find_node(PTree tree, int value){
    if(tree==NULL){
        return NULL;
    }
    if(tree->data == value){
        return tree;
    }
    else{
        if(value<tree->data){
            find_node(tree->left,value);
        }
        else{
            find_node(tree->right,value);
        }
    }
}
//清空整棵树
PTree clean_tree(PTree tree){
    if(tree!=NULL){
        clean_tree(tree->left);
        clean_tree(tree->right);
        free(tree);
    }
    return NULL;
}
//查找二叉排序树的最大值
PTree max_BTree(PTree tree){
    if(tree ==NULL){
        return NULL;
    }
    else{
        if(tree->right==NULL){
            return tree;
        }
        else{
            return max_BTree(tree->right);
        }       
    }
}
//查找二叉排序树的最小值
PTree min_BTree(PTree tree){
    if(tree ==NULL){
        return NULL;
    }
    else{
        if(tree->left==NULL){
            return tree;
        }
        else{
            return min_BTree(tree->left);
        }       
    }
}
//判断两颗树是否相等（没有判断左右互换相等）
int compare_tree(PTree tree1, PTree tree2){
    if(tree1==NULL&&tree2==NULL){
        return 1; 
    }
    if((tree1==NULL)!=(tree2==NULL)){
        return 0;
    }
    if(tree1->data!=tree2->data){
        return 0;
    }
    return compare_tree(tree1->left,tree2->left)&&compare_tree(tree1->right,treee2->right)
}
int main(){
    PTree pt =create(0);   
    createBiTree(&pt,5);
    createBiTree(&pt,6);
    createBiTree(&pt,7);
    createBiTree(&pt,4);  
    //pre_read_tree(pt); //前序打印
    //mid_read_tree(pt); //中序打印
    //rear_read_tree(pt); //后序打印
    //pt = find_node(pt,4);
    pt = clean_tree(pt);
    pre_read_tree(pt); //前序打印
}

霍夫曼树

霍夫曼树，也称为最佳二叉树，是加权路径长度最短的二叉树. 所谓的树的加权路径长度是树中所有叶子节点的权重乘以其到根节点的路径长度.

霍夫曼树的构建过程:

首先按从小到大的顺序排列，然后每次将第一个中的最小两个作为树，依此类推. 参考示例:

霍夫曼编码

霍夫曼编码: 霍夫曼树是解决数据压缩或传输优化问题的最佳树.

对于一个字符串，里面每个字符的概率是不同的，这等效于不同的权重，这可以通过霍夫曼树来解决. 具体方法是: 根据权重（发生概率）的不同，按照霍夫曼树排列所有字符，然后将霍夫曼树上的所有左分支更改为0数据结构二叉排序树，将所有右分支更改为1 （即权重更改为0和1），然后在从根节点到叶子的路径上使用0和1对叶子上的字符进行编码.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-280550-1.html