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

数据结构——小小二叉树第三幕（链式结构的小拓展，二叉树的创建，深入理解二叉树的遍历）超详细！！！

article 2024/11/27 15:53:31

在这里插入图片描述

文章目录

  • 前言
  • 一、二叉树的层序遍历
  • 二、二叉树的有关习题
    • 2.1 单值二叉树
      • 题目
      • 思路
      • 代码
    • 2.2 相同的树
      • 题目
      • 思路
      • 代码
    • 2.3 对称的树
      • 题目
      • 思路
      • 代码
    • 2.4 二叉树的遍历
      • 题目
      • 思路
      • 代码
    • 2.5 二叉树的遍历
      • 题目
      • 思路
      • 代码
    • 2.6 二叉树的有关选择题
  • 总结

前言

上篇博客我们学习了链式结构的二叉树，从递归角度实现了二叉树的前中后序遍历以及各种有关二叉树的结点个数和高度等函数，今天我们来学习一个不使用递归的二叉树的层序遍历以及一些二叉树有关的算法题，发车咯

一、二叉树的层序遍历

二叉树的层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
层序遍历还要借助我们的数据结构：队列

对队列不熟悉的可以看看我的这篇博客嗷
链接：栈和队列

有图才能有真相
在这里插入图片描述

其实就是当前一层的结点入队列，然后一个一个出队列，出队列时把该节点的左右孩子入队列，这样下一个层级的结点就跟着上一层结点之后啦，重复这个操作，层序遍历就完成啦。话不多说，上代码

这是队列的结构以及一些函数的声明
这里把之前的 int 改成 BTNode 就好啦 队列里面的元素是二叉树的结点类型*

typedef BTNode* QDataType;    //   int  改成  BTNode*
typedef struct QueueNode  //  队列内每个元素用链式结构 一个一个结点连接
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue   //  队列  
{
	QueueNode* phead;     // 队头
	QueueNode* ptail;     // 队尾
	int size;  
}Queue;

void QueueInit(Queue* pq);  //  队列初始化  

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

void QueuePop(Queue* pq);	//  出队    

bool QueueEmpty(Queue* pq);	// 判空函数  

QDataType QueueFront(Queue* pq);  //  获取对头元素  

QDataType QueueBack(Queue* pq);		//  获取队尾元素

int QueueSize(Queue* pq);		//  队内有效元素

void QueueDestory(Queue* pq);    //  销毁队列   

void QueuePrint(Queue* pq);   //  打印  方便测试代码

借助队列实现层序遍历

// 层序遍历
void LevelOrder(BTNode* root)
{
	//借助数据结构——队列
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);  //  初始第一层的根结点入队列   
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		cout<< top->data;
		//将队头左右孩子入队列（不为空）
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
	}
	QueueDestroy(&q);
}

学习了层序遍历之后，我们可以用它来判断二叉树是否为完全二叉树，因为完全二叉树是一层一层去填满每一个结点的，不能跳着填。

思路：正常层序遍历二叉树，当遇到空结点时，跳出循环，此时如果是完全二叉树，那它之后的结点除了空结点是没有有效结点的，如果有，那就不是完全二叉树。

在这里插入图片描述

// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		//把不为空的队头结点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//  第一个循环之后，来到第二个循环，没有遇到有效元素就是完全二叉树
	//队列不一定为空，继续取队头出队头  
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

层序遍历就到这里啦

二、二叉树的有关习题

2.1 单值二叉树

习题链接：单值二叉树

题目

在这里插入图片描述

思路

思路：本题给定一个二叉树，判断所有的结点的值是否相同
简简单单的一个题，就是递归判断每一个左右孩子是否与根结点相同就好啦
对于认真了解二叉树的遍历的我们，洒洒水啦

代码

class Solution 
{
public:
    bool isUnivalTree(TreeNode* root) 
    {
        if(root == NULL)
        return true;
        if(root->left && root->val != root->left->val)
        return false;
        if(root->right && root->val != root->right->val)
        return false;
        return isUnivalTree(root->left) && isUnivalTree(root->right);  
    }
};

轻松拿下
在这里插入图片描述

2.2 相同的树

习题链接：相同的树

题目

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

思路

思路：本题和上一题有些类似，算是上一个题的拓展学习吧，需要判断是不是两颗相同的树
我们就同时递归两个树就好啦，一边递归一边判断结点的值是否相等
另外再处理一下不是相同的两颗树的判断就好啦

代码

class Solution 
{
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        if(q == NULL && p == NULL)  //  如果两颗树的当前结点都为空  返回true
            return true;
        if(q == NULL || p == NULL)  //  如果其中有一个不为空  证明两颗树的结点个数不同
            return false;
        if(p->val != q->val)  //  值不相同
            return false;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); 
        //  递归到每个根节点的左右子树  
    }
};

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

2.3 对称的树

习题链接：对称的树

题目

在这里插入图片描述

思路

思路：本题要判断一颗树是否为对称二叉树
一开始没什么头绪，但是想到对称，就从对称入手了，除了第一层的根节点，如果符合对称条件，左右子树是两颗左右孩子相反的树，这好像与判断两颗相同的树有些许差别，但处理一下就好啦，递归第一颗树的左节点和第二颗树的右结点匹配，右结点与左结点匹配。

代码

class Solution 
{
public:
    bool check(TreeNode* p, TreeNode* q)
    {
        if(p == nullptr && q == nullptr)
        {
            return true;
        }
        if(p == nullptr || q == nullptr)
        {
            return false;
        } //  当前结点是否相等  以及 左右孩子反过来匹配判断   
        return p->val == q->val && check(p->left,q->right) && check(p->right,q->left);
    }
    bool isSymmetric(TreeNode* root) 
    {		//  递归第一个根结点的左右子树  分成两棵树来看  
        return check(root->left, root->right);
    }
};

也是稳稳的过啦
在这里插入图片描述

2.4 二叉树的遍历

习题链接：二叉树的遍历

题目

在这里插入图片描述

思路

思路：本题看起来就有难度了，就像上篇博客留下来的一个小问题，构建二叉树
本题根据读入的先序遍历，根据字符串创建二叉树，然后再进行中序遍历
这颗树建起来还不算麻烦，毕竟已经给了先序遍历，我们就构建链式结构，然后递归字符串的下标就好啦，走一遍先序遍历，然后把值赋给结点

代码

#include <functional>
#include <iostream>
using namespace std;
typedef struct BinaryTreeNode //  正常创建二叉树链式结构  
{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode*right;
}BTNode;
BTNode* BuyNode(char ch)   //  获取新结点函数  
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = ch;
    node->left = node->right =NULL;
    return node;
}
BTNode* createTree(string arr,int* pi)   //  建树过程  
{
    if(arr[*pi] == '#')   //  这里传了一个pi  表示字符串的下标   
    {
        (*pi)++;     //  如果当前字符是  #  pi++  返回  
        return NULL;
    }
    
    BTNode* root = BuyNode(arr[*pi]);   //  根据先序遍历  获取值为arr[pi]的结点  pi++
    (*pi)++;
    root->left =  createTree(arr, pi);
    root->right =  createTree(arr, pi);
    return root;               //  类似于先序遍历的过程建树  
}
void InOrder(BTNode* root)    //  再更具中序遍历输出就好了
{
    if(root == NULL)
    return ;
    InOrder(root->left);
    cout<<root->data<<' ';
    InOrder(root->right);
}
int main() 
{
    string arr;
    cin>>arr;
    int i = 0;
    BTNode* root = createTree(arr,&i);
    InOrder(root);
    return 0;
}

拿下
在这里插入图片描述

2.5 二叉树的遍历

本题就没有习题链接啦，是实验课的习题

题目

在这里插入图片描述

思路

思路：本题和上一题不同的是，上一题是给定先序遍历，然后再建树输出中序遍历。
但本题是给定后序遍历和中序遍历，再输出层序遍历。听起来有点不知道怎么处理了，只给定先序遍历建树还好，这里是给定后序和中序遍历。
**想到后序遍历（左右根）和中序遍历（左根右 ）的具体过程，可以根据后序遍历找根节点，然后再根据中序遍历找左右子树，**如此反复这个过程就好啦‘

假设我们有以下后序遍历和中序遍历的结果：

后序遍历：3 2 5 6 4 1
中序遍历：3 2 1 5 4 6

确定根节点：
在后序遍历中，最后一个元素 1 是根节点。

分割中序遍历：
在中序遍历中找到根节点 1 的位置，它将中序遍历分为左子树 3 2 和右子树 5 4 6。

递归构建子树：
对于左子树 3 2 和右子树 5 4 6，分别在后序遍历中找到对应的部分（去掉已处理的根节点）。
左子树的后序遍历是 3 2 ，右子树的后序遍历是 5 6 4。
对左子树和右子树重复上述过程，直到构建完整棵树。’
在这里插入图片描述
左子树：
在这里插入图片描述
右子树：
在这里插入图片描述
就是不断找当前根节点的左右子树，把一个大问题化成很多重复相同的子问题。

代码

这里小编就用c++来实现这个题目了嗷

#include<bits/stdc++.h>
using namespace std;
struct TNode     //  二叉树的结点结构   数据域  左右指针域  
{
	int data;
	TNode* left;
	TNode* right;
};
void LevelOrder(TNode* root)   //  层序遍历   
{
	queue<TNode*> q;   //  这里小编就直接使用   stl库的  queue  函数啦
	q.push(root);
	while (!q.empty())
	{
		TNode* top = q.front();
		q.pop();
		if (top == root)
			cout << top->data;
		else
			cout << ' ' << top->data;    //   这里的输出需要注意一下格式  因为题目的最后没有空格  
		if (top->left)
			q.push(top->left);
		if (top->right)
			q.push(top->right);    //  这些步骤就和前面讲的层序遍历一样  
	}
}
TNode* BuildTree(int* inorder,int * postorder,int n)   //  至关重要的环节  建树
{													//  根据后序遍历和中序遍历建树  
	if (n == 0)
		return nullptr;
	TNode* node = new TNode; 
	node->data = postorder[n - 1];        //   这里直接找到根节点  为后序遍历的最后一个数据  
	node->left = node->right = nullptr;
	int pos = 0;
	for (pos; pos < n; pos++)
	{
		if (inorder[pos] == postorder[n - 1])    //   然后再在中序遍历找到根结点   分出左右子树  
			break;								//   pos左边的就是左子树  pos 右边的就是右子树  
	}
	node->left = BuildTree(inorder, postorder, pos);   //  当前根节点的左子树   
	node->right = BuildTree(inorder + pos + 1, postorder + pos, n - pos - 1);   // 右子树  
	return node;			//  这里中序遍历要在pos结点之后  因为pos是根结点 
}							//  后序遍历在pos开始  因为根节点在结尾  
int main()					//  然后就是反复循环左右子树递归就好啦  就像前面举例一样   
{
	int inorder[50], postorder[50];   //  创建中序遍历和后序遍历的数组  
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)  
	{
		cin >> postorder[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> inorder[i];
	}
	TNode* root =  BuildTree(inorder, postorder, n);   //  建树
	LevelOrder(root);   // 层序遍历   
	return 0;
}

也是稳稳拿下了
在这里插入图片描述

2.6 二叉树的有关选择题

先来了解一些新的二叉树的性质：

对任何一棵二叉树, 如果度为 0 的叶结点个数为 n0 , 度为2 的分支结点个数为 n2 ,则有 n0 = n 2 + 1
在这里插入图片描述
假设一个二叉树有a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个二叉树的边数是2a+b
另一方面，由于共有a+b+c 个节点，所以边数等于a+b+c-1
结合上面两个公式：
2a+b = a+b+c-1 ，即： a = c-1

话不多说，上题

  1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
    A 不存在这样的二叉树
    B 200
    C 198
    D 199

由前面推导出来的 a = c-1 叶子结点个数有200个

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

已知是完全二叉树则有 b = 1或0 2a+b+1 = 2n 若要符合要求 b只能=1 所以 a = n-1 、c = n;

3.一棵完全二叉树的结点数为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

完全二叉树最后一层之前都是满的，所以可以根据2的次幂来求层数，前面在最开始讲到满二叉树时有结点个数的公式：结点个数 = 2^k-1 为层数
2的9次幂是512 所以这颗树的高度为10

4.一个具有767个结点的完全二叉树，其叶子结点个数为（）
A 383
B 384
C 385
D 386

完全二叉树，还是回到 b只能取1或0 则2a+b+1 = 767 b只能取0 推出 a = 383 c=384;

来一些链式二叉树的遍历题

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

越来越觉得完全二叉树是个好东西
左子树 b d e h 右子树 c f h
在这里插入图片描述

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为
A E
B F
C G
D H

找根节点 给了先序遍历 那不就是E嘛

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde

和我们前面根据中序遍历和后序遍历建树的题相似 ， 这不是手拿把掐吗
在这里插入图片描述

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

这个题更有意思，中序遍历和后序遍历相同，那不是只有左子树
在这里插入图片描述

总结

简单的一些二叉树的学习就到这里啦，目前小编的石粒还没有涉及到更深层次的二叉树
回顾前面两篇文章，从二叉树的基本概念到顺序结构二叉树（堆）的实现，再到链式结构二叉树的实现，然后是二叉树的遍历方式，最后到习题部分的巩固与深入，对二叉树的遍历越来越深刻，特别是根据中序遍历和后序遍历建树再层序遍历输出，对递归又有了进一步理解，小编持续进步中~~~~
下一篇我们将开启新的数据结构——排序，小编持续更新中，不要走开~~~~

在这里插入图片描述


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

相关文章：

  • AX58100+STM32使用FSMC接口，运行EtherCAT Slave协议栈
  • 零基础3分钟快速掌握 ——Linux【终端操作】及【常用指令】Ubuntu
  • 计算机毕业设计Hadoop+Spark音乐推荐系统 音乐预测系统 音乐可视化大屏 音乐爬虫 HDFS hive数据仓库 机器学习 深度学习 大数据毕业设计
  • 工作问题总结4
  • EXTI配置流程 含中断延时消抖点亮小灯
  • Qt中2D绘制系统
  • Vue进阶面试题目（四）
  • 【设计模式】【创建型模式（Creational Patterns）】之原型模式（Prototype Pattern）
  • 25A物联网微型断路器 智慧空开1P 2P 3P 4P-安科瑞黄安南
  • C# 泛型 学习理解记录
  • vue3+ts 我写了一个跟swagger.yml生成请求和响应实体（接口）
  • 电商平台数据获取：解锁商业洞察的多元渠道
  • #Verilog HDL# Verilog中的UDP原语
  • 2024算法基础公选课练习五（DFS2）
  • 前端---CSS（部分用法）
  • C++的中的继承
  • 计算机操作系统——进程控制（Linux）
  • 第八篇：CamX RawHdr Feature Enable
  • org.apache.log4j的日志记录级别和基础使用Demo
  • 【kafka01】消息队列与微服务之Kafka详解
  • 数据库（总结自小林coding）|索引失效的场景、慢查询、原因及如何优化？undo log、redo log、binlog 作用、MySQL和Redis的区别
  • 阿里云私服地址
  • SpringBoot（四十）SpringBoot集成RabbitMQ使用过期时间+死信队列实现延迟队列
  • 林业产品推荐系统：Spring Boot架构设计
  • K8s的水平自动扩容和缩容HPA
  • C#中面试的常见问题006