数据结构之树操作
本文打出了大部分树的操作 和部分知识点 还有自己编写的哈夫曼树中的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 1m=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 100typedef 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进行编码 /*从根到叶子进行编码 */ 本篇文章主要是树的操作