C++(数据结构)：树和二叉树资源-CSDN下载

数据结构

需积分: 3 134 浏览量 2024-08-03 19:51:31 上传评论收藏 1.67MB PDF 举报

资源推荐

资源详情

资源评论

1/16

第 4 章树和二叉树

4.1 树

1、常见的数据结构？

（1）集合

集合的定义是由一组无序且唯一（即不能重

复）的项组成的。不包含任何元素的集合就

叫做空集。

（2）线性结构

线性结构是一个有序数据元素的集合。

常用的线性结构有：线性表，栈，队列，双

队列，数组，串。

元素 1

元素 2

元素 3

元素 4

元素 5

0 1 2 3 4

（3）树

形结构

n 个有限节点组成一个具有层次关系的集

合。

（4）图形结构

图形结构——多个对多个，如图。

2、什么是树？

树：是一种数据结构，它是由 n（n>=0）个有限

节点组成一个具有层次关系的集合。树是一类非线性

结构。这种结构结点之间有分支，并具有层次关系。

它非常类似于自然界中的树。

树的作用：表达家谱顺序、行政组织结构、计算

机文件结构、书的教材章节结构等。

3、树的基本概念

（1）树是 n（n≥0）个结点的有限集。

（2）当 n=0 时称为空树；

（3）当 n>0 时为非空树，在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点

可分

为 m(m ≥0)个互不相交的有限集 T

,…,

，其

中每一个集合又称为一棵树，并且称

为根的子树；同理，每一棵子树又可以分为若干个互不相交的有限集……

总结树的特性：

（1）空树是树的特例;

（2）非空树中至少有一个结点，称为树的根，只有根结点的树称为最小树;

2/16

（3）在含有多个结点的树中，除根结点外，其余结点构成若干棵子树，且各子树间互

不相交。

4、树的基本术语

（1）树的结

点：包含一个数据元素及若干个指向其子树的分支；

（2）结点的度：一

个结点拥有的子树数目；

（3）树的度：一棵树上

所有结点度的最大值；

（4）叶子结点（终端结点）：度为零的结点；

（5）分支结点（非终端结点）

：度大于零的结点；

（6）路径（从根到结点的）：由从根到该结点所经分支和结点构成；

（7）孩子结

点：结点的子树的根称为该结点的孩子结点；

（8）双亲结

点：相应地，该结点称为孩子的双亲结点；

（9）兄弟：

具有同一父结点的子结点互称兄弟；

（10）

堂兄弟：其双亲在同一层的结点互为堂兄弟；

（11）

祖先结点：从根到该结点所经分支上的所有结点；

（12）

子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；

（13）结点的层次：从根结点到该结点所经过的路径长度加 1 ；

（14）树的深度：树

中叶子结点具有的最大层次数；

（15）

树的宽度：整棵树中某一层中最多的结点数称为树的宽度；

（16）

有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称

该树为有序

树，与之相对的是无序树；

（17）第一个孩子：在有序树中，最左边的子树的根称为第一个孩子；

（18）最后一个孩子：在有序树中，最右边的子树的根称为最后一个孩子；

练习

：参照右图的树，回答下列问题

（1）该树有哪些结点

ABCDEFGHIJKLM ，

其中的叶子节点

有 EKLGHIM ，分支节点有

ABCDFJ

。

（2）结点 A 的度为

3 ，结点 B 的度为 2 ，树的度

为 3

。

（3）请写出 A 节点到 K 节

点经过的路径 A->B->F->K 。

（4）H 结点的兄弟结

点有 I、J ，堂兄弟结点有 E、F、G 。

（5）F 结点的祖先结点有 B、A ，子孙结点有 K、L 。

（6）该树的深度为 4 ，树的宽度为 6 。

剩余15页未读，继续阅读

评论收藏

内容反馈

小海狸Xiaohaili

粉丝: 31

C++(数据结构)：树和二叉树

c++数据结构树与二叉树课件

数据结构：树和二叉树 课件

C++数据结构

数据结构中树和二叉树的使用

数据结构树和二叉树(C++)

数据结构树和二叉树——树

数据结构 树、二叉树的数据结构 哈夫曼树

数据结构：实现平衡二叉树的各种算法-C/C++代码类资源

c++数据结构

编程c++ 数据结构理论 树和二叉树

平衡二叉树（纯C++实现）

树和二叉树的实验报告

c++数据结构二叉树

《数据结构课程设计》二叉树基本操作实验程序（10种基本操作）

c++ 数据结构

数据结构 c++

数据结构 c++

数据结构（C++版）

数据结构课设二叉树C++

数据结构：二叉树

树与二叉树的转换

数据结构 C++ 二叉树 广义表

数据结构二叉树的C++实现

C++课程设计二叉树

前端开发环境、运行环境、场景题

FrNm (FlexRay Network Management)

最新资源

数据结构：树和二叉树课件

数据结构树、二叉树的数据结构哈夫曼树

编程c++ 数据结构理论树和二叉树

数据结构 C++ 二叉树广义表