本文打出了大部分树的操作 和部分知识点 还有自己编写的哈夫曼树中的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进行编码 /* 从根到叶子进行编码 */
