【数据结构】树-二叉树(链式)
🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍
目录
🐼前言
🌟在上一节我们实现了二叉树的堆排序，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 堆排序，这一节小编给大家介绍二叉树的链式结构。
🐼用链式结构实现二叉树
❄️链式结构的二叉树就是通过指针的关系将逻辑关系串起来。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来指向该结点左孩子和右孩子所在的链结点的存储地址 :
二叉树节点定义如下:
//定义二叉树节点类型
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;//左节点
struct BinaryTreeNode* right;//右节点
BTDataType data;
}BTNode;
🐼遍历规则
🐟我们知道，二叉树有空树和非空二叉树。而非空二叉树又是由根节点，左子树，右子树构成。左子树又是子树节点，子树节点的左子树，子树节点的右子树构成的。所以二叉树的定义是递归的。
我们先学习二叉树几种常见的遍历方式:
🔍前序遍历:访问根结点的操作发生在遍历其左右子树之前。访问顺序为：根结点、左子树、右子树。
🔍中序遍历: 访问根结点的操作发生在遍历其左右子树之间。访问顺序为：左子树、根结点、右子树。
🔍 后序遍历:访问根结点的操作发生在遍历其左右子树之后。访问顺序为：左子树、右子树、根结点。
以前序遍历为例:
🐼手动创建二叉树
🌟为了演示下面的遍历,我们先手动创建一颗二叉树:
BTNode* BuyNode(BTDataType x)
{
BTNode* node =(BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->left = node->right = NULL;
node->data = x;
return node;
}
BTNode* CreateTree()
{
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
🌻代码解析
🌟这里我们手动创建了一颗二叉树。每一个结点都是向操作系统申请的，根据根节点，左子树，右子树的逻辑关系将二叉树连接起来。
手动创建的二叉树:
🐼前序遍历
//前序遍历--根左右
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
🌻代码解析
📋前序遍历访问根结点的操作发生在遍历其左右子树之前。如果根节点是NULL,即走到空，打印并直接返回。遇到根节点，直接打印其保存的数值，接着左子树再向下递归，进行前序遍历；右子树再向下递归，进行前序遍历。按照这样的顺序 根-左子树-右子树直到把整颗二叉树遍历完。
我们可以把二叉树的每一个结点都看做一开辟好的函数栈帧。
🍂画图剖析:
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍀测试结果:
🐼中序遍历
//中序遍历--左根右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
🌻代码解析
📋中序遍历访问根结点的操作发生在遍历其左右子树之间。如果根节点是NULL,即走到空，打印并直接返回。先是左子树再向下递归，进行中序遍历；左子树递归完，再遇到根节点，直接打印其保存的数值；右子树再向下递归，进行中序遍历。按照这样的顺序
左子树-根-右子树直到把整颗二叉树遍历完。
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼后序遍历
//后序遍历--左右根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
🌻代码解析
📋后序遍历访问根结点的操作发生在遍历其左右子树之后。如果根节点是NULL,即走到空，打印并直接返回。先是左子树再向下递归，进行后序遍历；接着右子树再向下递归，进行后序遍历；左右子树递归完，再遇到根节点，直接打印其保存的数值。按照这样的顺序左子树-右子树-根直到把整颗二叉树遍历完。
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼二叉树节点个数
// 二叉树结点个数--1+左子树+右子树
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
🌻代码解析
📋首先设置递归出口，如果根节点是NULL,即走到空，表示没有节点，直接返回0。接着左子树向下递归，求左子树的节点个数，右子树向下递归，求右子树的节点个数，再加上当前节点的个数(+1表示自已)。即整个二叉树的节点个数为当前节点的个数(1)+左子树节点的个数+右子树节点的个数
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼二叉树叶子节点个数
/ ⼆叉树叶子结点个数
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);
}
🌻代码解析
📋首先设置递归出口，如果根节点是NULL,即走到空，表示没有节点，直接返回0，如果根节点的左右孩子都为NULL，表示是叶子节点，返回1。接着左子树向下递归，求左子树的叶子节点个数，右子树向下递归，求右子树的叶子节点个数。即整个二叉树的叶子节点个数为左子树叶子节点的个数+右子树叶子节点的个数
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼二叉树第k层结点个数
// ⼆叉树第k层结点个数
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);
}
🌻代码解析
📋首先设置递归出口，如果根节点是NULL,即走到空，表示不是第K层节点，直接返回0。递归每次让k–(深度优先遍历)，如果K==1，表示是第k层节点，直接返回1。接着左子树向下递归，求左子树的第k层叶子节点个数，右子树向下递归，求右子树的第k层叶子节点个数。即整个二叉树的第k层叶子节点个数为左子树叶子第k层节点的个数+右子树第k层叶子节点的个数
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼二叉树的深度/高度
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
//根节点+max(左右子树的最大层次)
if (root == NULL)
{
return 0;
}
int leftdep = BinaryTreeDepth(root->left);
int rightdep = BinaryTreeDepth(root->right);
return 1 + (leftdep > rightdep ? leftdep : rightdep);
}
🌻代码解析
📋首先设置递归出口，如果根节点是NULL,即走到空，直接返回0。。接着左子树向下递归，求左子树的深度，右子树向下递归，求右子树的深度。即整个二叉树的深度根节点+(左右子树的最大深度)
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼二叉树查找值为x的结点
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftfind = BinaryTreeFind(root->left, x);
if (leftfind)
{
return leftfind;
}
BTNode* rightfind = BinaryTreeFind(root->right, x);
if (rightfind)
{
return rightfind;
}
return NULL;
}
🌻代码解析
📋首先设置递归出口，如果根节点是NULL,即走到空，直接返回NULL，表示未找到；如果根节点保存的值是x,即存在，直接返回该节点，表示找到。接着左子树向下递归，如果左子树中有要查找的x，直接返回，左子树没找到，右子树向下递归，如果右子树中有要查找的x，直接返回。即要查找的x左子树查找+右子树查找
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼二叉树销毁
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
//左右根
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}
🌻代码解析
📋首先设置递归出口，如果根节点是NULL,即走到空，直接返回NULL，先是左子树再向下递归，进行后序遍历；接着右子树再向下递归，进行后序遍历；左右子树递归完，再遇到根节点，直接释放该节点。按照这样的顺序左子树-右子树-根直到把整颗二叉树的节点释放完。(注意:释放节点需要将根节点地址传过去，以保证对形参的修改，可以影响到实参)
时间复杂度为O(N)二叉树的每个节点都只会被访问一次
🍂画图剖析:
🍀测试结果:
🐼层序遍历
⚽️除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历(广度优先遍历)。设二叉树的根结点所在层数
为1，层序遍历就是从所在⼆叉树的根结点出发，首先访问第⼀层的树根结点，然后从左到右访问第2
层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层
序遍历。比如该图的层序遍历为:ABCDEF
实现层序遍历我们需要借助数据结构队列:
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
InitQueue(&q);
PushQueue(&q, root);
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
printf("%c ", top->data);
PopQueue(&q);
if (top->left)
{
PushQueue(&q, top->left);
}
if (top->right )
{
PushQueue(&q, top->right);
}
}
printf("\n");
QueueDestroy(&q);
}
🌻代码解析
📋创建队列，队列每一个元素类型都是二叉树的节点。我先将根节点入队列。接着，如果队列不为空，我就取队头元素并打印，并将队头元素的左右孩子入队列(如果左右孩子不为空),循环往复，直到队列为空。
时间复杂度为O(N)，程序只遍历一次，每个树的节点只会访问一次
🍂画图剖析:
🍀测试结果:
🐼 判断二叉树是否是完全二叉树
🎳完全二叉树指的是最后一层节点不一定达到最大，并从左向右依次排列。
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
InitQueue(&q);
PushQueue(&q, root);
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
PopQueue(&q);
if (top == NULL)
{
break;
}
//不管是不是NULL，将top的左右孩子入队列
PushQueue(&q, top->left);
PushQueue(&q, top->right);
}
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
PopQueue(&q);
if (top != NULL)
{
QueueDestroy(&q);
return false;
}
}
return true;
QueueDestroy(&q);
}
🌻代码解析
📋借助刚刚完成的层序遍历的思想。创建队列，队列每一个元素类型都是二叉树的节点。我先将根节点入队列。接着，如果队列不为空，我就取队头元素并判断是否为空，如果取到的队头元素为空，直接退出循环，如果不为空，将队头元素的左右孩子入队列(不管左右孩子是否为空)。再循环取队头元素时，如果队头不为空，则该树不是完全二叉树，如果全部取完，都为空，则该树是完全二叉树。换句话说，第二个取队列的所有元素都应该为空。
时间复杂度为O(N)，程序只遍历一次，每个树的节点只会访问一次
🍂画图剖析:
🍀测试结果:
🐼全部源码
Tree.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义二叉树节点类型
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;//左节点
struct BinaryTreeNode* right;//右节点
BTDataType data;
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);
//void BinaryTreeSize(BTNode* root,int* psize);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
Tree.c
#include "Tree.h"
#include "Queue.h"
//前序遍历--根左右
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历--左根右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
//后序遍历--左右根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
// 二叉树结点个数--1+左子树+右子树
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// ⼆叉树叶子结点个数
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 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);
}
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
//根节点+max(左右子树的最大层次)
if (root == NULL)
{
return 0;
}
int leftdep = BinaryTreeDepth(root->left);
int rightdep = BinaryTreeDepth(root->right);
return 1 + (leftdep > rightdep ? leftdep : rightdep);
}
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftfind = BinaryTreeFind(root->left, x);
if (leftfind)
{
return leftfind;
}
BTNode* rightfind = BinaryTreeFind(root->right, x);
if (rightfind)
{
return rightfind;
}
return NULL;
}
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
//左右根
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
InitQueue(&q);
PushQueue(&q, root);
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
printf("%c ", top->data);
PopQueue(&q);
if (top->left)
{
PushQueue(&q, top->left);
}
if (top->right )
{
PushQueue(&q, top->right);
}
}
printf("\n");
QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
InitQueue(&q);
PushQueue(&q, root);
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
PopQueue(&q);
if (top == NULL)
{
break;
}
//不管是不是NULL，将top的左右孩子入队列
PushQueue(&q, top->left);
PushQueue(&q, top->right);
}
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
PopQueue(&q);
if (top != NULL)
{
QueueDestroy(&q);
return false;
}
}
return true;
QueueDestroy(&q);
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include "Tree.h"
BTNode* BuyNode(BTDataType x)
{
BTNode* node =(BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->left = node->right = NULL;
node->data = x;
return node;
}
BTNode* CreateTree()
{
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
void test()
{
BTNode* root = CreateTree();
//PreOrder(root);
//InOrder(root);
//PostOrder(root);
//printf("Treesize:%d\n", BinaryTreeSize(root));
//printf("LeafSize:%d\n", BinaryTreeLeafSize(root));
/*printf("LeveKSize:%d\n", BinaryTreeLevelKSize(root, 3));
printf("LeveKSize:%d\n", BinaryTreeLevelKSize(root, 2));*/
printf("TreeDepth:%d\n", BinaryTreeDepth(root));
//BTNode* tmp = BinaryTreeFind(root,'E');
//printf("%c\n", tmp->data);
//if (BinaryTreeFind(root, 'E') != NULL)
//{
//printf("找到了\n");
//}
//else
//{
//printf("未找到\n");
//}
//BinaryTreeLevelOrder(root);
if (BinaryTreeComplete(root))
{
printf("是完全二叉树！\n");
}
else
{
printf("不是完全二叉树!\n");
}
BinaryTreeDestory(&root);
}
int main()
{
test();
return 0 ;
}
🐼文末
感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️
原文地址：https://blog.csdn.net/2401_83251330/article/details/143451472
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！