目录

一.二叉树链式结构的实现

1.二叉树的创建

2.二叉树的销毁

3.二叉树的遍历

1.深度优先

2.广度优先

4.求二叉树节点数

5.求二叉树叶子节点个数

6.求第k层节点数

7.查找值为x的节点

8.判断是否为完全二叉树

二.整体代码

1.BinaryTree.h

2.BinaryTree.c

3.Queue.h

4.Queue.c

5.test.c

       在上一篇中我们实现了二叉树的顺序结构——堆的实现,这次实现链式结构,若对堆不了解,可以观看https://blog.csdn.net/w200514/article/details/143086428?sharetype=blog&shareId=143086428&sharerefer=APP&sharesource=w200514&sharefrom=link

一.二叉树链式结构的实现

1.二叉树的创建

        对于二叉树的创建,我们只需要创建节点,并将其连接到左右节点上即可

//构建二叉树
BTNode* CreatNode(BTDataType x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp == NULL)
		return 0;

	BTNode* node = tmp;
	if (node == NULL)
		printf("申请内存失败");

	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}
 BTNode* A = CreatNode('A');
 BTNode* B = CreatNode('B');
 BTNode* C = CreatNode('C');
 BTNode* D = CreatNode('D');
 BTNode* E = CreatNode('E');

 A->_left = B;
 A->_right = C;
 B->_left = D;
 B->_right = E;

如图我们创建出了一个二叉树,在这里我们将空节点显示出来,以便于接下来遍历时的理解

2.二叉树的销毁

        二叉树的销毁从底部开始向上逐层销毁,我们用递归的方法来实现

//销毁
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}

3.二叉树的遍历

        二叉树遍历分为两种,广度优先(层序遍历),深度优先(前/中/后序遍历)

1.深度优先

        前/中/后序遍历的不同,主要是因为根节点遍历的顺序不同

前序遍历:按照根-左子树-右子树的顺序遍历.

        对于我们上图创建的二叉树来说,前序遍历应为A B D NULL NULL E NULL NULL C NULL NULL

为何会出现这种情况,我们将使用递归的方式来实现

//前序排列
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->_data);
	PrevOrder(root->_left);
	PrevOrder(root->_right);
}

中序遍历:左子树-根-右子树

NULL D NULL B NULL E NULL A NULL C NULL

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}

后序遍历:左子树-右子树-根

NULL NULL D NULL NULL E B NULL NULL C A

void LastOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	LastOrder(root->_left);
	LastOrder(root->_right);
	printf("%c ", root->_data);
}

2.广度优先

层序遍历:自上而下,自左而右的遍历

A B C D E

对于层序遍历,我们可以利用队列来实现.

        将根节点存入队列,每次取出一个节点,就将其的左右节点放入队列(如果有左右节点)

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return;
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%c ", front->_data);
		if (front->_left)
			QueuePush(&q, front->_left);
		if (front->_right)
			QueuePush(&q, front->_right);
	}
	QueueDestory(&q);
	printf("\n");
}

4.求二叉树节点数

        二叉树节点数我们只需要将左子树节点数加上右子树节点数,再加1(根节点)即可

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

5.求二叉树叶子节点个数

        当只有根节点时,返回1,否则返回左子树加右子树节点数

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->_left == NULL && root->_right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

6.求第k层节点数

int BinaryTreeLeveIKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLeveIKSize(root->_left, k - 1) + BinaryTreeLeveIKSize(root->_right, k - 1);
}

7.查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;

	BTNode* node = BinaryTreeFind(root->_left, x);
	if (node != NULL)
		return node;

	node = BinaryTreeFind(root->_right, x);
	if (node != NULL)
		return node;

	return NULL;
}

8.判断是否为完全二叉树

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return 1;

	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
			break;

		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestory(&q);
			return 0;
		}
	}
	QueueDestory(&q);
	return 1;
}

二.整体代码

1.BinaryTree.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;

void PrevOrder(BTNode* root);
void InOrder(BTNode* root);
void LastOrder(BTNode* root);
int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLeveIKSize(BTNode* root, int k);
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
BTNode* CreatNode(BTDataType x);
void BinaryTreeDestroy(BTNode* root);
void LevelOrder(BTNode* root);
int BinaryTreeComplete(BTNode* root);

2.BinaryTree.c

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

//前序排列
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->_data);
	PrevOrder(root->_left);
	PrevOrder(root->_right);
}

//中序排列
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}

//后序排列
void LastOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	LastOrder(root->_left);
	LastOrder(root->_right);
	printf("%c ", root->_data);
}

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return;
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%c ", front->_data);
		if (front->_left)
			QueuePush(&q, front->_left);
		if (front->_right)
			QueuePush(&q, front->_right);
	}
	QueueDestory(&q);
	printf("\n");
}

//求二叉树节点数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->_left == NULL && root->_right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

//二叉树第k层节点数
int BinaryTreeLeveIKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLeveIKSize(root->_left, k - 1) + BinaryTreeLeveIKSize(root->_right, k - 1);
}

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

	BTNode* node = BinaryTreeFind(root->_left, x);
	if (node != NULL)
		return node;

	node = BinaryTreeFind(root->_right, x);
	if (node != NULL)
		return node;

	return NULL;
}
//构建二叉树
BTNode* CreatNode(BTDataType x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp == NULL)
		return 0;

	BTNode* node = tmp;
	if (node == NULL)
		printf("申请内存失败");

	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}

//销毁
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;

	BinaryTreeDestroy(root->_left);
	BinaryTreeDestroy(root->_right);
	free(root);
}

//判断是否为完全二叉树,是返回1不是返回0
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
		return 1;

	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
			break;

		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestory(&q);
			return 0;
		}
	}
	QueueDestory(&q);
	return 1;
}

3.Queue.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

extern struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;

typedef struct QueueNode
{
    struct QueueNode* _next;
    QDataType _data;
}QueueNode;

typedef struct Queue
{
    QueueNode* _head;
    QueueNode* _tail;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

4.Queue.c

#include "Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->_head = pq->_tail = NULL;
}

//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);

	QueueNode* cur = pq->_head;
	while (cur != NULL)
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	pq->_head = pq->_tail = NULL;
}

//队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		printf("申请内存失败");
		exit(-1);
	}

	newNode->_data = x;
	newNode->_next = NULL;

	if (pq->_head == NULL)
		pq->_head = pq->_tail = newNode;
	else
		pq->_tail->_next = newNode;
		pq->_tail = newNode;
}

//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->_head);

	QueueNode* next = pq->_head->_next;
	free(pq->_head);
	pq->_head = next;

	if (pq->_head == NULL)
		pq->_tail = NULL;

}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_head);

	return pq->_head->_data;
}

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_tail);

	return pq->_tail->_data;
}

//返回1为空,返回0为非空
int QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->_head == NULL ? 1 : 0;
}

//获取数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	assert(pq->_head);

	QueueNode* cur = pq->_head;
	int size = 0;
	while (cur != NULL)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}

5.test.c

#include "BinaryTree.h"

void TestBinaryTree()
{
    BTNode* A = CreatNode('A');
    BTNode* B = CreatNode('B');
    BTNode* C = CreatNode('C');
    BTNode* D = CreatNode('D');
    BTNode* E = CreatNode('E');

    A->_left = B;
    A->_right = C;
    B->_left = D;
    B->_right = E;

    printf("前序排列: ");
    PrevOrder(A);
    printf("\n");

    printf("中序排列: ");
    InOrder(A);
    printf("\n");

    printf("后序排列: ");
    LastOrder(A);
    printf("\n");

    printf("层序排列: ");
    LevelOrder(A);
    printf("\n");

    printf("二叉树节点为: ");
    printf("%d", BinaryTreeSize(A));
    printf("\n");

    printf("二叉树叶子节点个数为: ");
    printf("%d",BinaryTreeLeafSize(A));
    printf("\n");

    printf("二叉树第3层节点数为: ");
    printf("%d",BinaryTreeLeveIKSize(A, 3));
    printf("\n");

    BTNode* result = BinaryTreeFind(A, 'C');
    if (result != NULL) 
    {
        printf("结点的地址为: %p\n", (void*)result);
        printf("结点的值为: %c\n", result->_data); 
    }
    else 
        printf("节点不存在\n");

    printf("%d", BinaryTreeComplete(A));
    BinaryTreeDestroy(A);
}

int main()
{
    TestBinaryTree();
    return 0;
}

# 数据结构 # c语言
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区