数据结构二叉树的常规算法（C语言）

1. 求二叉树叶子结点个数。
2. 求二叉树的宽度。
3. 求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
4. 输出二叉树中从每个叶子结点到根结点的路径。

目录

//树的结构定义

//求叶子结点个数

//求树的宽度

//求树的深度

//求最长路径

//求叶子节点到根节点的路径

//树的结构定义

//二叉树：
typedef struct BTree {
	elemtype data;
	struct BTree* left;
	struct BTree* right;
}*BTree

---

//求叶子结点个数

思路：在遍历的基础上加一个判断语句和一个计数器，判断该节点是不是叶子节点，是的话计数器就加1.

//求叶子结点数
//前序遍历的方式
int count = 0;	//计数器
void GetNum(BTree root) {
	if (root == NULL)
		return;
	if (root->left == NULL && root->right == NULL) {//叶子结点
		++count;
		return;
	}
	GetNum(root->left);
	GetNum(root->right);
}

---

//求树的宽度

思路：用层次遍历的方式，比较每一层的结点数，最大的就是整颗树的宽度。先定义一个新的结构体，用来描述每一个结点所在的层次数，再定义一个队列，给所有的结点都记录上自己的层数，最后比较。

//用一个新结构体记录每一个结点所在的层数
typedef struct Width {
	BTree p;	//树的结点
	int num;	//该节点层数
}Width;
//求树的宽度
int GetWidth(BTree root) {
	BTree p = root;
	Width Queue[MAXSIZE];	//建一个队列
	int front = 0;			//队首指针
	int rear = 0;			//队尾指针
	int num = 1;			//初始层数
	BTree q = NULL;			//辅助结点
	if (p != NULL) {
		Queue[rear].p = p;						//结点入队
		Queue[rear++].num = num;				//该结点所在层数
		//先确定每一个结点所在的层数
		while (rear != front) {					//队不为空
			q = Queue[front].p;					//出队
			num = Queue[front++].num;			//获得当前结点的所在层数
			if (q->left) {						//左儿子存在就把左儿子入队
				Queue[rear].p = q->left;		//入队
				Queue[rear++].num = num + 1;	//所在层次要加1
			}
			if (q->right) {
				Queue[rear].p = q->right;
				Queue[rear++].num = num + 1;
			}
		}
		int i = 0;								//i作队列指针
		int max = 0;							//宽度
		num = 1;								//重置层次数
		while (i < rear) {		
			int count = 0;						//计数器，每层节点数
			while (i < rear && Queue[i].num == num) {		//统计同一层上结点数
				++count;
				++i;
			}
			num++;								//层次加1
			if (max < count)
				max = count;
		}
		return max;
	}
	return 0;
}

---

//求树的深度

思路：采用递归的方法，分别算出左子树和右子树的深度，然后比较两边深度大小，大的作为整颗树的深度。

//求树的深度
//递归方法
int Depth(BTree root) {
	if (root == NULL)
		return 0;
	int ldpeth = Depth(root->left) + 1;	//左子树深度
	int rdpeth = Depth(root->right) + 1;//右子树深度
	return ldpeth > rdpeth ? ldpeth : rdpeth;	//返回最深的子树的深度
}

---

//求最长路径

思路：还是用递归，中间通过判断两边的深度来决定递归的子树。

//求最长路径
void Long(BTree root) {
	if (root == NULL)
		return;
	printf("%c ", root->data);
	if (Depth(root->left) > Depth(root->right))	//判断哪边的深度最深
		Long(root->left);
	else
		Long(root->right);
}

---

//求叶子节点到根节点的路径

思路：用辅助栈来操作，将叶子结点前的每一个结点值存入栈中，如果遇到叶子结点，就打印栈中的结点值，这就是根结点到该叶子结点的路径。

//叶子到根的路径
//辅助栈：
typedef struct Stack {
	int top;//栈顶指针
	elemtype data[MAXSIZE];
}*Stack;
Stack stack;
//栈的初始化：
void init() {
	stack = (Stack)malloc(sizeof(struct Stack));
	stack->top = -1;
}
//压栈操作
void Push(elemtype ch) {
	stack->data[++stack->top] = ch;
}
//出栈操作
void Pop() {
	stack->top--;
}
//打印栈
void PrintStack() {
	printf("%c", stack->data[0]);
	for (int i = 1; i <= stack->top; i++) {
		printf("-->%c", stack->data[i]);
	}
	printf("n");
}
//求路径
void Path(BTree root) {
	if (root) {
		Push(root->data);	//先将结点值压栈
		if (!root->left && !root->right) {	//如果这个结点是叶子就打印栈里的内容
			PrintStack();
		}
		else {								//不是的话就递归左子树和右子树
			Path(root->left);
			Path(root->right);
		}
		Pop();								//出栈，改变叶子结点，改变路径的终点
	}
}

---

//加主函数的完整测试源码

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#define elemtype char
#define MAXSIZE 15

//二叉树：
typedef struct BTree {
	elemtype data;
	struct BTree* left;
	struct BTree* right;
}*BTree;

void menu() {
	printf("================n");
	printf("1、求叶子结点数n");
	printf("2、求二叉树宽度n");
	printf("3、最长路径长度n");
	printf("4、叶子到根路径n");
	printf("5、二叉树的深度n");
	printf("================n");
}
//队列初始化树
BTree InitTree(BTree root) {
	BTree Queue[MAXSIZE + 1];	//创建队，+1防止溢出
	int front = 1;				//队首指针,从1开始方便后面的左右儿子判断
	int rear = 0;				//队尾指针。从0开始方便后面计算
	BTree new;					//新节点
	elemtype ch;				//结点值
	while ((ch = getchar()) != 'n') {
		new = (BTree)malloc(sizeof(struct BTree));
		new->data = ch;
		new->left = new->right = NULL;
		Queue[++rear] = new;	//入队
		if (root == NULL)
			root = new;
		if (Queue[rear]->data == '#')
			Queue[rear] = NULL;
		if (rear == front * 2)	//判断是否是root的左儿子
			Queue[front]->left = Queue[rear];
		if (rear == front * 2 + 1) {	//判断是否是root的右儿子
			Queue[front]->right = Queue[rear];
			front++;			//如果是右儿子那代表着这个结点已经操作完了，就将front加1(出队)
		}
	}
	return root;
}
//求叶子结点数
//前序遍历的方式
int count = 0;	//计数器
void GetNum(BTree root) {
	if (root == NULL)
		return;
	if (root->left == NULL && root->right == NULL) {
		++count;
		return;
	}
	GetNum(root->left);
	GetNum(root->right);
}
//求树的宽度
//用一个结构体记录每一个结点所在的层数
typedef struct Width {
	BTree p;	//树的结点
	int num;	//该节点层数
}Width;
int GetWidth(BTree root) {
	BTree p = root;
	Width Queue[MAXSIZE];	//建一个队列
	int front = 0;			//队首指针
	int rear = 0;			//队尾指针
	int num = 1;			//初始层数
	BTree q = NULL;			//辅助结点
	if (p != NULL) {
		Queue[rear].p = p;						//结点入队
		Queue[rear++].num = num;				//该结点所在层数
		//先确定每一个结点所在的层数
		while (rear != front) {					//队不为空
			q = Queue[front].p;					//出队
			num = Queue[front++].num;			//获得当前结点的所在层数
			if (q->left) {						//左儿子存在就把左儿子入队
				Queue[rear].p = q->left;		//入队
				Queue[rear++].num = num + 1;	//所在层次要加1
			}
			if (q->right) {
				Queue[rear].p = q->right;
				Queue[rear++].num = num + 1;
			}
		}
		int i = 0;								//i作队列指针
		int max = 0;							//宽度
		num = 1;								//重置层次数
		while (i < rear) {		
			int count = 0;						//计数器，每层节点数
			while (i < rear && Queue[i].num == num) {		//统计同一层上结点数
				++count;
				++i;
			}
			num++;								//层次加1
			if (max < count)
				max = count;
		}
		return max;
	}
	return 0;
}
//求树的深度
//递归方法
int Depth(BTree root) {
	if (root == NULL)
		return 0;
	int ldpeth = Depth(root->left) + 1;	//左子树深度
	int rdpeth = Depth(root->right) + 1;//右子树深度
	return ldpeth > rdpeth ? ldpeth : rdpeth;	//返回最深的子树的深度
}
//求最长路径
void Long(BTree root) {
	if (root == NULL)
		return;
	printf("%c ", root->data);
	if (Depth(root->left) > Depth(root->right))	//判断哪边的深度最深
		Long(root->left);
	else
		Long(root->right);
}
//叶子到根的路径
//辅助栈：
typedef struct Stack {
	int top;//栈顶指针
	elemtype data[MAXSIZE];
}*Stack;
Stack stack;
//栈的初始化：
void init() {
	stack = (Stack)malloc(sizeof(struct Stack));
	stack->top = -1;
}
//压栈操作
void Push(elemtype ch) {
	stack->data[++stack->top] = ch;
}
//出栈操作
void Pop() {
	stack->top--;
}
//打印栈
void PrintStack() {
	printf("%c", stack->data[0]);
	for (int i = 1; i <= stack->top; i++) {
		printf("-->%c", stack->data[i]);
	}
	printf("n");
}
//求路径
void Path(BTree root) {
	if (root) {
		Push(root->data);	//先将结点值压栈
		if (!root->left && !root->right) {	//如果这个结点是叶子就打印栈里的内容
			PrintStack();
		}
		else {								//不是的话就递归左子树和右子树
			Path(root->left);
			Path(root->right);
		}
		Pop();								//出栈，改变叶子结点，改变路径的终点
	}
}
int main(){
	init();
	int chose = 0;
	BTree root=NULL;
	printf("用对列初始化，‘#’代表虚结点：n");
	root=InitTree(root);		//初始化树
	while (1) {
		menu();
		scanf("%d", &chose);
		switch (chose) {
		case 1: //叶子节点数目
			GetNum(root);
			printf("叶子结点数是：%dn",count);
			count = 0;
			break;
		case 2://树的最大宽度
			printf("宽度是%dn", GetWidth(root));
			break;
		case 3://树的最长路径
			Long(root);
			printf("n");
			break;
		case 4://树的所有路径
			Path(root);
			break;
		case 5://树的深度
			printf("二叉树的深度是：%dn", Depth(root));
			break;
		default:return;
		}
	}
	return 0;
}