数据结构——二叉树

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* left; // 指向当前结点左孩子
 struct BinTreeNode* right; // 指向当前结点右孩子
 BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* parent; // 指向当前结点的双亲
 struct BinTreeNode* left; // 指向当前结点左孩子
 struct BinTreeNode* right; // 指向当前结点右孩子
 BTDataType data; // 当前结点值域
}；

2、二叉树的顺序结构及实现

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆+堆排序+topK问题-CSDN博客我的这篇博客里有详细介绍

3、二叉树链式结构的实现

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。

由于现在对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，待二叉树结构了解的差不多时，再回来研究二叉树真正的创建方式。

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

BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("BuyNode()::malloc()");
return NULL;
}
node->_data = x;
node->_left = node->_right = NULL;
return node;
}

BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);

node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}

3.1 BinaryTree.h

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

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

BTNode* BuyNode(BTDataType x);
// 建树
BTNode* CreatBinaryTree();
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);

// 二叉树的高度
int TreeHeight(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

3.2 BinaryTree.c

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

BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("BuyNode()::malloc()");
return NULL;
}
node->_data = x;
node->_left = node->_right = NULL;
return node;
}

BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);

node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}

void BinaryTreeDestory(BTNode** root)// 二叉树销毁
{
assert(root);
if (*root == NULL)
return;
BinaryTreeDestory(&(*root)->_left);
BinaryTreeDestory(&(*root)->_right);
free(*root);
}

void BinaryTreePrevOrder(BTNode* root)// 二叉树前序遍历 
{
if (root == NULL)
return;
printf("%d ", root->_data);
BinaryTreePrevOrder(root->_left);
BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)// 二叉树中序遍历
{
if (root == NULL)
return;
BinaryTreeInOrder(root->_left);
printf("%d ", root->_data);
BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)// 二叉树后序遍历
{
if (root == NULL)
return;
BinaryTreePostOrder(root->_left);
BinaryTreePostOrder(root->_right);
printf("%d ", root->_data);
}

层序遍历二叉树，用队列存储(先进先出)，出一个节点，带入其下一层的节点

pop，是pop链式队列的一个节点(里面存的是指向二叉树节点的指针)

pop掉指针，没有pop掉二叉树的节点

队列为空(节点都free了)，不需要destroy，只有节点开了堆上的空间，Queue q是开在栈上的空间

void BinaryTreeLevelOrder(BTNode* root)// 层序遍历
{
if (root == NULL)
return;

Queue q;
QueueInit(&q);
QueuePush(&q, root);

//while (!QueueEmpty(&q))
//{
//BTNode* front = QueueFront(&q);
//QueuePop(&q);
//if (front != NULL)
//{
//printf("%d ", front->_data);
//QueuePush(&q, front->_left);
//QueuePush(&q, front->_right);
//}
//}//会把叶子节点的两个NULL,push，对于空节点，要push，pop

while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->_data);
if(front->_left)
QueuePush(&q, front->_left);
if (front->_right)
QueuePush(&q, front->_right);
}//不会把叶子节点的两个NULL,push，队列里只有非空的节点

}

用leftheight和rightheight，记录高度，不然底层的节点要重复执行非常多次

int TreeHeight(BTNode* root)// 二叉树的高度
{
if (root == NULL)
return 0;
int leftheight = TreeHeight(root->_left);
int rightheight = TreeHeight(root->_right);
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

int BinaryTreeSize(BTNode* root)// 二叉树节点个数
{
return root == NULL ? 0 : 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);
}

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

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

3.3 Queue.h

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

//typedef BTNode* QDataType;//若要用BTNode*，要包含"BinaryTree.h"，我认为结构体声明，作用域和全局变量一样，typedef，作用域只在当前个文件里
typedef struct BinaryTreeNode* QDataType;//存二叉树节点指针，
// 链式结构：表示队列 
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}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);

3.4 Queue.c

#include "Queue.h"

// 初始化队列 
void QueueInit(Queue* q)
{
assert(q);
q->_front = q->_rear = NULL;
q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
if (tmp == NULL)
{
perror("QueueNode()::malloc()");
return;
}
tmp->_next = NULL;
tmp->_data = data;
if (q->size == 0)
{
q->_front = q->_rear = tmp;
}
else
{
q->_rear->_next = tmp;
q->_rear = tmp;
}
q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
assert(q);
if (q->size == 0)
{
printf("队列已空\n");
return;
}
QNode* del = q->_front;
q->_front = q->_front->_next;
if (q->_front == NULL)
{
q->_rear = NULL;
}
free(del);
del = NULL;
q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
return q->size;
}

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

// 销毁队列 
void QueueDestroy(Queue* q)
{
while (q->_front)
{
QNode* del = q->_front;
q->_front = q->_front->_next;
free(del);
}
q->_rear = NULL;
q->size = 0;
}

3.5 test(测试代码)

#include "BinaryTree.h"

int main()
{
BTNode* root = CreatBinaryTree();
printf("BinaryTreeSize:>%d\n", BinaryTreeSize(root));// 二叉树节点个数
printf("BinaryTreeLeafSize:>%d\n", BinaryTreeLeafSize(root));// 二叉树叶子节点个数
printf("BinaryTreeLevelKSize:>%d\n", BinaryTreeLevelKSize(root, 3));// 二叉树第k层节点个数
BTNode* ret = BinaryTreeFind(root, 4);// 二叉树查找值为x的节点
if (ret == NULL)
printf("BinaryTreeFind:> NoFind");
printf("BinaryTreeFind:>%d\n", ret->_data);
BinaryTreePrevOrder(root);// 前序遍历
printf("\n");
BinaryTreeInOrder(root);// 中序遍历
printf("\n");
BinaryTreePostOrder(root);// 后序遍历
printf("\n");
BinaryTreeLevelOrder(root);// 层序遍历
printf("\n");
printf("TreeHeight:>%d\n", TreeHeight(root));// 树的高度

BinaryTreeDestory(&root);// 二叉树销毁
return 0;
}

3.6 二叉树的创建

pi是下标i的地址，每次调用时，i要移动到下一个位置

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')//注意是字符''，不是字符串""
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[(*pi)++]);
root->_left = BinaryTreeCreate(a, pi);
root->_right = BinaryTreeCreate(a,pi);
return root;
}

注意：若要运行，注意把前面

BinaryTree.c 中遍历函数里的%d->%c，

BinaryTree.h 中 typedef int BTDataType;->typedef char BTDataType;

test.c 中 BTNode* ret = BinaryTreeFind(root, 'F');// 二叉树查找值为x的节点，x为字符
printf("BinaryTreeFind:>%c\n", ret->_data);

原文地址：https://blog.csdn.net/2302_80310672/article/details/142342939

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：银行核心系统的现代化改造，华为的答案是重塑敏捷和重塑韧性
下一篇：外包干了5天，技术退步明显.......

数据仓库-数据质量规范
改层数据是由上游ODS层的数据进行清洗，转化，过滤，归一化，汇总而生产的，具有高度的一致性，同时也是DWS和DM层的基石。数据质量管理是测度、提高和验证质量，以及整合组织数据的方法等一套处理准则，而体
阅读更多2024-09-27
python功能测试
是 Python 中非常流行的测试框架，简单易用，功能强大，适合编写单元测试和集成测试。是 Python 自带的单元测试框架，用于编写、组织和运行测试。的语法简单而灵活，非常适合写 Python 的测
阅读更多2024-09-27
企微SOP：构建标准化运营流程，驱动企业高效增长
企业应高度重视企微SOP的建设工作，通过明确目标、制定计划、跨部门协作、持续优化与迭代等策略，构建一套符合企业实际、高效实用的企微SOP体系，为企业的持续高效增长提供有力支撑。1、提升运营效率：通过明
阅读更多2024-09-27
鸿蒙开发（NEXT/API 12）【硬件（取消注册智慧出行连接状态的监听）】车载系统
取消注册智慧出行连接状态的监听。
阅读更多2024-09-27
python select interpreter vscode 配置
python select interpreter 配置
阅读更多2024-09-27
鸿蒙开发（NEXT/API 12）【硬件（获取出行业务事件信息）】车载系统
获取出行业务事件信息。
阅读更多2024-09-27
【Gitee自动化测试0】日程
研究junit + gitee的ci/cd自动化测试，写文档导出PDF。
阅读更多2024-09-27
Git 使用方法
方法二用的比较多将仓库链接复制在 git base here ----> git clone 仓库链接。
阅读更多2024-09-27
宠物智能听诊器：打造宠物健康的数字守护神
这款设备的设计充满了人性化，它考虑到了宠物主人的需求，提供了易于理解的健康指标和建议。宠物智能听诊器的出现，不仅提升了宠物的健康水平，也提高了宠物主人的生活质量。它倡导的是一种预防为主的健康管理理念，
阅读更多2024-09-27
WinHttp辅助类封装, GET, POST, 多线程下载文件
基于WinHttp封装, 实现多线程文件下载, GET请求, POST请求
阅读更多2024-09-27

数据结构——二叉树

1、二叉树的概念及结构

1.1 概念

1.2 特殊的二叉树

1.3 二叉树的性质

1.4 二叉树的存储结构

1.4.1 顺序存储

1.4.2 链式存储