当前位置: 首页 > article >正文

【数据结构与算法】第9课—数据结构之二叉树(链式结构)

文章目录

  • 1. 二叉树的性质
  • 2. 链式结构二叉树
  • 3. 二叉树链式结构的4种遍历方式
  • 4. 二叉树节点个数
  • 5. 二叉树的叶子节点个数
  • 6. 二叉树第k层节点个数
  • 7. 二叉树的高度/深度
  • 8. 二叉树查找值为x的节点
  • 9. 二叉树的销毁
  • 10. 判断是否为完全二叉树
  • 11. 二叉树练习题
    • 11.1 单值二叉树
    • 11.2 相同的树
    • 11.3 另一棵树的子树
    • 11.4 二叉树的前序遍历
    • 11.5 二叉树遍历

1. 二叉树的性质

在这里插入图片描述
在这里插入图片描述


  • 假设一个二叉树有a个度为2的节点,b个度为1的节点,c个度为0的节点,那么该二叉树的边数是2a+b == a+b+c-1
  • 二叉树的边数等于其节点数-1
  • 二叉树度为2的节点数等于度为0的节点数-1
  • 完全二叉树的高度h = log2(n+1) 2为底,n+1为对数,n为二叉树节点数
  • 若完全二叉树的节点数为2n个,那么它的叶子节点数为n
  • 若完全二叉树的节点数为2n-1个,那么它的叶子节点数为n

2. 链式结构二叉树

  • 链式二叉树的数据结构

在这里插入图片描述

在这里插入图片描述


3. 二叉树链式结构的4种遍历方式

  • 前序遍历----根左右原则

在这里插入图片描述


//前序遍历
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,层序遍历就是从所在二叉树的根结点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历
  • 实现层序遍历需要额外借助数据结构:队列

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


在这里插入图片描述


//层序遍历
void LevelOrder(BTNode* root)
{
	//队列
	Queue q;
	QueueInit(&q);//初始化
	QueuePush(&q, root);//根节点入队
	//队列不为空
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);//取队头
		QueuePop(&q);//销毁队头
		printf("%c ", top->data);//打印队头
		//取出的队头的左子结点不为空入队
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		//取出的队头的右子结点不为空入队
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}
	QueueDestroy(&q);//销毁队列
}

4. 二叉树节点个数

在这里插入图片描述


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

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

在这里插入图片描述


//二叉树的叶子节点个数
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层节点个数

在这里插入图片描述


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

7. 二叉树的高度/深度

在这里插入图片描述


//二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

8. 二叉树查找值为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;
}

9. 二叉树的销毁

在这里插入图片描述


在这里插入图片描述


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

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

在这里插入图片描述


在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);//根节点入队
	//第一次遍历非空队列找NULL
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);//取队头
		QueuePop(&q);//出队头
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, top->left);//队头的左孩子入队
		QueuePush(&q, top->right);//队头的右孩子入队
	}
	//第二次遍历找NULL后是否有非NULL节点
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);//取队头
		QueuePop(&q);//出队头
		if (top != NULL)
		{
			QueueDestroy(&q);//销毁队列
			return false;
		}
	}
	//第二次循环中没有NULL
	QueueDestroy(&q);
	return true;
}

11. 二叉树练习题

11.1 单值二叉树

在这里插入图片描述

在这里插入图片描述


bool isUnivalTree(struct TreeNode* root) 
{
    //如果根节点为NULL,它也是单值二叉树
    if(root == NULL)
    {
        return true;
    }
    //如果根节点的左孩子节点存在且该节点的值不等于其左孩子节点的值
    if(root->left && root->val != root->left->val)
    {
        return true;
    }
    //如果根节点的右孩子节点存在且该节点的值不等于其右孩子节点的值
    if(root->right && root->val != root->right->val)
    {
        return true;
    }
    //说明当前节点和它的左孩子右孩子节点的值相等
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

11.2 相同的树

在这里插入图片描述
在这里插入图片描述


bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //两个二叉树都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //一个二叉树为空,另一个二叉树非空
    if(p == NULL || q == NULL)
    {
        return false;
    }

    //两个二叉树都是非空
    if(p->val != q->val)
    {
        return false;  //值不同返回
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

11.3 另一棵树的子树

在这里插入图片描述
在这里插入图片描述


bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //两个二叉树都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //一个二叉树为空,另一个二叉树非空
    if(p == NULL || q == NULL)
    {
        return false;
    }

    //两个二叉树都是非空
    if(p->val != q->val)
    {
        return false;  //值不同返回
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{
    //如果传过来的节点为空
    if(root == NULL)
    {
        return false;
    }
    //如果root和subRoot两个二叉树相同
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    //root和subRoot不是相同的树
    //分别判断subRoot是否是root的左子树和右子树
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

11.4 二叉树的前序遍历

在这里插入图片描述


在这里插入图片描述


 typedef struct TreeNode TreeNode;
 //求二叉树节点个数
 int TreeSize(TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }
 //前序遍历--根左右
 void PreOrder(TreeNode* root,int* arr,int* p)
 {
    if(root == NULL)
    {
        return ;
    }
    arr[(*p)++] = root->val;
    PreOrder(root->left,arr,p);
    PreOrder(root->right,arr,p);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //先求出二叉树节点的个数
    *returnSize = TreeSize(root);
    //为数组arr申请节点空间
    int* arr = (int*)malloc(sizeof(int)*(*(returnSize)));
    if(arr == NULL)
    {
        exit(1);
    }
    int i = 0;
    PreOrder(root,arr,&i);

    return arr;
}

11.5 二叉树遍历

在这里插入图片描述


在这里插入图片描述


#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
//创建二叉树的数据结构
typedef struct BinaryNode
{
    BTDataType data;
    struct BinaryNode* left;
    struct BinaryNode* right;
}BTNode;
//申请节点
BTNode* buyNode(char x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = x;
    node->left = node->right = NULL;
    return node;
}

//创建二叉树---根左右
BTNode* CreaterTreeNode(char* arr, int* p)
{
    if(arr[*p] == '#')
    {
        (*p)++;
        return NULL;
    }
    //如果读取到的数组元素不是'#'
    BTNode* root = buyNode(arr[*p]);
    (*p)++;
    root->left = CreaterTreeNode(arr, p);
    root->right = CreaterTreeNode(arr, p);

    return root;
}
//中序遍历
void InOrder(BTNode* root)
{
    if(root == NULL)
    {
        return;
    }
    //非空
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main() 
{
    //创建数组
    char arr[100];
    scanf("%s",arr);//读取字符串
    //创建二叉树
    int i = 0;//数组下标
    BTNode* root = CreaterTreeNode(arr,&i);
    //中序遍历
    InOrder(root);
    return 0;
}

http://www.kler.cn/a/387107.html

相关文章:

  • java模拟键盘实现selenium上下左右键 table中的左右滚动条实现滚动
  • ReactPress技术揭秘
  • Autosar CP DDS规范导读
  • 实战指南:理解 ThreadLocal 原理并用于Java 多线程上下文管理
  • 【韩老师零基础30天学会Java 】07章 面向对象编程(基础)
  • 算法训练(leetcode)二刷第二十三天 | 455. 分发饼干、*376. 摆动序列、53. 最大子数组和
  • es数据同步(仅供自己参考)
  • 机器学习中的分类:决策树、随机森林及其应用
  • 鸿道Intewell高实时架构:鸿道Intewell-Hyper II 构型
  • c语言宏定义的优缺点及举例说明
  • AscendC从入门到精通系列(二)基于Kernel直调开发AscendC算子
  • Vue禁止打开控制台/前端禁止打开控制台方法/禁用F12/禁用右键
  • 如何设置docker的定时关闭和启动
  • MCU的OTA升级(未完-持续更新)
  • 19. 异常处理
  • 2.4_SSRF服务端请求伪造
  • Docker lmdeploy 快速部署Qwen2.5模型openai接口
  • PHP静默活体识别API接口应用场景与集成方案
  • 常用的c++新特性-->day03
  • 持续集成(Continuous Integration, CI)和持续部署(Continuous Deployment, CD)
  • C++高级编程(8)
  • unity3d————屏幕坐标,GUI坐标,世界坐标的基础注意点
  • PHP API的数据交互类型设计
  • 短视频矩阵系统的源码, OEM贴牌源码
  • LSM树 (Log-Structured Merge Tree)、Cuckoo Hashing详细解读
  • ubuntu 22.04 server 安装 和 初始化 LTS