二级公共基础之数据结构与算法篇(五)树和二叉树

news/2025/2/23 10:36:33

目录

前言

一、树的基本概念

1.父结点和根节点

2.子节点和叶子节点

3.度和深度

4.子树

二、二叉树及其基本性质

1. 二叉树的定义

2. 二叉树的基本性质

性质1

性质2

性质3

性质4

性质5

性质6

三、二叉树的存储结构

四、二叉树的遍历

1.遍历二叉树的概念

1. 前序遍历二叉树

2. 中序遍历二叉树

3. 后序遍历二叉树

4. 层次遍历二叉树

2.常考题目

五、二叉树中常考题目

1.完全二叉树

前言

        这篇博客主要介绍树和二叉树。树是一种常见的数据结构，广泛应用于计算机科学和工程领域，如文件系统、数据库索引、表达式解析等。二叉树是树的一种特殊形式，具有许多独特的性质和应用。

一、树的基本概念

        树（Tree）是一种简单的非线性结构。

        图1.二叉树

1.父结点和根节点

        在树结构中，每一个结点有一个直接前驱，称为父节点。

        没有前驱的节点只有一个，称为树的根节点。

        在图1中，A节点是树的根节点。

2.子节点和叶子节点

        在树结构中，每一个节点可以有多个直接后继，称为子节点。

        没有子节点的节点称为叶子节点。

        叶子节点是树的最底层节点。

        在图1中D、H、I、F、G均为叶子节点。

3.度和深度

        在树结构中，节点所拥有的子节点的个数称为该节点的度。

       在图1中节点A和节点E的度为2，节点C的度为1。

        节点的深度是从根节点到该节点的路径长度。

        树的深度是所有节点深度的最大值。

4.子树

        在树结构中，以某节点的一个子节点为根构成的树称为该节点的一棵子树。

二、二叉树及其基本性质

        二叉树是一种特殊的树，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

1. 二叉树的定义

        二叉树可以为空，也可以由一个根节点和两个互不相交的子树组成，分别称为左子树和右子树。

2. 二叉树的基本性质

性质1

        在二叉树的第k层上最多有$2^{k-1}$个节点（k≥1）。

性质2

        深度为k的二叉树中，最多有$2^{k-1}$个节点。

性质3

        对任意一棵二叉树，度为0的节点(即叶子节点)总比度为2的节点多一个。​

性质4

        具有n个节点的二叉树，其深度至少为[\log_{2} n]+1，其中\log_{2} n表示表达式的整数部分。

性质5

        具有n个节点的完全二叉树的深度为[\log_{2} n]+1

性质6

图2.二叉树的性质6

三、二叉树的存储结构

        二叉树通常采用链式存储结构。用于存储二叉树中数据元素的存储节点由数据域和指针域两部分组成。指针域包括左指针域和右指针域。

四、二叉树的遍历

1.遍历二叉树的概念

        二叉树的遍历是指按照某种顺序访问二叉树中的所有节点。常见的遍历方法有前序遍历、中序遍历和后序遍历。

1. 前序遍历二叉树

        前序遍历二叉树(Pre_order Traversal)是先遍历左子树，然后遍历根节点和右子树。

        访问顺序：根节点 -> 左子树 -> 右子树。

2. 中序遍历二叉树

        前序遍历二叉树(In_order Traversal)是先遍历根节点，然后遍历左子树和右子树。

        访问顺序：左子树 -> 根节点 -> 右子树。

3. 后序遍历二叉树

        前序遍历二叉树(Post_order Traversal)是先遍历左子树，然后遍历根节点和右子树。

        访问顺序：左子树 -> 右子树 -> 根节点。

4. 层次遍历二叉树

        层次遍历二叉树(Level_order Traversal)是按照树的层次从上到下，从左到右依次访问每个节点。用队列实现，先访问根节点。

        访问顺序：左子树 -> 右子树 -> 根节点。

        以下是二叉树的前序、中序和后序遍历的实现：

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

// 定义二叉树节点
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义队列节点
typedef struct QueueNode {
    TreeNode *treeNode;
    struct QueueNode *next;
} QueueNode;

// 定义队列
typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 创建队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

// 入队
void enqueue(Queue* queue, TreeNode* treeNode) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;

    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队
TreeNode* dequeue(Queue* queue) {
    if (queue->front == NULL) {
        return NULL;
    }

    QueueNode* temp = queue->front;
    TreeNode* treeNode = temp->treeNode;
    queue->front = queue->front->next;

    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    free(temp);
    return treeNode;
}

// 判断队列是否为空
int isEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 层次遍历
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return;

    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isEmpty(queue)) {
        TreeNode* currentNode = dequeue(queue);
        printf("%d ", currentNode->data);

        if (currentNode->left != NULL) {
            enqueue(queue, currentNode->left);
        }
        if (currentNode->right != NULL) {
            enqueue(queue, currentNode->right);
        }
    }

    free(queue);
}

// 前序遍历
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 中序遍历
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left);
    printf("%d ", root->data);
    inOrderTraversal(root->right);
}

// 后序遍历
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%d ", root->data);
}

// 主函数
int main() {
    // 创建一个简单的二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("前序遍历: ");
    preOrderTraversal(root);
    printf("\n");

    printf("中序遍历: ");
    inOrderTraversal(root);
    printf("\n");

    printf("后序遍历: ");
    postOrderTraversal(root);
    printf("\n");

    printf("层次遍历: ");
    levelOrderTraversal(root);
    printf("\n");

    return 0;
}

2.常考题目

某二叉树的后序遍历序列和中序遍历序列相同，均为A、B、C、D、E、F，则按层次输出(同一层从左到右)的序列为()

A、ABCDEF        B、CBAFED        C、FEDCBA        D、DEFCBA

        答案为C。

五、二叉树中常考题目

1.完全二叉树

1.深度为5的完全二叉树的结点数不可能是()

A、15

B、16

C、17

D、18

       

        我觉得这道题的关键在于理解后序遍历和中序遍历相同的情况。后序遍历是左子树、右子树、根节点，中序遍历是左子树、根节点、右子树。题目说这两个序列相同，都是ABCDEF。

        我先假设树的结构，如果每个节点都只有左子节点，中序遍历会是B, A, D, C, F, E，这和ABCDEF不一样。如果每个节点都只有右子节点，中序遍历会是A, B, C, D, E, F，也不对。完全平衡的树也不行，因为后序遍历会是F, D, E, B, C, A，这也不对。

后来我想到，如果后序遍历和中序遍历相同，根节点F必须在序列的末尾。这表明左子树包含所有节点，除了F。所以树的结构应该是：

   F
   /
  E
 /
D
/
C
/
B
/
A

        这棵树的后序遍历是A, B, C, D, E, F，中序遍历也是A, B, C, D, E, F，符合题意。

        接下来，我需要找出这棵树的层次遍历。从根节点F开始，然后是E，然后是D，然后是C，然后是B，最后是A。所以层次遍历应该是FEDCBA。

        选项C是FEDCBA，这和我得到的结果一致。所以答案是C. FEDCBA。


http://www.niftyadmin.cn/n/5863326.html

相关文章

基于ffmpeg+openGL ES实现的视频编辑工具-添加贴纸（八）

基于ffmpeg+openGL ES实现的视频编辑工具-添加贴纸（八）

在当下丰富多元的音视频编辑应用领域，添加贴纸已然成为一项广受欢迎的功能，它能够为音视频作品注入独特的趣味与创意元素。本文将深入探究音视频添加贴纸背后所涉及的技术原理与实现路径。 一、技术原理概述 音视频从本质上来说，是由一系列连续的图像帧（针对视频部分）以…
阅读更多...
排序链表--字节跳动

排序链表--字节跳动

少年的书桌上没有虚度的光阴 题目描述 请你对链表进行排序 思路分析 核心思想&#xff1a;归并排序 有三个部分 链表排序实现 1. merge 函数 21.见 合并两个有序链表&#xff0c; 首先创建一个虚拟头节点 newhead&#xff0c;并使用指针 tail 来构建合并后的链表。 通过…
阅读更多...
Windows安装MySQL教程

Windows安装MySQL教程

1.下载 下载地址&#xff1a;https://www.mysql.com/downloads/ 下载版本&#xff1a;MySQL Installer for Window 2.安装MySQL 以下只列出需要注意的一些界面&#xff0c;没出现的界面默认继续即可。 1.选择安装类型 提供了多种安装模式&#xff0c;包括默认开发版、仅…
阅读更多...
高清下载油管视频到本地

高清下载油管视频到本地

下载工具并安装: yt-dlp官网地址&#xff1a; GitHub - yt-dlp/yt-dlp: A feature-rich command-line audio/video downloader ffmpeg官网地址&#xff1a; Download FFmpeg 注&#xff1a;记住为其添加环境变量 操作命令&#xff1a; 该指令表示以720p码率下载VIDEO_UR…
阅读更多...
深入理解设计模式之解释器模式

深入理解设计模式之解释器模式

深入理解设计模式之解释器模式 在软件开发的复杂世界中，我们常常会遇到需要处理特定领域语言的情况。比如在开发一个计算器程序时，需要解析和计算数学表达式；在实现正则表达式功能时，要解析用户输入的正则表达式来匹配文本。这些场景都涉及到对特定语言的解释和执行，而解…
阅读更多...
ClickHouse系列之ClickHouse安装

ClickHouse系列之ClickHouse安装

ClickHouse系列之ClickHouse安装 1 ClickHouse2 Docker安装ClickHouse2.1 docker 启动脚本2.2 默认用户及密码2.3 8123和9000端口的作用2.3.1 81232.3.2 9000 3 Clickhouse连接3.1 命令行客户端连接3.1.1 常见的客户端脚本3.1.1.1 查看数据库&#xff1a;show databases;3.1.1.…
阅读更多...
【大模型LLM】DeepSeek LLM Scaling Open-Source Language Models with Longtermism

【大模型LLM】DeepSeek LLM Scaling Open-Source Language Models with Longtermism

深度探索LLM&#xff1a;以长期主义扩展开源语言模型 0.论文摘要 开源大语言模型&#xff08;LLMs&#xff09;的快速发展确实令人瞩目。然而&#xff0c;以往文献中描述的扩展规律得出了不同的结论&#xff0c;这为LLMs的扩展蒙上了一层阴影。我们深入研究了扩展规律&#…
阅读更多...
Java常用设计模式-代码实例详解

Java常用设计模式-代码实例详解

1. 单例模式&#xff08;Singleton Pattern&#xff09; 原理 确保一个类只有一个实例&#xff0c;并提供全局访问点。核心是通过私有构造器和静态方法控制实例化。 应用场景 配置管理类数据库连接池日志记录器 代码实例1&#xff1a;日志管理器&#xff08;懒汉式&#x…
阅读更多...
最新文章

Copyright @ 2022~2023