遍历二叉树求叶子结点，深度，结点数，以及前序，中序，后序遍历

bcc0729 / 2023-08-16 / 原文

#include <stdio.h>


// 二叉树结构体
typedef struct BT_node
{
	int data;
	struct BT_node* left;
	struct BT_node* right;
}BT_node;


// 先序遍历
void DLR(BT_node* tree)
{
	if(NULL == tree)
		return;
	printf("%d ", tree->data);
	DLR(tree->left);
	DLR(tree->right);

}

// 中序遍历
void LDR(BT_node* tree)
{
	if(NULL == tree)
		return;
	LDR(tree->left);
	printf("%d ", tree->data);
	LDR(tree->right);

}

// 后序遍历
void LRD(BT_node* tree)
{
	if(NULL == tree)
		return;
	LRD(tree->left);
	LRD(tree->right);
	printf("%d ", tree->data);

}

// 叶子结点数
int leaf(BT_node* tree)
{
	if(NULL == tree)
		return 0;
	if(NULL == tree->left && NULL == tree->right)
		return 1;
	int l = leaf(tree->left);
	int r = leaf(tree->right);

	return l+r;
}

// 深度
int high(BT_node* tree)
{
	if(NULL == tree)
		return 0;

	int l = high(tree->left);
	int r = high(tree->right);

	if(l > r)
		return l + 1;
	else
		return r + 1;

}

// 深度
int node_Num(BT_node* tree)
{
	if(NULL == tree)
		return 0;
	static int count = 0;
	count++;
	node_Num(tree->left);
	node_Num(tree->right);
	

	return count;
}

int main(int argc, char const *argv[])
{
	// 结点数据
	BT_node bt[9] = {
		{1, NULL, NULL},
		{2, NULL, NULL},
		{3, NULL, NULL},
		{4, NULL, NULL},
		{5, NULL, NULL},
		{6, NULL, NULL},
		{7, NULL, NULL},
		{8, NULL, NULL},
		{9, NULL, NULL}
	};

	bt[0].left = &bt[1];bt[0].right = &bt[2];
	bt[1].left = &bt[3];bt[1].right = &bt[4];
	bt[2].left = &bt[5];bt[2].right = &bt[6];
	bt[3].left = &bt[7];bt[3].right = &bt[8];

	DLR(bt);
	puts("");
	LDR(bt);
	puts("");
	LRD(bt);
	puts("");

	printf("leaf: %d\n", leaf(bt)); 
	printf("high: %d\n", high(bt)); 
	printf("count: %d\n", node_Num(bt)); 


	return 0;
}