二叉树链式结构的遍历

遍历指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

二叉树链式结构的实现–核心模块

开辟空间

BTNode* BuyBinaryTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == node)
	{
		assert(0);
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

二叉树销毁

void BinaryTreeDestory(BTNode** root)
{
	assert(root);
	if (NULL == *root)
	{
		return;
	}
	//按照后序遍历进行销毁
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

二叉树节点个数

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

二叉树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{
	//判断该节点是否为空，返回值为0
	if (root == NULL)
		return 0;
	//判断其左右子树是否为空，都为空则返回1
	if (root->left == NULL && root->right == NULL)
		return 1;
	//递归
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//判断是否为空树或者k的值是否小于等于0
	if (root == NULL || k <= 0)
		return 0;
	//树不空并且k = 1
	if (k == 1)
		return 1;
	//k > 1
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

求树的高度

int BinTreeHeight(BTNode *root)
{
	if (root == NULL)
	{
		return 0;
	}
	//左右子树高度加1 即为树的高度
	int leftHeight = BinTreeHeight(root->left);
	int rightHeight = BinTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

二叉树查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	BTNode *ret = NULL;
	if (NULL == root)
		return NULL;
	if (x == root->data)
		return root;
	if (ret == BinaryTreeFind(root->left, x))
		return ret;
	return  BinaryTreeFind(root->right, x);
}

二叉树前序遍历(递归)

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

二叉树中序遍历

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

二叉树后序遍历

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

层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	if (root == NULL)
	{
		assert(0);
		return;
	}
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* cur =  QueueFront(&q);
		printf("%c ", cur->data);
		if (cur->left)
		{
			QueuePush(&q, cur->left);
		}
		if (cur->right)
		{
			QueuePush(&q, cur->right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
}

判断是否是完全二叉树

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	int flag = 0;
	//空树
	if (root == NULL)
		return 1;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		if (flag)
		{
			//从第一个不饱和的节点后，所有结点都不能有孩子
			if (cur->left || cur->right)
			{
				QueueDestroy(&q);
				return 0;
			}
		}
			//找树中第一个不饱和的结点
		else
		{
			if (cur->left && cur->right)
			{
				QueuePush(&q, cur->left);
				QueuePush(&q, cur->right);
				flag = 1;
			}
			else if (cur->left)
			{
				QueuePush(&q, cur->left);
				flag = 1;
			}
			else if (cur->right)
			{
				QueueDestroy(&q);
				return 0;
			}
			else
			{
				flag = 1;
			}
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return 1;
}

二叉树链式结构的实现–全代码

Queue.h

#pragma once

struct BTNode;//前置声明

typedef struct  BinaryTreeNode* QDataType;

typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

Queue.c

#include"Queue.h"
#include<assert.h>
#include<stdio.h>
#include<malloc.h>

QNode* BuyQueueNode(QDataType data)
{
	QNode* node = (QNode *)malloc(sizeof(QNode));
	if (NULL == node)
	{
		assert(0);
		return NULL;
	}
	node->data = data;
	node->next = NULL;
	return node;
}

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = BuyQueueNode(0);
}

// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	q->rear->next = BuyQueueNode(data);
	q->rear = q->rear->next;
}
// 队头出队列
void QueuePop(Queue* q)
{
	QNode *delNode = NULL;
	if (QueueEmpty(q))
		return;
	delNode = q->front->next;
	q->front->next = delNode->next;

	//如果队列中此时只有一个元素，将该元素删除后还需将rear放在front的位置
	if (delNode->next == NULL)
		q->rear = q->front;
	free(delNode);
}

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(!QueueEmpty(q));
	return q->front->next->data;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(!QueueEmpty(q));
	return q->rear->data;
}

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	int count = 0;
	QNode* cur = q->front->next;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front->next == NULL;
}

// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	q->front = q->rear = NULL;
}

BinTree.h

#pragma once

typedef char BTDataType;

//孩子表示法
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;


// 构建二叉树
BTNode* BinaryTreeCreate(BTDataType a[], int n,BTDataType invalid); 

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

//求树的高度
int BinTreeHeight(BTNode *root);

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

void TestBinTree();

BinTree.c

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include "BinaryTree.h"
#include "Queue.h"

//开辟空间
BTNode* BuyBinaryTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == node)
	{
		assert(0);
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}



// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	assert(root);
	if (NULL == *root)
	{
		return;
	}
	//按照后序遍历进行销毁
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	//判断该节点是否为空，返回值为0
	if (root == NULL)
		return 0;
	//判断其左右子树是否为空，都为空则返回1
	if (root->left == NULL && root->right == NULL)
		return 1;
	//递归
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//判断是否为空树或者k的值是否小于等于0
	if (root == NULL || k <= 0)
		return 0;
	//树不空并且k = 1
	if (k == 1)
		return 1;
	//k > 1
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

//求树的高度
int BinTreeHeight(BTNode *root)
{
	if (root == NULL)
	{
		return 0;
	}
	//左右子树高度加1 即为树的高度
	int leftHeight = BinTreeHeight(root->left);
	int rightHeight = BinTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	BTNode *ret = NULL;
	if (NULL == root)
		return NULL;
	if (x == root->data)
		return root;
	if (ret == BinaryTreeFind(root->left, x))
		return ret;
	return  BinaryTreeFind(root->right, x);
}

// 二叉树前序遍历(递归)
void BinaryTreePrevOrder(BTNode* root)
{
	if (root)
	{
		printf("%c ", root->data);
		BinaryTreePrevOrder(root->left);
		BinaryTreePrevOrder(root->right);
	}
}


// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreeInOrder(root->left);
		printf("%c ", root->data);
		BinaryTreeInOrder(root->right);
	}
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreePostOrder(root->left);
		BinaryTreePostOrder(root->right);
		printf("%c ", root->data);
	}
}

// 层序遍历，借助队列来实现
//1.定义一个队列并初始化，然后将根节点入队列
//2.只要队列不空,则循环以下步骤
//从队列中获取一个节点并遍历
//	若该节点的左孩子存在，则入队列
//	若该节点的右孩子存在，入队列
//    将队头元素删除
//3.销毁队列，只有队列在初始化之后才需要销毁
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	if (root == NULL)
	{
		assert(0);
		return;
	}
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* cur =  QueueFront(&q);
		printf("%c ", cur->data);
		if (cur->left)
		{
			QueuePush(&q, cur->left);
		}
		if (cur->right)
		{
			QueuePush(&q, cur->right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
}

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{

	Queue q;
	int flag = 0;
	//空树
	if (root == NULL)
		return 1;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		if (flag)
		{
			//从第一个不饱和的节点后，所有结点都不能有孩子
			if (cur->left || cur->right)
			{
				QueueDestroy(&q);
				return 0;
			}
		}
			//找树中第一个不饱和的结点
		else
		{
			if (cur->left && cur->right)
			{
				QueuePush(&q, cur->left);
				QueuePush(&q, cur->right);
				flag = 1;
			}
			else if (cur->left)
			{
				QueuePush(&q, cur->left);
				flag = 1;
			}
			else if (cur->right)
			{
				QueueDestroy(&q);
				return 0;
			}
			else
			{
				flag = 1;
			}
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return 1;
}



void TestBinTree()
{
	//int index = 0;
	char arr[] = { 'A','B','D','G','#','#','H','#','#','E','#','#','C','F','#','I','#','#','#'};
	BTNode *root = BinaryTreeCreate(arr, sizeof(arr) / sizeof(arr[0]),'#');
	printf("二叉树的前序遍历结果为:");
	BinaryTreePrevOrder(root);
	printf("\n");

	printf("二叉树的中序遍历结果为:");
	BinaryTreeInOrder(root);
	printf("\n");

	printf("二叉树的后序遍历结果为:");
	BinaryTreePostOrder(root);
	printf("\n");

	printf("二叉树的层序遍历结果为:");
	BinaryTreeLevelOrder(root);
	printf("\n");

	printf("该二叉树的节点个数为：%d\n", BinaryTreeSize(root));

	printf("该二叉树的叶子节点个数为：%d\n", BinaryTreeLeafSize(root));

	printf("该二叉树的第%d层的节点个数为：%d\n", 4, BinaryTreeLevelKSize(root, 4));

	printf("该二叉树的高度：%d\n", BinTreeHeight(root));

	printf("%p\n", BinaryTreeFind(root,'A'));
	printf("%p\n", BinaryTreeFind(root,'R'));

	BinaryTreeDestory(&root);
} 

测试

#include"Queue.h"
#include "BinaryTree.h"

int main()
{
	TestBinTree();
	//TestQueue();
	//system("pause");
	return 0;
}

以上就是本篇文章的重点，今天就到此结束了哈，有不同的观点或者有不同思路的朋友欢迎大家赏光私我哈，本着相互进步的原则，希望大家能多多向我提意见，谢谢~~