C语言树总结

#include 
#include 
 typedef struct BitNode {
	int data;//数据域
	struct BitNode* lchild;//左孩子指针
	struct BitNode* rchild;//右孩子指针
	//struct BitNode* parent;//三叉链表
}BitNode,*BiTree;//二叉树二叉链表链式存储
 /*二叉树的顺序存储按完全二叉树存储*/
 /*1.树的结点数等于所有结点度数之和加1
   2.结点的孩子个数叫做该结点的度
   3.满二叉树 完全二叉树 二叉排序树 平衡二叉树
   4.深度是从上至下高度从下至上
   5.结点数为n的二叉树空链域为n+1*/
 int visit(BiTree A) {
	 return A->data;
 }
 void PreOrder(BiTree T) {
	 if (T!= NULL) {
		 visit(T);
		 PreOrder(T->lchild);
		 PreOrder(T->rchild);
	 }
 }//先序遍历根左右
 void InOrder(BiTree T) {
	 if (T != NULL) {
		 InOrder(T->lchild);
		 visit(T);
		 InOrder(T->rchild);
	 }
 }//中序遍历左根右
 void PostOrder(BiTree T) {
	 if (T != NULL) {
		 PostOrder(T->lchild);
		 PostOrder(T->rchild);
		 visit(T);
	 }
 }//后序遍历左右根
 //时间复杂度O(n)
 void LevelOrder(BiTree T) {
	 //InitQueue(Q);初始化辅助队列
	 BiTree p;//队头元素
	// InQueue(Q, T);根节点入队
	/* while (!IsEmpty(Q)) {
		 OutQueue(Q, p);
		 visit(p);
		 if (p->lchild != NULL)
			 InQueue(Q, p->lchild);
		 if (p->lchild != NULL)
			 InQueue(Q, p->lchild);
	 }*/
 }//层次遍历
 /*根据先序序列和中序序列可唯一确定一颗二叉树
   根据后序序列和中序序列可唯一确定一颗二叉树 
   根据层次序列和中序序列可唯一确定一颗二叉树*/
 typedef struct ThreadNode {
	 int data;//数据域
	 struct ThreadNode* lchild, * rchild;//左右孩子指针
	 struct ThreadNode* ltag, * rtag;//左右线索标志ltag为0 lchild指左孩子为1指前驱
 }ThreadNode,*ThreadTree;//线索二叉树
 void InThread(ThreadTree p, ThreadTree pre) {//pre为P的前驱pre为刚访问过的结点p为正在访问的结点
	 if (p != NULL) {
		 InThread(p->lchild, pre);
		 //visit(p);
		 if (p->lchild == NULL) {
			 p->lchild = pre;
			 p->ltag = 1;
		 }
		 if (pre != NULL && pre->rchild == NULL) {
			 pre->rchild = p;
			 pre->rtag = 1;
		 }
		 pre = p;
		 InThread(p->rchild, pre);
	 }
 }//中序遍历的二叉树线索化
 void CreatInThread(ThreadTree T) {
	 ThreadTree pre = NULL;
	 if (T != NULL) {
		 InThread(T, pre);
		 pre->lchild = NULL;
		 pre->ltag = 1;
	 }
 }//建立中序线索二叉树
 ThreadNode* Firstnode(ThreadNode* p){
	 while (p->ltag == 0)
		 p = p->lchild;
	 return p;
 }//找以p为根结点的树的中序序列中第一个结点
 ThreadNode* Nextnode(ThreadNode* p) {
	 if (p->ltag == 1) {
		 return p->lchild;
	 }
	 else {
		 return Firstnode(p->lchild);
	 }
 }//求p在中序序列中的后继
 void Inorder(ThreadNode* T) {
	 for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p)) {
		 visit(p);
	 }
 }//中序遍历
#define Max_Tree_Size 100
 typedef struct PTNode {
	 int data;//数据域
	 int parent;//双亲位置域
 }PTNode;
 typedef struct PTree {
	 PTNode nodes[Max_Tree_Size];
	 int node;//结点数
 }PTree;//树的双亲表示法根结点位置为0 parent置-1
 typedef struct CBNode {
	 int data;//数据域
	 struct CBNodde* firstchild, * rightbrother;//结点第一个孩子指针，右兄弟指针
 }CBNode,*CBTree;//孩子兄弟表示法用于树森林转化为二叉树
 /*树的遍历先根遍历，后根遍历，层次遍历
   先根遍历等同于该对应二叉树的先序遍历后根遍历等同于该对应二叉树的中序遍历
   树的遍历先序遍历，中序遍历（也可叫后根遍历
   先序遍历等同于该对应二叉树的先序遍历中序遍历等同于该对应二叉树的中序遍历）*/
 typedef struct BSTNode {
	 int key;//数据域
	 struct BSTNode* lchild, * rchild;//左孩子指针，右孩子指针
 }BSTNode,*BSTree;//排序二叉树
 BSTNode* BST_Search(BSTree T, int key) {
	 while (T != NULL && T->key != key) {
		 if (T->key > key) {
			 T = T->lchild;
		 }
		 else {
			 T = T->rchild;
		 }
	 }
	 return T;
 }//非递归查找 *** 作空间复杂度O（1）
 BSTNode* BST_Search(BSTree T, int key) {
	 if (T == NULL) {
		 return NULL;
	 }
	 else if (T->key == key)
		 return T;
	 else if (T->key > key)
		 return BST_Search(T->lchild, key);
	 else
		 return BST_Search(T->rchild, key);
 }//递归查找 *** 作空间复杂度O(h)
 bool BST_Insert(BSTree T, int k) {
	 if (T->key == k)
		 return false;
	 else if (T->key > k) {
		 return BST_Insert(T->lchild, k);
	 }
	 else if (T->key < k) {
		 return BST_Insert(T->rchild, k);
	 }
	 else {
		 T = (BSTNode*)malloc(sizeof(BSTNode));
		 T->key = k;
		 T->lchild = T->rchild = NULL;
		 return true;
	 }
 }//二叉排序树插入 *** 作
 void Creat_BST(BSTree T, int str[], int n) {//T为根结点 str为要插入二叉树中的数值数组 n为数据个数
	 T = NULL;
	 int i = 0;
	 while (i < n) {
		 BST_Insert(T, str[i]);
		 i++;
	 }
 }//二叉排序树的构造将二叉排序树中序遍历可得到递增序列
 /*二叉排序树的删除操作
   1.要删除的结点为叶子结点直接删除
   2.若要删除的结点只有左子树或右子树删除结点并让删除结点的子树做删除结点父节点的子树（删除结点的子树根结点代替删除结点位置）
   3.若要删除的结点有左子树和右子树
        方法1.让删除结点的中序后继结点代替删除结点位置然后对该后继结点做删除操作（转化为第一种或第二种情况）
		方法2.让删除结点的中序前驱结点代替删除结点位置然后对该前驱结点做删除操作（转化为第一种或第二种情况）*/
 /*查找长度:在查找操作中需要对比关键字的次数 反映查找操作的时间复杂度最好情况O（log2n)最坏情况O（n)越宽越好即平衡二叉树
查找成功平均查找长度ASL
例ASL=（1*1需要对比一次的数据有一个+2*2需要对比两次的数据有两个+3*4需要对比三次的数据有四个+4*1需要对比四次的数据有一个）/（1+2+4+1）一共有8个数据
查找失败的平均查找长度ASL
例ASL=（3*7需要对比三次数据的空链域有7个+4*1需要对比四次数据的空链域有1个）/（7+1）一共8个空链域*/
/*平衡二叉树 树上任一结点的左右子树高度差不超过1
  平衡二叉树的插入操作从插入点往回找到第一个不平衡结点以该结点为根的子树为最小不平衡子树调整最小不平衡子树即可
  1.LL 在最小不平衡子树A的左孩子B的左子树中插入   B右旋
      A->lchild=B->rchild;
	  B->rchild=A;
	  parentA->lchild或rchild=B;
  2.RR 在最小不平衡子树A的右孩子B的右子树中插入   B左旋
      A->rchild=B->lchild;
	  B->lchild=A;
	  parentA->lchild或rchild=B;
  3.LR 在最小不平衡子树A的左孩子B的右子树中插入   B的右孩子C先左旋后右旋
  4.RL 在最小不平衡子树A的右孩子B的左子树中插入   B的左孩子C先右旋后左旋
  平衡二叉树平均查找长度为O（log2n)*/
 /*结点的权：表示结点的重要程度等
   结点的带权路径长度 例3*3（从根结点到该结点的长度为3，该结点的权重为3）
   树的带权路径长度：树中所有叶子结点的带权路径长度之和WPL
   在含n个结点的二叉树中WPL最小的二叉树叫哈夫曼树（最优二叉树）
   哈夫曼树的构造
   1.将n个结点作为n棵树构成森林
   2.在森林中选取两个根结点权重最小的树构造一颗新的二叉树，新二叉树根结点权重为这两颗树的根结点权重和（左右子树的顺序任意）
   3.将新树加入森林刚选中的两棵树删除
   4.重复 *** 作直到森林中只有一颗树
   n个有权值的结点构造的哈夫曼树总结点为2n+1有权值的结点为叶子结点
   哈夫曼树不唯一
   哈夫曼树不存在度为1的结点
   权重越小的结点路径长度越大
   哈夫曼编码：先构造哈夫曼树将左孩子定义为0右孩子定义为1（自己定义相反也可即左1右0）
   例A的哈夫曼编码为10即A在哈夫曼树中为以根结点的右孩子为根结点的这颗子树的左孩子
   哈夫曼编码为可变长度编码（即允许对不同字符用不等长的二进制来表示）前缀编码（没有一个编码是另外编码的前缀）*/