数据结构（七）：树介绍及面试常考算法

一、树介绍

1、定义

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。树有以下特点：

（1）每个节点有零个或多个子节点；

（2）没有父节点的节点称为根节点；

（3）每一个非根结点有且只有一个父节点；

（4）除了根结点外，每个子节点可以分为多个不相交的子树；

2、优缺点及使用场景

优点：清晰的层级关系，快速查找，动态添加、删除和修改节点。

缺点：存在冗余存储，插入和删除的复杂性，高度不平衡等。

适用场景：层次关系、分类和搜索、表达关系和数据可视化等。

3、遍历方法

（1）深度遍历--先序（根-左-右）  

（2）深度遍历--中序（左-根-右）

（3）深度遍历--后序（左-右-根）

先序：【2, 1, 3, 6, 4, 8, 5】

中序：【1, 6, 3, 2, 8, 4, 5】

后序：【6, 3, 1, 8 ,5, 4, 2】

层序：【2, 1 ,4, 3, 8, 5, 6】

（4）层序遍历--自上而下，自左而右

4、主要类型

（1）二叉树

（a）概念：节点度不超过2的树。

（b）特点

（a）每个结点最多有两颗子结点。

（b）左子树和右子树是有顺序的，次序不能颠倒。

（c）即使某结点只有一个子树，也要区分左右子树。

（c）二叉树类型

① 满二叉树：在满二叉树中，除了叶节点外，每个节点都有两个子节点，且所有叶节点都在同一层级上

② 完全二叉树：完全二叉树是指除了最后一层外，其他层都是满的，并且最后一层的节点从左到右连续存在。

③ 二叉搜索树：二叉搜索树是一种有序的二叉树，对于每个节点，其左子树的值都小于节点的值，右子树的值都大于节点的值。这种有序性质使得二叉搜索树在查找、插入和删除等操作上有很高的效率。

④ 平衡二叉树：平衡二叉树是指任意节点的左子树和右子树的高度差不超过1的二叉树。平衡二叉树可以提高插入、删除和查找等操作的效率，常见的平衡二叉树有AVL树和红黑树。

（2）AVL树

（a）介绍：AVL树是一种自平衡的二叉搜索树，它的名称来自于它的发明者Adelson-Velsky和

Landis。AVL树通过在插入和删除节点时进行旋转操作来保持树的平衡。

（b）平衡调整：在AVL树中，每个节点都带有一个平衡因子（balance factor），它表示节点的左

子树高度与右子树高度之差。平衡因子可以是-1、0或1，如果平衡因子的绝对值大于1，就表示树

失去了平衡，需要进行平衡调整。AVL树的平衡调整通过四种旋转操作来完成。

（c）AVL树的特点：

① 平衡性：在AVL树中，任意节点的左子树和右子树的高度差不超过1。

② 严格的排序性：AVL树是一种二叉搜索树，它保持了节点的严格排序性。对于每个节点，左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点。

（3）红黑树

（a）介绍：红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它通过对节点进行颜色标记

和旋转操作来保持树的平衡。

（b）红黑树的特点

① 节点颜色：每个节点被标记为红色或黑色。这是红黑树的核心特征之一。

② 平衡性：红黑树通过一些规则来维持平衡性。具体规则如下：

  • 根节点是黑色。
  • 所有叶节点（NIL节点或空节点）是黑色。
  • 如果一个节点是红色，那么它的两个子节点都是黑色。
  • 从任意节点到其每个叶子节点的路径上，包含相同数量的黑色节点。

③ 排序性：红黑树是一种二叉搜索树，它保持了节点的严格排序性。对于每个节点，左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点。

二、面试关于树结构常考算法

1、求二叉树的高度

题目：给定一颗二叉树，求该数的高度，例如，如下二叉树的高度是4。

思路：有两种方法来求解二叉树的高度，一是递归二是迭代。

递归方法通过递归调用求解左子树和右子树的高度，并取较大值加1得到二叉树的高度。

迭代方法使用层序遍历，每遍历完一层，高度加1，直到遍历完所有节点。

#include<iostream>
#include <algorithm>
#include<queue>
using namespace std;
struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    int data;  
    BinaryTreeNode(int x): data(x), left(NULL),right(NULL) {}
};

// 迭代方法
int FindHeightofTree(BinaryTreeNode* root){
    if (root == nullptr) {
        return 0; // 空树高度为0
    }
    int count = 0;
    while(root != NULL){
        if(root->left || root->right){
            count += 1;
            if(root->left){
                root = root->left;
                continue;
            } 
            if(root->right){
                root = root->right;
                continue;
            } 
        } 
        root = NULL;

    }
    return count + 1;
}

// 递归方法
int getHeight(BinaryTreeNode* root){
    if (root == nullptr) {
        return 0; // 空树高度为0
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return 1 + std::max(leftHeight, rightHeight);
}

int main(){
    BinaryTreeNode* root = new BinaryTreeNode(2);
    root->left = new BinaryTreeNode(1);
    root->right = new BinaryTreeNode(4);
    root->left->right = new BinaryTreeNode(3);
    root->right->left = new BinaryTreeNode(8);
    root->left->right->left = new BinaryTreeNode(5);
    // 递归法
    int res = FindHeightofTree(root);
    // 迭代法
    int res1 = getHeight(root);
    cout<< res1;
    cout<< res;
    // 释放内存，防止内存泄漏
    delete root->left->right->left;
    delete root->right->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;
}

  

2、在二叉搜索树中查找第K个最大值

 题目：如下二叉搜索树，给定k = 5，[19, 18, 17, 16, 15, 12, 9, 5, 3]，则下列二叉搜索树中第5个最大值为15。

思路：二叉搜索树（BST）的后序遍历实际是对树节点的升序排列。所以同第一题，有递归法和迭代法实现BST的中序遍历，遍历后再逆序，返回第k个最大值。

迭代法实现中序遍历：使用一个栈来实现迭代法的中序遍历。先遍历树的左子树，如果当前节点存在左子树，则将当前节点压入栈，直到没有左子树，则记录栈顶元素（temp），并弹出。在遍历当前节点（temp）的右子树。

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

struct BinaryTreeNode{
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    int val;
    BinaryTreeNode(int x): val(x), left(NULL), right(NULL){}
};
int getNthMaxFromTree2(BinaryTreeNode* root, int k){
    vector<int> res;
    stack<BinaryTreeNode*> s;
    BinaryTreeNode* temp;
    //非递归中序遍历
    while(root != NULL || !s.empty()){
        if(root){
            s.push(root);
            root = root->left;
        }
        else{
            temp = s.top();
            s.pop();
            cout << temp->val<<",";
            res.push_back(temp->val);
            root = temp->right;   
        }

    }
     // 降序
    sort(res.rbegin(),res.rend());
    cout << endl;
    for(auto c: res){
        cout<< c << "-";
    }
    return res[k-1]; 
 }


int main(){
    BinaryTreeNode* root = new BinaryTreeNode(12);
    root->left = new BinaryTreeNode(5);
    root->right = new BinaryTreeNode(18);
    root->left->left = new BinaryTreeNode(3);
    root->left->right = new BinaryTreeNode(9);
    root->right->left = new BinaryTreeNode(15);
    root->right->right = new BinaryTreeNode(19);
    root->right->left->right = new BinaryTreeNode(17);
    root->right->left->right->left = new BinaryTreeNode(16);
    int val = getNthMaxFromTree2(root, 5);
    cout << endl <<val;
    // 释放内存，防止内存泄漏
    delete root->right->left->right->left;
    delete root->right->left->right;
    delete root->right->right;
    delete root->right->left;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;
}

 

3、查找与根节点距离K的节点

题目：如下二叉树，给定k = 2， 输出与根节点距离2的节点[3， 8， 5]。

思路： 可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历二叉树，并记录每个节点的距离。当找到距离为K的节点时，将其存储起来。

广度优先搜索（BFS）+队列：我们可以在遍历每一层节点时，将该节点的子节点加入队列（size--控制循环），并记录它们的距离。当距离等于K时，将该节点的值存储起来。

深度优先搜索（DFS）+栈：使用一个栈来存储当前节点和距离的信息。在每次循环中，取出栈顶元素，检查当前距离是否等于K，如果是，则将该节点的值存储到结果数组中。然后，将当前节点的子节点按照右子节点先入栈，左子节点后入栈，并将距离加1。这样，我们可以确保在深度优先搜索中，离根节点更远的节点会在栈中先被访问。

#include<iostream>
#include<stack>
#include<queue>
#include<map>

using namespace std;
typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinaryTreeNode* _pLeft;
    struct BinaryTreeNode* _pRight;
    BTDataType _data;
    BinaryTreeNode(int x): _data(x), _pLeft(NULL), _pRight(NULL){}
    
};

// 二叉树的广度优先遍历+队列实现（非递归）
vector<int> LevelOrder(BinaryTreeNode* root, int k){
    queue<BinaryTreeNode*> que; //使用一个队列来存储当前层的节点
    BinaryTreeNode* temp;
    int distance;
    vector<int> res;
    if(root) que.push(root);
    while(!que.empty()){
        // 记录队列中的节点个数
        int size = que.size();
        if(distance == k){
            while(!que.empty()){
                res.push_back(que.front()->_data);
                que.pop();
            }
            break;
        }
        // 用size--控制循环处理当前层的节点(当前层所有节点出队，下层节点入队)
        while(size--){
        temp = que.front();
        que.pop();
        // cout << temp->_data << ",";
        if(temp->_pLeft) que.push(temp->_pLeft);
        if(temp->_pRight) que.push(temp->_pRight);
    }
    distance++;
}
 return res;   
}


// 二叉树的深度优先遍历（先序）+栈实现（非递归）
vector<int> getKdistanceInOrder(BinaryTreeNode* root, int k){
    vector<int> res;
    stack<pair<BinaryTreeNode*, int>> s; //栈用来存储节点和当前距离
    if(root) s.push({root, 0});
    while(!s.empty()){
        BinaryTreeNode* p = s.top().first;
        int distance = s.top().second;
        s.pop();
        if(distance == k) res.push_back(p->_data); //当距离等于K时，将该节点的值存储起来。
        if(p->_pRight) s.push({p->_pRight, distance + 1});
        if(p->_pLeft) s.push({p->_pLeft, distance + 1});
        
    }
    return res;
}

int main(){
    BinaryTreeNode* root = new BinaryTreeNode(2);
    root->_pLeft = new BinaryTreeNode(1);
    root->_pRight = new BinaryTreeNode(4);
    root->_pLeft->_pRight = new BinaryTreeNode(3);
    root->_pRight->_pLeft = new BinaryTreeNode(8);
    root->_pRight->_pRight = new BinaryTreeNode(7);
    root->_pLeft->_pRight->_pLeft = new BinaryTreeNode(5);
    vector<int> res = LevelOrder(root, 2);
    for(auto c: res){
        cout << c << ",";
    }
    cout << endl;
    vector<int> res2 = getKdistanceInOrder(root, 2);
    for(auto b: res2){
        cout << b << ",";
    }
    // 释放内存
    delete root->_pLeft->_pRight->_pLeft;
    delete root->_pRight->_pRight;
    delete root->_pRight->_pLeft;
    delete root->_pLeft->_pRight;
    delete root->_pRight;
    delete root->_pLeft;   
    
}

4、在二叉树中查找给定节点的祖先节点

祖先节点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。

题目：如下二叉树，给定节点值6，打印节点6的祖先节点 [3, 1, 2]。

思路： 使用递归方法，检查当前节点是否为空，为空就返回false。如果当前节点不为空，检查是否为目标节点，如果是返回true。接下来，递归地在左子树和右子树中查找目标节点，如果在左子树或右子树中找到了目标节点，则将当前节点的值添加到结果数组中，并返回true。如果左子树和右子树都没有找到目标节点，则返回false。

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

struct BinaryTreeNode{
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    int val;
    BinaryTreeNode(int x): val(x), left(NULL), right(NULL){}
};

bool findAncestorsDFS(BinaryTreeNode* root, int target, vector<int>& ancestors) {
    if (root == nullptr) {
        return false;
    }

    if (root->val == target) {
        return true;
    }

    if (findAncestorsDFS(root->left, target, ancestors) || findAncestorsDFS(root->right, target, ancestors)) {
        ancestors.push_back(root->val);
        return true;
    }

    return false;
}


int main(){
    BinaryTreeNode* root = new BinaryTreeNode(2);
    root->left = new BinaryTreeNode(1);
    root->right = new BinaryTreeNode(4);
    root->left->right = new BinaryTreeNode(3);
    root->right->left = new BinaryTreeNode(8);
    root->right->right = new BinaryTreeNode(5);
    root->left->right->left = new BinaryTreeNode(6);
    int target = 6;
    vector<int> ancestors;
    bool res = findAncestorsDFS(root, target, ancestors);
    cout << "节点 " << target << " 的祖先节点值为：";
    for (int val : ancestors) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/248828.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

企业微信旧版-新版网络连接错误，无法登录的解决方案

企业微信旧版-新版网络连接错误，无法登录的解决方案

一.企业微微信无法登录故障 二.解决方案 1.网上的解决方案 **检查网络连接&#xff1a;**确保你的计算机正常连接到互联网。尝试打开其他网页&#xff0c;以确保网络连接正常。 **防火墙和安全软件&#xff1a;**某些防火墙或安全软件可能会阻止企业微信的正常连接。请确保你…
阅读更多...
computed 和 watch 的奇妙世界：让数据驱动你的 Vue 应用(下)

computed 和 watch 的奇妙世界：让数据驱动你的 Vue 应用(下)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
idea2023解决右键没有Servlet的问题

idea2023解决右键没有Servlet的问题

复制Servlet Class.java中的文件。 回到文件&#xff0c;然后点击小加号 然后输入刚刚复制的东西&#xff1a; 3. 此时右键有servlet。 4. 然后他让你输入下面两个框&#xff1a; JAVAEE TYPE中输入Servlet Class Name 表示你要创建的Servlet类的名称是什么。自己起名字。然后…
阅读更多...
寒冷冬天，再次撕下了新能源汽车的续航遮羞布，北方真不适合

寒冷冬天，再次撕下了新能源汽车的续航遮羞布，北方真不适合

随着懂车帝的冬测&#xff0c;新能源汽车的冬天续航成为关注焦点&#xff0c;电池性能在冬天里缩减众所周知&#xff0c;不过从来没有机构告诉消费者&#xff0c;到底冬天电池的续航会减少多少&#xff0c;如今这一切显然暴露在人们眼前了。 懂车帝的冬测显示除了特别优秀的新能…
阅读更多...
Elasticsearch的 8.x常用api汇总

Elasticsearch的 8.x常用api汇总

ES的查询语法比较复杂，对于初学者需要在不断练习中才会逐渐掌握，本文汇总了ES各种查询语法以及常用api，可以作为新手的实用笔记 首先，安装 Kibana！ 下载Elasticsearch，官方下载页面;Elasticsearch 参考，官方文档;<
阅读更多...
「构」向云端 - 我与 2023 亚马逊云科技 re:Invent 大会

「构」向云端 - 我与 2023 亚马逊云科技 re:Invent 大会

授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 亚马逊云科技开发者社区, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚马逊云科技官方渠道 2023年亚马逊AWS re:Invent大会宣布一项Amazon Q的创新项目&#x…
阅读更多...
为什么 GAN 不好训练

为什么 GAN 不好训练

为什么 GAN 不好训练&#xff1f;先看 GAN 的损失&#xff1a; 当生成器固定时&#xff0c;堆D(x)求导&#xff0c;推理得到&#xff08;加号右边先对log求导&#xff0c;再对负项求导&#xff09; 然后在面对最优Discriminator时&#xff0c;Generator的优化目标就变成了&…
阅读更多...
基于BWA，Bowtie2，samtools、checkm等工具计算宏基因组学序列分析中Contigs与Genes在样品中的丰度，多种计算方式和脚本对比

基于BWA，Bowtie2，samtools、checkm等工具计算宏基因组学序列分析中Contigs与Genes在样品中的丰度，多种计算方式和脚本对比

计算contigs和genes相对丰度可以提供有关微生物群落结构和功能的信息。以下是计算这两个指标的意义&#xff1a; 1. Contigs的相对丰度&#xff1a;contigs是利用基因组测序技术获得的碎片序列&#xff0c;通过计算contigs的相对丰度可以了解微生物群落中不同菌种的相对丰度。…
阅读更多...
ARM KEIL 安装

ARM KEIL 安装

根据设备类型安装开发工具及环境 Arm,Cortex ----> MDK-Arm 8051 ----> C51 80251 ----> C251 C166,XC166,XC2000 MCU设备 ----> C155 填写信息提交后下载 点击MDK539.EXE下载 : MDK539.EXE 双击MDK539安装 点击Next 默认安装路径,点击Ne…
阅读更多...
SaaS行业分析

SaaS行业分析

文章目录 什么是SaaS ?SaaS的标准定义什么是软件即服务&#xff1f;SaaS与传统软件的区别 &#xff1f; SaaS行业分析你知道最赚钱的行业是什么&#xff1f;互联网带给企业的变化 SaaS与PaaS、IaaS的区别&#xff1f;IaaS&#xff08;Infrastructure as a Service&#xff09;…
阅读更多...
C与C++编程语言的区别和联系

C与C++编程语言的区别和联系

一、引言 C和C是两种广泛使用的编程语言&#xff0c;它们都在软件开发领域有着广泛的应用。虽然C是从C语言演化而来的&#xff0c;但两者之间存在一些重要的区别和联系。本文将详细介绍这两种编程语言的相同点和不同点&#xff0c;并通过实际例子进行说明。 二、C与C的相同点 …
阅读更多...
微服务组件Sentinel的学习（3）

微服务组件Sentinel的学习（3）

Sentinel 隔离和降级Feign整合Sentinel线程隔离熔断降级熔断策略 授权规则&#xff1a;自定义异常 隔离和降级 虽然限流可以尽量避免因高并发而引起的服务故障&#xff0c;但服务还会因为其它原因而故障。而要将这些故障控制在一定范用避免雪崩&#xff0c;就要靠线程隔离(舱壁…
阅读更多...
BearPi Std 板从入门到放弃 - 先天神魂篇（7）(RT-Thread 定时器-软件定时器)

BearPi Std 板从入门到放弃 - 先天神魂篇（7）(RT-Thread 定时器-软件定时器)

简介 RT-Thread 软件定时器的简单使用步骤 创建项目 参考 BearPi RT-Thread项目创建 定时器管理接口 定时器时钟节拍 定时器管理相关函数 定时器类型 #define RT_TIMER_FLAG_ONE_SHOT 0x0 //一次性计时器 #define RT_TIMER_FLAG_PERIODIC 0x2 // 周期性定时器 #…
阅读更多...
若依框架springboot——修改前端图片上传样式

若依框架springboot——修改前端图片上传样式

简述 使用过若依框架的&#xff0c;一定知道若依前端框架上传图片的样式&#xff0c;是一个正方形加号图片&#xff0c;但是如果你要使用自定义样式呢。 比如将下面这个图进行修改呢 修改后的样式 你可以直接找到element-ui 修改上传图片的组件&#xff0c;也可以加入新的组…
阅读更多...
计算机组成原理-选择语句和循环语句的汇编表示

计算机组成原理-选择语句和循环语句的汇编表示

文章目录 选择语句jmpjxx示例&#xff1a;选择语句的机器级表示扩展&#xff1a;cmp指令的底层原理 循环语句使用条件转移指令实现循环用loop指令实现循环 选择语句 不一定知道指令的位置&#xff0c;所以jmp直接跳转到指令的位置很难办 jmp 标号相当于位置&#xff0c;名字…
阅读更多...
OSPF理论总结与实验

OSPF理论总结与实验

第1章 OSPF[1] 本章阐述了OSPF协议的特征、术语&#xff0c;OSPF的路由器类型、网络类型、区域类型、LSA类型&#xff0c;OSPF报文的具体内容及作用&#xff0c;描述了OSPF的邻居关系&#xff0c;通过实例让读者掌握OSPF在各种场景中的配置。 本章包含以下内容&#xff1a; …
阅读更多...
【Java代码审计】文件上传篇

【Java代码审计】文件上传篇

【Java代码审计】文件上传篇 1.Java常见文件上传方式2.文件上传漏洞修复 1.Java常见文件上传方式 1、通过文件流的方式上传 public static void uploadFile(String targetURL, String filePath) throws IOException {File file new File(filePath);FileInputStream fileInpu…
阅读更多...
node.js 启一个前端代理服务

node.js 启一个前端代理服务

文章目录 前言一、分析技术二、操作步骤2.1、下载依赖2.2、创建一个 serve.js 文件2.3、js 文件中写入以下代码 三、运行&#xff1a; node serve四、结果展示五、总结六、感谢 前言 有时候我们需要做一些基础的页面时&#xff0c;在研发过程中需要代理调用接口避免浏览器跨域…
阅读更多...
设计模式——桥接模式(结构型)

设计模式——桥接模式(结构型)

引言 桥接模式是一种结构型设计模式&#xff0c; 可将一个大类或一系列紧密相关的类拆分为抽象和实现两个独立的层次结构&#xff0c; 从而能在开发时分别使用。 问题 抽象&#xff1f; 实现&#xff1f; 听上去挺吓人&#xff1f; 让我们慢慢来&#xff0c; 先考虑一个简单的…
阅读更多...
Docker Swarm编排：构建简单集群

Docker Swarm编排：构建简单集群

Docker Swarm 是 Docker 官方提供的容器编排工具&#xff0c;通过它可以轻松构建和管理多个 Docker 容器的集群。本文将深入探讨 Docker Swarm 的基础概念、构建集群的步骤&#xff0c;并提供更为丰富和实际的示例代码&#xff0c;帮助大家全面了解如何使用 Docker Swarm 搭建一…
阅读更多...
最新文章

Copyright @ 2022~2023