首页 > 其他分享 >考研系列-数据结构第五章:树与二叉树(上)

考研系列-数据结构第五章:树与二叉树(上)

时间:2024-06-19 15:31:27浏览次数:11  
标签:结点 遍历 后序 中序 二叉树 数据结构 线索 考研

目录

写在前面:

一、树的基本知识点

1.树的基本概念

2.树的常见术语

(1)结点之间的关系描述

(2)结点、树的属性描述

(3)有序树和无序树对比

(4)树和森林对比

(5)总结

3.树常考性质

(1)结点数=总度数+1

(2)度为m的树 VS m叉树

(3)树的层数(高度)和结点个数

(4)求树最多/最少结点个数

(5)给定结点个数求树最小高度

(6)考点总结

4.易错习题

(1)选择题

(2)简答题

二、二叉树

1.二叉树的概念和几种特殊的二叉树

2.二叉树的性质

(1)二叉树叶子结点比二分支结点(左右孩子均存在的结点)多1

(2)结点数量与层数关系

(3)树的高度与结点数量关系

3.完全二叉树

(1)结点数量与高度关系

(2)可以由结点总数量求得度分别为0、1、2的结点数量

4.二叉树存储结构

(1)顺序存储

①代码定义

②常考的基本操作

(2)链式存储

①代码定义

②初始化根结点

③插入新结点

④查找p结点及p结点的左右孩子

(3)知识点总结

5.易错习题总结

三、二叉树的遍历和线索二叉树

1.二叉树的先中后序遍历

(1)手算求遍历序列

(2)画图法求遍历序列

(3)代码实现

①先序遍历

②中序遍历

③后序遍历

(4)递归遍历求树的高度

(5)总结

2.二叉树的层序遍历

(1)算法思想

(2)代码实现

(3)扩展思路

3.由遍历序列构造二叉树

(1)先序+中序

①还原思路

②举例说明

③代码实现(java实现)

(2)后序+中序

①还原思路

②举例说明

(3)层序+中序

①还原思路

②举例说明

(4)总结

4.线索二叉树的概念

(1)线索二叉树基本概念、定义

(2)线索二叉树存储结构

①中序线索二叉树

②先序线索二叉树

​编辑③后序线索二叉树

(3)三种线索二叉树对比

(4)二叉树的线索化(代码实现)

①中序线索化

②先序线索化

③后序线索化

(5)在线索二叉树中找前驱或后继(分支结点或叶子结点)

①中序线索二叉树

②先序线索二叉树

③后序线索二叉树

④总结

5.易错习题总结

(1)选择题

(2)简答题

四、总结

五、参考


写在前面:

本章知识点、代码很多,所以这里将树与二叉树部分分成两篇文章来写,减少阅读压力

一、树的基本知识点

1.树的基本概念

树的结构一般是

标签:结点,遍历,后序,中序,二叉树,数据结构,线索,考研
From: https://blog.csdn.net/hehe_soft_engineer/article/details/139706283

相关文章

  • 【数据结构】顺序表
    Hi~!这里是奋斗的小羊,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎~~......
  • 复习数据结构的第八天(串)
    串的概念字符串的概念很简单,就是一堆字符形成的有限序列。比如"看到这里的都是帅哥","abcdef"等都是字符串。而字符串字符的个数就是字符串的长度。通常一个字符串的结束标识是'\0'。对串的操作通常都是针对子串进行的,子串可以理解为就是一个字符串的子集,比如"帅哥"就是"看到......
  • 数据结构与算法-红黑树的java实现-构建红黑树
    红黑树红黑树是一种二分查找树,与普通的二分查找树不同的一点是,红黑树的每个节点都有一个颜色(color)属性。该属性的值要么是红色,要么是黑色。通过限制从根到叶子的任何简单路径上的节点颜色,红黑树确保没有比任何其他路径长两倍的路径,从而使树近似平衡。节点红黑树的节......
  • 列举几种常见的数据结构,以及线性数据结构
    数据结构是计算机科学中用来组织、存储和管理数据的方式。它定义了数据元素之间的逻辑关系,以及如何对数据进行操作。数据结构的选择对于算法的效率至关重要,因为它直接影响到数据在计算机中的存储和访问方式。以下是几种常见的数据结构:数组(Array):数组是一种线性数据结构,用......
  • 【面试八股总结】Redis数据结构及底层实现
    一、五种基本数据结构        Redis提供了丰富的数据类型,常见的有五种数据类型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合)结构类型结构可存储值结构读写能力使用命令底层数据结构String字符串、整数或浮点数对字符串或字符串的一部分进行操作,对整数或浮点......
  • 103. 二叉树的锯齿形层序遍历
    /***Definitionforabinarytreenode.*typeTreeNodestruct{*Valint*Left*TreeNode*Right*TreeNode*}*/funczigzagLevelOrder(root*TreeNode)[][]int{//层序遍历改下ifroot==nil{returnnil}que......
  • 【408考点之数据结构】数据结构的基本概念
    数据结构的基本概念基本概念和术语数据结构是计算机科学中一个非常重要的概念,它描述了数据元素之间的关系及其在计算机内存中的组织方式。理解数据结构的基本概念和术语是学习数据结构的第一步。数据结构可以分为逻辑结构和存储结构两类。逻辑结构是指数据元素之间的逻辑......
  • 【408考点之数据结构】算法和算法评价(时间空间复杂度)
    算法和算法评价算法的基本概念在计算机科学中,算法是解决特定问题的一系列步骤。一个好的算法应该具备以下五个基本特性:有穷性:算法必须在有限的步骤内终止。确定性:每一步骤都必须明确,没有歧义。可行性:算法的每个步骤都可以通过基本运算在有限时间内完成。输入:一个算法有零......
  • 从零开始学数据结构系列之第三章《先序线索二叉树查找及总代码》
    文章目录查找下一个节点总代码往期回顾查找下一个节点​  我们为啥没有像中序二叉树一样有第一个节点,因为我们一开始最大就是我们的根节点,所以无需遍历去寻找我们的第一个节点,我们的T就是我们的第一个节点​我们回过来看中序线索二叉树的节点应该是怎么写的/*......
  • 二叉树的基础讲解
    二叉树在遍历,查找,增删的效率上面都很高,是数据结构中很重要的,下面我们来基础的认识一下。(高级的本人还没学,下面的代码用伪代码或C语言写的)我会从树,树的一些专有名词,树的遍历,二叉树,二叉树的遍历以及后面升级的树进行一部分的介绍。树首先我们从最开始的树来进行讲解,我们知道......