数据结构-树和二叉树-PPT
树是一种非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。在客观世界中，树形结构广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。
树的定义：树是一棵n（n≥0）个结点的有限集，它或为空树（n=0），或为非空树。对于非空树T：
* 有且仅有一个称之为根的结点；
* 除根结点以外的其余结点可分为m（m>0）个互不相交的有限集T1，T2， …，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
树的表示方法有多种，如树形表示法、文氏图表示法、凹入图表示法、广义表表示法等。
树的基本术语包括：
* 结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树。
* 非终端结点和终端结点：度不为0的结点称为非终端结点或分支结点。度为0的结点称为终端结点或叶结点。
* 孩子结点、双亲结点和兄弟结点：在一棵树中，结点的子树的根（直接后继），被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。
* 堂兄弟结点：双亲结点在同一层的结点互为堂兄弟结点。
* 路径与路径长度：对于任意两个结点di和dj，若树中存在一个结点序列di, di1, di2, …, din, dj，使得序列中除di外的任一结点都是其在序列中的前一个结点的后继，则称该结点序列为由di到dj的一条路径，用路径所通过的结点序列（di, di1, di2, …, dj）表示这条路径。路径长度等于路径所通过的结点数目减1（即路径上分支数目）。
* 祖先结点、子孙结点：从根结点到该结点的路径上所经过的所有结点，被称作该结点的祖先结点。以某结点为根的子树中的任一结点，都称为该结点的子孙结点。
* 结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推。一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度（或树的深度）。
二叉树是树的一种特殊情况，它的每个结点最多有两个孩子结点。二叉树可以分为满二叉树和完全二叉树两种。满二叉树是一种特殊的二叉树，它的每个结点都有两个孩子结点，或者它是一个叶结点。完全二叉树是一棵具有n个结点的二叉树，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同。
单分支二叉树是所有结点都没有右孩子的二叉树，右右支支树树是所有结点都没有左孩子的二叉树。
树和二叉树是非常重要的数据结构，它们广泛应用于计算机科学和信息技术领域。
2025-06-19 10:33:20
3.3MB
1
数据结构实例教程（C语言版）：第6章 树和二叉树的结构分析与应用.ppt
2022-06-25 09:09:20
2.63MB