[树] 树、二叉树、二叉排序树、平衡二叉树、哈夫曼树（C语言代码合集）

妖狐艹你老母 2023-06-19 13:27 16阅读 0赞

> 本文所有函数，查看直接搜索函数名  
> 所有算法都是采用简答容易理解的方法，适合应试

/* 创建 */
    int CreateBiTree_PreOrder(BiTree &T); //用带有NULL的先序序列创建二叉树
    /* 二叉树的遍历 */
    void PreOrder(BiTree ); void InOrder(BiTree ); void PostOrder(BiTree ); void LevelOrder(BiTree );
    void PreOrder_norec(BiTree ); void InOrder_norec(BiTree ); void PostOrder_norec(BiTree );
    /* 基础操作 */
    int GetBiTreeHeigh(BiTree );	//高度
    int GetBiTreeWidth(BiTree );	//宽度
    int NodeCnt(BiTree );			//结点个数
    int LeafNodeCnt(BiTree );		//叶子结点个数
    int OneBranchNodeCnt(BiTree );  //单分支结点的个数
    int TwoBranchNodeCnt(BiTree );	//双分支结点的个数
    int ChildsCnt(BiTree );			//各节点的子孙个数
    /* 二叉树的判断 */
    int BiTreeIsComplete(BiTree root);	//判断二叉树是否是完全二叉树
    int BiTreeIsFull(BiTree root);		//判断二叉树是否为满二叉树
    int BiTreeIsSort(BiTree root);		//判断二叉树是不是二叉排序树
    int BiTreeIsBalance(BiTree );		//判断二叉树是不是平衡二叉树

##### 树 #####

// 树的高度

##### 二叉树 #####

#include<stdio.h>
    #include<stdlib.h>
    #define INF 0x7F7F7F7F //最大值
    #define MAXSIZE 50
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)>(b)?(b):(a))
    
    	/* 数组结构 */
    typedef struct BiTNode{ 
    	char data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree; //孩子链表表示法
    
    
    /* 创建 */
    int CreateBiTree_PreOrder(BiTree &T); //用带有NULL的先序序列创建二叉树
    /* 二叉树的遍历 */
    void PreOrder(BiTree ); void InOrder(BiTree ); void PostOrder(BiTree ); void LevelOrder(BiTree );
    void PreOrder_norec(BiTree ); void InOrder_norec(BiTree ); void PostOrder_norec(BiTree );
    /* 基础操作 */
    int GetBiTreeHeigh(BiTree );	//高度
    int GetBiTreeWidth(BiTree );	//宽度
    int NodeCnt(BiTree );			//结点个数
    int LeafNodeCnt(BiTree );		//叶子结点个数
    int OneBranchNodeCnt(BiTree );  //单分支结点的个数
    int TwoBranchNodeCnt(BiTree );	//双分支结点的个数
    int ChildsCnt(BiTree );			//各节点的子孙个数
    /* 二叉树的判断 */
    int BiTreeIsComplete(BiTree root);	//判断二叉树是否是完全二叉树
    int BiTreeIsFull(BiTree root);		//判断二叉树是否为满二叉树
    int BiTreeIsSort(BiTree root);		//判断二叉树是不是二叉排序树
    int BiTreeIsBalance(BiTree );		//判断二叉树是不是平衡二叉树
    
    int main() { 
    
    	BiTree T;
    	CreateBiTree_PreOrder(T); //输入示例：ABC##DE#G##F###
    	// 遍历测试
    	printf("\n先序遍历_递归："); PreOrder(T);
    	printf("\n中序遍历_递归："); InOrder(T); 
    	printf("\n后序遍历_递归："); PostOrder(T); 
    	printf("\n层次遍历："); LevelOrder(T);
    	printf("\n先序遍历_非递归："); PreOrder_norec(T);
    	printf("\n中序遍历_非递归："); InOrder_norec(T);
    	printf("\n后序遍历_非递归："); PostOrder_norec(T);
    
    	// 基本操作测试
    	printf("\n\n高度：%d", GetBiTreeHeigh(T) );
    	printf("\n宽度：%d", GetBiTreeWidth(T) );
    	printf("\n结点个数：%d", NodeCnt(T) );
    	printf("\n叶子结点个数：%d", LeafNodeCnt(T) );
    	printf("\n单分支结点个数：%d", OneBranchNodeCnt(T) );
    	printf("\n双分支结点个数：%d", TwoBranchNodeCnt(T) );
    	printf("\n各节点的子孙个数（输出形式：结点-子孙个数）："); ChildsCnt(T);
    	
    	return 0;
    }
    
    	/* 二叉树的构造 */
    int CreateBiTree_PreOrder(BiTree &T) {  //用包含NULL的先序序列构造二叉树
    	char ch;
    	scanf("%c", &ch); //输入示例：ABC##DE#G##F###
    	if (ch=='#') T=NULL; //空指针
    	else {  //结点
    		T = (BiTNode *)malloc(sizeof(BiTNode));
    		T->data = ch;
    		CreateBiTree_PreOrder(T->lchild); //递归创建左子树
    		CreateBiTree_PreOrder(T->rchild); //递归创建右子树
    	}
    	return 1; //创建成功
    }
    
    //由完全二叉树（存储在数组中）构造
    
    //前序、中序序列构造二叉树
    
    //后序、中序序列构造二叉树
    
    //由树转二叉树
    
    
    
    
    	/* 二叉树的遍历 */
    void PreOrder(BiTree T) {  // 先序遍历
    	if (T==NULL) return ;
    	printf("%c", T->data);
    	PreOrder(T->lchild);
    	PreOrder(T->rchild);
    }
    void InOrder(BiTree T) {  //中序遍历
    	if (T==NULL) return ;
    	InOrder(T->lchild);
    	printf("%c", T->data);
    	InOrder(T->rchild);
    }
    void PostOrder(BiTree T) {  //后序遍历
    	if (T==NULL) return ;
    	PostOrder(T->lchild);
    	PostOrder(T->rchild);
    	printf("%c", T->data);
    }
    void LevelOrder(BiTree root) {  //层次遍历
    	BiTNode *que[MAXSIZE]; int front,rear; //队列
    	BiTNode *p;
    	front=rear=0;
    	if (root==NULL) return ; //空树，此句容易少写
    	que[rear]=root; rear=(rear+1)%MAXSIZE; //根结点入队列
    	while (front!=rear) {  //不为空
    		p=que[front]; front=(front+1)%MAXSIZE; //出队列
    		printf("%c", p->data); //访问
    		if(p->lchild!=NULL) { 
    			que[rear]=p->lchild; //左子树入队列
    			rear=(rear+1)%MAXSIZE;
    		}
    		if (p->rchild!=NULL) { 
    			que[rear]=p->rchild; //右子树入队列
    			rear=(rear+1)%MAXSIZE;
    		}
    	}
    }
    void PreOrder_norec(BiTree root) {  //先序非递归
    	// 思路：模拟遍历时指针p的移动
    	// 操作：1. 从根结点开始一直往左走，每经过一个结点先访问，然后放入栈；
    	// 2. 往左走不动了，结点出栈，然后往右走一步，继续上一步，直到往右走不动了
    	BiTNode *stack[MAXSIZE]; int top=-1; //栈
    	BiTNode *p = root; //指针
    	if (root==NULL) return ; 
    	do { 
    		while (p!=NULL) {  //一直往左走
    			printf("%c", p->data); //访问
    			stack[++top]=p; //入栈
    			p=p->lchild;	//往左走
    		}
    		// 往左走不动了
    		if (top!=-1) { 
    			p=stack[top--]; //出栈
    			p=p->rchild; //往右走一步
    		}	  
    	} while (top!=-1 || p!=NULL);
    }
    void InOrder_norec(BiTree root) {  //中序非递归
    	// 思路：模拟遍历时指针p的移动
    	// 操作：从根结点开始一直往左走，每经过一个结点不访问，放入栈；
    	// 往左走不动了，结点出栈，然后访问该结点，并往右走一步，继续上一步，直到往右走不动的时候
    	BiTNode *stack[MAXSIZE]; int top=-1;
    	BiTNode *p = root;
    	do { 
    		while (p!=NULL) {  //一直往左走
    			stack[++top]=p;
    			p=p->lchild;
    		}
    		// 往左走不动了
    		if (top!=-1) { 
    			p=stack[top--]; //出栈
    			printf("%c", p->data); //访问
    			p=p->rchild; //往右走一步
    		}
    	} while (top!=-1 || p!=NULL);
    }
    void PostOrder_norec(BiTree root) {  //后序非递归
    	/*PreOrder_norec中利用的思想是模拟遍历途中指针p的移动，但此方法有一个缺点，无法实现后序遍历 另一种思想：根据访问次序入栈并输出 【先序遍历的操作步骤】访问根，然后把右、左入栈（先入栈后输出，所以将右子树入栈） 【后序遍历】那么次方法下后序遍历应该怎么做？ 1. 后序序列：左 右 根 -> 逆后序序列：根 右 左 2. 想到先序序列：根 左 右。故后序序列可效仿先序序列非递归的方法 操作步骤：根结点入栈；然后出栈，将左右子树加入栈中；直到栈空为止。由此得到逆后序序列；然后将逆后序序列倒过来输出 */
    	BiTNode *stack[MAXSIZE]; int top=-1; //栈
    	BiTNode *inPostOrder[MAXSIZE]; int top2=-1; //第二个栈：用于存储逆后序序列
    	BiTNode *p;
    
    	if (root==NULL) return ; //虽然在这里，这句话可以省略。但还是要养成判断临界条件的好习惯
    	stack[++top] = root; //根结点入栈
    	while (top!=-1) { 
    		p=stack[top--]; //出栈
    		inPostOrder[++top2]=p; //访问
    		if (p->lchild!=NULL) stack[++top]=p->lchild; //右子树入栈
    		if (p->rchild!=NULL) stack[++top]=p->rchild; //左子树入栈
    	}
    	while (top2!=-1) {  //倒序输出逆后序序列
    		p = inPostOrder[top2--];
    		printf("%c", p->data); //正式访问
    	}
    }
    // 以上只给出二叉树遍历的一种方法，其他方法见：https://geodoer.blog.csdn.net/article/details/82889711
    
    	/* 二叉树的基础操作 */
    int GetBiTreeHeigh(BiTree T) {  //二叉树的高度
    	int a,b;
    	if (T==NULL) return 0;
    	a = GetBiTreeHeigh(T->lchild);
    	b = GetBiTreeHeigh(T->rchild);
    	return max(a,b)+1;
    }
    int GetBiTreeWidth(BiTree root) { //二叉树的宽度
    	// 思路：层次遍历取最大的一层的节点数
    	BiTNode *que[MAXSIZE]; int front,rear;
    	int maxNumLevel=0; //数据最多的一层
    	BiTNode *p; int cnt, lastLevelCnt;
    	
    	if (root==NULL) return 0;
    	front=rear=0; //队列初始化
    	que[rear]=root; rear=(rear+1)%MAXSIZE; //根结点入队列
    	lastLevelCnt=1; //这一层共有一个结点
    	cnt=0; //计算下一层有几个结点
    	while (front!=rear) { 
    		p=que[front]; front=(front+1)%MAXSIZE; //出队列
    		lastLevelCnt--; //上一层已有一个出栈
    		if (p->lchild!=NULL) { 
    			que[rear]=p->lchild; rear=(rear+1)%MAXSIZE;
    			cnt++; //新的一层又有一个
    		}
    		if (p->rchild!=NULL) { 
    			que[rear]=p->rchild; rear=(front+1)%MAXSIZE;
    			cnt++; //新的一层又有一个
    		}
    
    		if (lastLevelCnt==0) {  //如果上一层的已经全部出完，将要进入下一层的遍历
    			lastLevelCnt=cnt; //上一层的个数=这一层的个数
    			if (cnt>maxNumLevel) maxNumLevel=cnt; //这一层个数与最大值比较
    			cnt=0; //归零，进入下一层
    		}
    	}
    
    	return maxNumLevel;
    }
    int NodeCnt(BiTree T) {  //计算结点总数
    	if (T==NULL) return 0;
    	return 1+NodeCnt(T->lchild)+NodeCnt(T->rchild);
    }
    int LeafNodeCnt(BiTree T) {  //计算叶子结点的总数
    	if (T==NULL) return 0;
    	if (T->lchild!=NULL && T->rchild!=NULL) return 1;
    	return LeafNodeCnt(T->lchild)+LeafNodeCnt(T->rchild);
    }
    int OneBranchNodeCnt(BiTree T) {  //单分支结点数
    	int cnt=0;
    	if (T==NULL) return 0;
    	if (T->lchild && T->rchild==NULL) cnt++;
    	if (T->lchild==NULL && T->rchild) cnt++;
    	return cnt+OneBranchNodeCnt(T->lchild)+OneBranchNodeCnt(T->rchild);
    }
    int TwoBranchNodeCnt(BiTree T) { //双分支结点数
    	int cnt=0;
    	if (T==NULL) return 0;
    	if (T->lchild && T->rchild) cnt++;
    	return cnt+TwoBranchNodeCnt(T->lchild)+TwoBranchNodeCnt(T->rchild);
    }
    int ChildsCnt(BiTree T) {  //各节点的子孙个数
    	// 思路：结点总数+后序遍历
    	int cnt=0;
    	if (T==NULL) return 0;
    	if (T->lchild!=NULL) cnt+=1+ChildsCnt(T->lchild);
    	if (T->rchild!=NULL) cnt+=1+ChildsCnt(T->rchild);
    	printf("%c-%d\t", T->data, cnt);
    	return cnt;
    }
    
    	/* 二叉树的相关判断 */
    int BiTreeIsComplete(BiTree root) { // 判断二叉树是否是完全二叉树
    	// 思路：完全二叉树的层次遍历应没有NULL 或者说 在完全二叉树包括空指针的层次遍历中NULL在最后面
    	// 操作：对完全二叉树进行层次遍历（包括空指针）。若遍历途中出现空指针，则标记为flag=1。在遍历途中如果是非空结点，而且flag=0，则不是二叉树
    	BiTNode *que[MAXSIZE]; int front,rear; //定义一个队列
    	BiTree p;
    	int flag=0; //标识前面是否出现过空指针
    	
    	if (root==NULL) return 1; //临界条件不要丢：完全二叉树也有空树
    	
    	front=rear=0;
    	que[rear]=root; rear=(rear+1)%MAXSIZE; //根指针入队列
    	while (front!=rear) { 
    		p=que[front]; front=(front+1)%MAXSIZE; //出队列
    		if (p==NULL) {  //此指针是空指针
    			flag=1; //标记出现过空指针
    		} else {  //此指针是非空结点
    			if (flag) return 0; //之前出现过空指针，不是完全二叉树
    			// 不判断p的孩子是否为空指针，直接队列
    			que[rear]=p->lchild; rear=(rear+1)%MAXSIZE; 
    			que[rear]=p->rchild; rear=(rear+1)%MAXSIZE;
    		}
    	}
    
    	return 1;
    }
    int BiTreeIsFull(BiTree root) { // 判断二叉树是否是满二叉树
    	// 思路：首先它是完全二叉树，并且结点总数sum=2^n-1
    	// 操作：在判断完全二叉树的途中记录结点个数，然后判断sum=2^n-1是否满足
    	/* 补充知识：判断数num是否是2^k --> !( num&(num-1) ) [理解] 若num是2的k次方，那么它二进制只有一位是1-->举例0100。那num-1=0011。0100&0011=0000 */
    	BiTNode *que[MAXSIZE]; int front,rear;
    	BiTree p;
    	int flag=0; //标记之前是否出现了空指针
    	int sum=0; //结点总数
    
    	if (root==NULL) return 1; //满二叉树也有空树
    
    	front=rear=0;
    	que[rear]=root; rear=(rear+1)%MAXSIZE;
    	++sum;
    	while (front!=rear) { 
    		p=que[front]; front=(front+1)%MAXSIZE;
    		if (p==NULL) flag=1; //出现了空指针
    		else { 
    			if (flag) return 0;
    			++sum;
    			que[rear]=p->lchild; rear=(rear+1)%MAXSIZE;
    			que[rear]=p->rchild; rear=(rear+1)%MAXSIZE;
    		}
    	}
    
    	// 检查sum=2^n-1 --> sum+1是2的n次方
    	sum = sum+1;
    	if ( !( sum&(sum-1) ) ) return 1; //检查数num是否为2的k次方
    	else return 0;
    }
    int BiTreeIsSort(BiTree T) { // 判断二叉树是不是二叉排序树
    	// 思路：二叉排序树的中序序列是一个从小到大的序列
    	static int pre=0; 
    
    	if (T==NULL) return 1; //二叉排序树也有空树
    
    	if ( BiTreeIsSort(T->lchild)==0 ) return 0; //判断左子树
    	if ( pre > T->data ) return 0; //是否从小的到大排序
    	pre = T->data;
    	if ( BiTreeIsSort(T->rchild)==0 ) return 0; //判断右子树
    
    	return 1; //判断都通过，返回是
    }
    int BiTreeIsBalance(BiTree T, int &flag) {  // 判断二叉树是不是平衡二叉树
    	// 思路：修改计算二叉树高度的函数，并判断平衡二叉树的条件-1<=左子树高度-右子树高度<=-1
    	// flag为返回结果，1为是平衡二叉树，0为不是
    	// 调用：int flag=1; BiTreeIsBlance(T, flag);
    	int rh, lh; //左右子树高度
    
    	if (T==NULL) return 0;
    	lh = BiTreeIsBalance(T->lchild, flag);
    	rh = BiTreeIsBalance(T->rchild, flag);
    	if ( lh-rh<-1 || lh-rh<1 ) flag=0; //不是平衡二叉树
    	return max(lh, rh)+1; //返回T的高度
    }
    
    	/* 哈夫曼树 */
    
    
    	/* 二叉排序树 */
    //构造二叉排序树（由数组A[]构造）
    
    
    	/* 平衡二叉树 */
    //平衡二叉树的构造