数据结构之树 *** 作

     本文打出了大部分树的 *** 作 和部分知识点   还有自己编写的哈夫曼树中的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