链式二叉树及二叉树各种接口的实现(C)

🕗 发布于 2024-10-07 17:37 c语言 开发语言

二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第 $i$ 层上最多有 $2^{i-1}$ 个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 $2^{h}-1$
对任何一棵二叉树，如果度为0其叶结点个数为 $n_{0}$ ，度为2的分支结点个数为 $n_{2}$ ，则有 $n_{0}=n_{2}+1$
若规定根节点的层数为1，具有n个结点的满二叉树的深度， $h=\log_{2}(n+1)$
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为 $i$ 的结点有：
1. 若 $i > 0$ ， $i$ 位置节点的双亲序号： $(i - 1) /2$ ； $i = 0$ ， $i$ 为根节点编号，无双亲节点
2. 若 $2 i + 1 < n$ ，左孩子序号： $2 i + 1$ ， $2i+1\ge n$ 否则无左孩子
3. 若 $2 i + 2 < n$ ，右孩子序号： $2 i + 2$ ， $2i+2\ge n$ 否则无右孩子

链式结构的实现

![[Pasted image 20240927174228.png]]

每棵树都可以分解成根节点，根节点的左子树，根节点的右子树
这样可以从根节点开始一直往下拆解，直到这棵树的左右两个子树都是空树停止

二叉树的遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中。
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

前序
要求把树拆成根节点，左子树，右子树
遍历顺序：
1，{2，（3，N，N），（N）}，{4，（5，N，N），（6，N，N）}
中序
左子树，根，右子树
遍历顺序：
{（N，3，N），2，（N）}，1，{（N，5，N），4，（N，6，N）}
遍历顺序
后序
左子树，右子树，根
遍历顺序：
{（N，N，3），（N），2}，{（N，N，5），（N，N，6），4}，1
层序
一层一层走
1，2，4，3，5，6

普通的链式二叉树没有意义

二叉树树的实现

链式树的定义

typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;

有左右两个子树节点
还有val表示节点存的值

创建节点

BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node = NULL)
{
perror("malloc fail");
exit(-1);
}

node->val = x;
node->left = NULL;
node->right = NULL;

return node;
}

malloc一个树节点的内存空间大小
判断空间是否创建成功
将节点的值置为x，左子树和右子树的指针置为空

二叉树的递归结构

递归调用展开图
![[Pasted image 20240929160449.png]]

先序中序后序遍历实现

void PrevOrder(BTNOde* root)
{
if (root == NULL)
return;

printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}

void InOrder(BTNOde* root)
{
if (root == NULL)
return;

InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}

void PostOrder(BTNOde* root)
{
if (root == NULL)
return;

PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}

通过递归实现遍历二叉树
先实现返回条件，当目前子树的根节点是空时，返回
这里是双路递推，先是递推左子树，再递推右子树，前中后遍历分别在两次递推的前中后访问根节点的值

节点个数

局部静态变量

int TreeSize(BTNode* root)
{
static int size = 0;
if (root == NULL)
return 0;
else
++size;

TreeSize(root->left);
TreeSize(root->right);

return size;
}

静态变量和全局变量存在于静态区，所以各个位置的size指同一个size，因为都是从静态区去取的，不是栈帧里面都有的
不会每次都走初始化，局部的静态成员变量只会执行一次
但是当多次调用这个函数时，size会累加，不符合预期。每次调用都要初始化为0
目前生命周期是全局的，作用域是局部的
这是不对的，这样的treesize是一次性的。
2. 手动初始化

int size = 0;

int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
++size;

TreeSize(root->left);
TreeSize(root->right);

return size;
}

在全局初始化size为0，之后调用的时候手动将size置为0
会发生限制安全问题
3. 变为递归子问题
遇到根节点，想求这棵树的节点个数，返回它的两棵子树的节点个数，接着找子树的子树，一直递归直到子树为空
树的节点的个数等于左子树节点的个数加右子树节点的个数再加自己

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

![[Pasted image 20241001113806.png]]

叶子节点个数

节点是空，返回0
节点是叶子节点，返回1
都不是，返回左子树和右子树

int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;

if (root->left == NULL && root->right == NULL)
{
return 1;
}

return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

![[Pasted image 20241001130133.png]]

第k层的节点个数

当前树的第k层=左子树的第k-1层+右子树的第k-1层
一直到某一节点的第一层
如果为空，返回0；不为空，返回1

int TreeKLevel(BTNode* root, int level)
{
assert(k > 0);

if (root == NULL)
return 0;

if (k == 1)
{
return 1;
}

return TreeKLever(root->left, k-1) 
+ TreeKLever(root->right, k-1);
}

![[Pasted image 20241001140506.png]]

销毁

遇到一个根节点，先销毁左子树，再销毁右子树，回来再销毁自己

void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}

TreeDestroy(root->left);
TreeDestroy(root->right);

free(root);
}

不需要置空，形参的改变不影响实参

查找

如果节点为空，返回空
如果节点的值等于x，返回节点
左子树找到就不用到右子树找了

//二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;

if (root->val == x)
return root;

return TreeFind(root->left, x)
|| TreeFind(root->right, x);
}

这样返回的不是节点的指针，返回的是x在不在，是空指针或1的结果
如果这个函数返回的是bool值，只判断真和假

BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;

if (root->val == x)
return root;

BTNode* ret = NULL;
ret = TreeFind(root->left, x);
if (ret)
return ret;

ret = TreeFind(root->right, x);
if (ret)
return ret;

return NULL;
}

如果左边找到了，就return一下
如果没找到，就去右边找，找到了就return
如果右边也没找到，就返回空

若x=3
若x=4

类似写法

BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;

if (root->val == x)
return root;

BTNode* ret = NULL;
ret = TreeFind(root->left, x);
if (ret)
return ret;

return TreeFind(root->right, x);

}

层序遍历

先进先出
根节点入队列，出队列的时候将它的两个左子节点和右子节点插入队列
上一层带下一层
因为要存的是树的指针，所以队列的数据类型要改为BTNode*
.h文件不会被编译，而会在.c文件里面展开，所以要包含队列的.h文件，include语句要在树的结构体的下面，这样.h文件可以找见树的定义

void LevelOrder(BTNode* root)
{
Que q;
QueueInit(&q);

if (root)
QueuePush(&q, root);

while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->val);
if (front->left)
QueuePush(&q, front->left);

if (front->right)
QueuePush(&q, front->right);

QueuePop(&q);
}
printf("\n");

QueueDestroy(&q);
}

判断完全二叉树

完全二叉树走层序遍历的特征
完全二叉树在满二叉树的基础上，前n-1层都是满的，最后一层不满
但是最后一层，从左到右是连续的
如果这棵树是完全二叉树，这棵树层序遍历都是连续的
即层序：非空节点是连续的就是完全二叉树；非空节点是不连续，中间有空节点，就是非完全二叉树
要判断是否连续，层序遍历的时候，把NULL也入进去
非完全二叉树，出现空了以后，一定还有非空在队列里面

int TreeComplete(BTNode* root)
{
Que q;
QueueInit(&q);

if (root)
QueuePush(&q, root);

while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front == NULL)
break;

QueuePush(&q, front->left);
QueuePush(&q, front->right);
QueuePop(&q);
}

//已经遇到空节点，如果队列中后面还有非空，就不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);

if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}

QueueDestroy(&q);
return true;
}

pop了以后还可以访问front节点，pop删除的是队列的节点，不会影响树的节点
队列里有指针指向树的节点
取front，相当于用一个front指针指向队头的节点
队列为空才能结束，不是到那个节点结束

返回树的高度

对于根节点而言，如果求出了左子树的高度和右子树的高度
树的高度等于左子树和右子树高的那一个加1
空树的时候，高度取0

int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

这样写运算消耗很大，会重复计算，每棵树都是这样
所以要把每次计算出来的值保存下来

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 TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

return fmax(TreeHeight(root->left), TreeHeight(root-<right)) + 1;
}

没有重复计算

深度优先广度优先

深度优先遍历：前序遍历，递归
广度优先遍历：层序遍历，队列配合

声明定义分离实现

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

typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;

BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node = NULL)
{
perror("malloc fail");
exit(-1);
}

node->val = x;
node->left = NULL;
node->right = NULL;

return node;
}

void PrevOrder(BTNOde* root)
{
if (root == NULL)
return;

printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}

void InOrder(BTNOde* root)
{
if (root == NULL)
return;

InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}

void PostOrder(BTNOde* root)
{
if (root == NULL)
return;

PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}

//节点个数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

//叶子节点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;

if (root->left == NULL && root->right == NULL)
{
return 1;
}

return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

//第k层节点个数
int TreeKLevel(BTNode* root, int level)
{
assert(k > 0);

if (root == NULL)
return 0;

if (k == 1)
{
return 1;
}

return TreeKLever(root->left, k-1) 
+ TreeKLever(root->right, k-1);
}

//二叉树销毁
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}

TreeDestroy(root->left);
TreeDestroy(root->right);

free(root);
}

//二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;

if (root->val == x)
return root;

TreeFind(root->left, x);
TreeFind(root->right, x);
}

void LevelOrder(BTNode* root)
{
Que q;
QueueInit(&q);

if (root)
QueuePush(&q, root);

while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->val);
if (front->left)
QueuePush(&q, front->left);

if (front->right)
QueuePush(&q, front->right);

QueuePop(&q);
}
printf("\n");

QueueDestroy(&q);
}

int TreeComplete(BTNode* root)
{
Que q;
QueueInit(&q);

if (root)
QueuePush(&q, root);

while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front == NULL)
break;

QueuePush(&q, front->left);
QueuePush(&q, front->right);
QueuePop(&q);
}

//已经遇到空节点，如果队列中后面还有非空，就不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);

if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}

QueueDestroy(&q);
return true;
}

int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

return fmax(TreeHeight(root->left), TreeHeight(root-<right)) + 1;
}

int main()
{
//手动构建二叉树
BTNode* node1 = BuyNode(1);
BTNode* node1 = BuyNode(2);
BTNode* node1 = BuyNode(3);
BTNode* node1 = BuyNode(4);
BTNode* node1 = BuyNode(5);
BTNode* node1 = BuyNode(6);

node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;

PrevOrder(node1);
printf("\n");

InOrder(node1);
printf("\n");

PostOrder(node1);
printf("\n");

return 0;
}

原文地址：https://blog.csdn.net/CoderZzz6310/article/details/142727070

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

上一篇：代码随想录算法训练营第二十七天|第77题. 组合 216.组合总和III 17.电话号码的字母组合
下一篇：动态版通讯录（在前一个基础上修改）

职场中的人情世故，你懂了多少？
事情可以干，可以做得好，但是不要炫耀自己是天下第一。职场上的各种光怪陆离现象，有很多职场人吐槽：“人情世故难过大学高数“，“工作之后才知道，高考是你所能经历的最公平的事”，“钱难挣，屎难吃，全是坑”。
阅读更多2024-10-08
深度学习中的结构化概率模型 - 学习依赖性的关系篇
在深度学习的探索之旅中，结构化概率模型以其独特的能力，在学习数据间复杂依赖关系方面展现出非凡的潜力。传统模型往往难以有效捕捉变量间错综复杂的相互作用，而结构化概率模型则通过引入结构化的先验知识，使得模
阅读更多2024-10-08
TypeScript 算法手册【选择排序】
选择排序是一种简单直观的排序算法。它的工作原理是: 在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小(大)元素，接着放到已排序序列的末尾。以此类推，直到所有
阅读更多2024-10-08
Python操作TXT文本：从入门到精通
通过本文的介绍，您已经掌握了Python操作TXT文本的基本方法，包括读取和写入文本内容、处理文本内容以及分割和合并文本。这些技能在数据分析、自动化脚本编写、网站内容管理等领域都有广泛的应用。希望本文
阅读更多2024-10-08
旋转位置编码Rope
大模型都在用的：旋转位置编码-CSDN博客https://zhuanlan.zhihu.com/p/690726751
阅读更多2024-10-08
2024四大剪辑软件推荐及下载地址介绍！
在这个数字时代，视频成为了我们记录生活、分享故事的重要手段。无论是专业摄影师还是业余爱好者，都需要一款好用的视频剪辑软件来将自己的创意变为现实。下面，我将为大家介绍几款各有特色的视频剪辑工具，同时也附
阅读更多2024-10-08
【AI知识点】反向传播（Backpropagation）
反向传播（Backpropagation）是训练神经网络的核心算法，它通过反向逐层计算损失函数对每个权重的梯度，来反向逐层更新网络的权重，从而最小化损失函数。
阅读更多2024-10-08
如何使用Immersity AI将图片转换成3D效果视频
通过以上简单的五个步骤，你就可以利用Immersity AI将图片转换成3D效果视频。无论是艺术创作、营销宣传，还是个人兴趣，你都可以尝试这一技术，提升你的作品质量。系统会开始处理你的请求，并生成3D
阅读更多2024-10-08
Python的多线程与多进程：并发编程基础与实战
本文详细介绍了Python中的并发编程，涵盖多线程、多进程和异步编程（asyncio）的基本原理和应用场景。文章分析了各技术的优势和局限，并通过代码示例展示了如何使用threading、multipr
阅读更多2024-10-08
多线程编程的利器：C++线程锁深度解析
在多线程编程中，线程锁是确保数据一致性和防止竞态条件的关键机制。C++11及之后的版本提供了多种线程锁，以满足不同场景下的并发控制需求。以下将详细分析几种常见的C++线程锁的原理、应用场景、优缺点，并
阅读更多2024-10-08