第4章 树和二叉树.pdf

青少年编程C++

第4章树和二叉树

4.1树

1、常见的数据结构？

1（2）线性结构

集合的定义是由一组无序且唯一（即不能重线性结构是一个有序数据元素的集合。

复）的项组成的。不包含任何元素的集合就常用的线性结构有：线性表，栈，队列，双

叫做空集。队列，数组，串。

元素1元素2元素3元素4元素5

01234

（3）树形结构（4）图形结构

n个有限节点组成一个具有层次关系的集图形结构——多个对多个，如图。

合。

2、什么是树？

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

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

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

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

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

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

3、树的基本概念

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

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

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

可分为m(m≥0)个互不相交的有限集T,T,…,T，其中每一个集合又称为一棵树，并且称

12m

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

总结树的特性：

（1）空树是树的特例;

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

1/16

青少年编程C++

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

不相交。

4、树的基本术语

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

（2）结点的度：一个结点拥有的子树数目；

（3）树的度：一棵树上所有结点度的最大值；

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

（5）分支结点（非终端结点）：度大于零的结点；

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

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

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

（9）兄弟：具有同一父结点的子结点互称兄弟；

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

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

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

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

（14）树的深度：树中叶子结点具有的最大层次数；

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

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

该树为有序树，与之相对的是无序树