二叉树基本功能实现（递归）

目录

一、二叉树的定义

二、二叉树的遍历

一、先序遍历

二、中序遍历

三、后序遍历

四、层序遍历

三、二叉树的其他 *** 作

一、求二叉树节点个数

二、求二叉树叶子节点的个数

三、求二叉树的最大深度

四、完整二叉树源码

---

一、二叉树的定义

顾名思义，二叉树有两个分支，每个节点下分两条路径，分为左子树和右子树。如图：

 

所以二叉树的结构体需要两个指针和一个数据存储。结构为：

typedef char TD;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode*left; //指向左节点的指针
	struct BinaryTreeNode*right; //指向右节点的指针
	TD data; //节点存储的数据
}BTNode;

二、二叉树的遍历

对先、中、后序的遍历可以参考上图。

这涉及深度优先搜索(DFS)，是纵向遍历整个数。

一、先序遍历

void PrevOrder(BTNode*root)
{
	if (root)
	{
        //这里打印数据是为了便于观察理解
		printf("%c ", root->data);//先根，后左，最后右
		PrevOrder(root->left);
		PrevOrder(root->right);
	}
	else
		printf("NULL ");
}

二、中序遍历

void InOrder(BTNode*root)
{
	if (root)
	{
		InOrder(root->left);//先左，后根，最后右
		printf("%c ", root->data);
		InOrder(root->right);
	}
	else
		printf("NULL ");
}

三、后序遍历

void PostOrder(BTNode*root)
{
	if (root)
	{
		PostOrder(root->left);//先左，后右，最后根
		PostOrder(root->right);
		printf("%c ", root->data);
	}
	else
		printf("NULL ");
}

可以看到，用递归很容易写出来。

四、层序遍历

这涉及广度优先搜索（BFS），是按每层从左向右依次遍历每个树节点。

我使用了一个队列来实现。

#include"Queue for Tree.h" //因为c语言库没有这些数据结构，需要自己实现
void LevelOrder(BTNode*root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);//将节点存入队列
	while (!QueueEmpty(&q))
	{
		BTNode*ret = QueueFront(&q);//暂存节点·，便于后续调用
		QueuePop(&q);
		printf("%c ", ret->data);
		if (ret->left)//左右节点不为空，递归调用
			QueuePush(&q, ret->left);
		if (ret->right)
			QueuePush(&q, ret->right);
	}
	printf("\n");
}

 队列源码如下

#pragma once
#include
#include
#include
#include

typedef	BTNode* QUD;

typedef struct QueueNode
{
	struct QueueNode*next;
	QUD data;
}Qnode;
typedef struct Queue
{
	Qnode*head;
	Qnode*tail;
}Queue;
void QueueInit(Queue*p)
{
	assert(p);
	p->head = p->tail = NULL;
}
void QueuePush(Queue*p, QUD n)
{
	assert(p);
	Qnode*node = (Qnode*)malloc(sizeof(Qnode));
	node->next = NULL;
	node->data = n;
	if (p->tail == NULL)
	{
		p->head = p->tail = node;
	}
	else
	{
		p->tail->next = node;
		p->tail = node;
	}
}
void QueuePop(Queue*p)
{
	assert(p&&p->head);
	if (p->head->next == NULL)
	{
		free(p->head);
		p->head = p->tail = NULL;
	}
	else
	{
		Qnode*temp = p->head->next;
		free(p->head);
		p->head = temp;
	}
}
QUD QueueFront(Queue*p)
{
	assert(p&&p->head);
	return p->head->data;
}
QUD QueueBack(Queue*p)
{
	assert(p&&p->head);
	return p->tail->data;
}
void QueueDestory(Queue*p)
{
	assert(p);
	Qnode*cur = p->head;
	while (cur)
	{
		Qnode*temp = cur->next;
		free(cur);
		cur = temp;
	}
	p->head = p->tail = NULL;
}
bool QueueEmpty(Queue*p)
{
	return p->head == NULL;
}
int QueueSize(Queue*p)
{
	assert(p);
	int size = 0;
	Qnode*cur = p->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

二叉树的遍历就到此结束了。

三、二叉树的其他 *** 作 一、求二叉树节点个数

用一个递归就能得出。

int TreeNodeSize(BTNode*root)
{
	return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

二、求二叉树叶子节点的个数

int TreeLeafSize(BTNode*root)
{
	if (!root)//自身为空返回0
		return 0;
	if (!root->left && !root->right)//左右都为空时，为一个叶子节点
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);//递归求解
}

三、求二叉树的最大深度

int TreeMaxDepth(BTNode*root)
{
	if (!root)//为空返回0
		return 0;
	int leftDepth = TreeMaxDepth(root->left);//左子树深度
	int rightDepth = TreeMaxDepth(root->right);//右子树深度
	return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
//哪个递归次数多，哪个值大，即为最大深度
}

四、完整二叉树源码

#pragma once
#include

typedef char TD;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode*left;
	struct BinaryTreeNode*right;
	TD data;
}BTNode;
#include"Queue for Tree.h"
void PrevOrder(BTNode*root)
{
	if (root)
	{
		printf("%c ", root->data);
		PrevOrder(root->left);
		PrevOrder(root->right);
	}
	else
		printf("NULL ");
}

void InOrder(BTNode*root)
{
	if (root)
	{
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
	else
		printf("NULL ");
}

void PostOrder(BTNode*root)
{
	if (root)
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
	else
		printf("NULL ");
}

int TreeNodeSize(BTNode*root)
{
	return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

int TreeLeafSize(BTNode*root)
{
	if (!root)
		return 0;
	if (!root->left && !root->right)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeMaxDepth(BTNode*root)
{
	if (!root)
		return 0;
	int leftDepth = TreeMaxDepth(root->left);
	int rightDepth = TreeMaxDepth(root->right);
	return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
void LevelOrder(BTNode*root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode*ret = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", ret->data);
		if (ret->left)
			QueuePush(&q, ret->left);
		if (ret->right)
			QueuePush(&q, ret->right);
	}
	printf("\n");
}

void TreeDestory(BTNode*root)
{
	if (!root)
		return;
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
	root = NULL;
}

上图的测试用例，这里是手动构建的，便于测试。

#include"BinaryTree.h"
#include
int main()
{
	BTNode*A = (BTNode*)malloc(sizeof(BTNode));
	A->data = 'A';
	A->left = A->right = NULL;

	BTNode*B = (BTNode*)malloc(sizeof(BTNode));
	B->data = 'B';
	B->left = B->right = NULL;

	BTNode*C = (BTNode*)malloc(sizeof(BTNode));
	C->data = 'C';
	C->left = C->right = NULL;

	BTNode*D = (BTNode*)malloc(sizeof(BTNode));
	D->data = 'D';
	D->left = D->right = NULL;

	BTNode*E = (BTNode*)malloc(sizeof(BTNode));
	E->data = 'E';
	E->left = E->right = NULL;

	BTNode*F = (BTNode*)malloc(sizeof(BTNode));
	F->data = 'F';
	F->left = F->right = NULL;

	BTNode*G = (BTNode*)malloc(sizeof(BTNode));
	G->data = 'G';
	G->left = G->right = NULL;

	BTNode*H = (BTNode*)malloc(sizeof(BTNode));
	H->data = 'H';
	H->left = H->right = NULL;

	BTNode*I = (BTNode*)malloc(sizeof(BTNode));
	I->data = 'I';
	I->left = I->right = NULL;

	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	C->left = F;
	C->right = G;
	D->left = H;
	D->right = I;

	PrevOrder(A);
	printf("\n");
	InOrder(A);
	printf("\n");
	PostOrder(A);
	printf("\n");
	LevelOrder(A);
	printf("TreeNodeSize:%d\n", TreeNodeSize(A));
	printf("TreeNodeSize:%d\n", TreeNodeSize(B));
	printf("TreeNodeSize:%d\n", TreeNodeSize(C));
	printf("TreeLeafSize:%d\n", TreeLeafSize(A));
	printf("TreeMaxDepth:%d\n", TreeMaxDepth(A));
	TreeDestory(A);
	return 0;
}

好了，以上便是二叉树的基本内容了，掌握这些后继续向更深处学习吧。