数据结构-树和二叉树-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
一、实验目的：
理解二叉树特别是完全二叉树的性质，掌握二叉树的存储结构（二叉链表）；熟练掌握二叉树的常用操作算法（初始化、插入结点、删除结点、遍历等）；初步掌握二叉树的应用。
二、实验内容：
要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。
具体要求如下：
①给出基于二叉链表的二叉树类的定义；
②给出二叉树初始化（构造函数）的实现；
③给出二叉树三种遍历算法的递归实现；
④二叉树先序遍历的非递归算法实现；
⑤利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度；
⑥二叉树的撤销删除
三、实验步骤：
1、需求分析：
本演示程序用JAVA编写，完成树的生成，任意位置的插入、删除，以及遍历二叉树中的结点，查找和修改树中元素的值。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；遍历时采用三种遍历方法中的一种遍历方法；修改操作时需要输入的元素的值；查找操作时，需要找到要查找元素的位置。在所有输入中，元素的值都是整数。
② 输出的形式：在所有四种操作中都显示操作是否正确以及操作后树中的内容。其中删除操作后显示删除的元素的值，遍历二叉树中的元素，查找操作、修改操作后显示修改的值。
③ 程序所能达到的功能：完成树的生成（通过插入操作）、插入、删除、遍历、查找、修改操作。
④ 测试数据：
A． 树中已有以50,25,75,12,37,43,30,33,87,93,97为关键字的结点
B． 插入操作中依次输入10，20，30，40，50，60，70，80，90，100十个数
C． 删除操作中输入10删除值为10的元素
D． 查找操作中输入20，30，40，50返回这个元素在树中的位置
2．概要设计：
1）为了实现上述程序功能，需要定义树的抽象数据类型：
public int iData;
public double dData;
public Node leftChild;
public Node rightChild;
private Node root;int value;
private Node getSuccessor；
基本操作：{
Tree ()
操作结果：构造一个空的二叉树
insert ()
初始条件：是否存在一个空二叉树
操作结果：往二叉树中插入数值
delete ()
初始条件：存在一非空的二叉树
操作条件：将二叉树中的元素删除
displayTree ()
初始条件：存在一非空的树
操作条件：显示非空树中的所有元素的值
getString ()
初始条件：存在一非空的二叉树
操作结果：返回整个字符串的数值
getChar ()
初始条件：存在一非空的二叉树
操作结果：返回字符型的数值
getInt ()
初始条件：存在一非空的二叉树
操作结果：返回整型的数值
find ()
初始条件：存在一非空二叉树
操作结果：从二叉树中查找某一元素
traverse ()
初始条件：存在一非空的二叉树
操作结果：对二叉树中的元素进行遍历
preorder ()
初始条件：存在一非空的二叉树
操作结果：对二叉树中的元素进行先根遍历
inOrder ()
初始条件：存在一非空的二叉树
操作结果：对二叉树中的元素进行中根遍历
postOrder ()
初始条件：存在一非空的二叉树
操作结果：对二叉树中的元素进行后根遍历
DisplayNode ()
初始条件：存在一非空的二叉树
操作结果：显示出二叉树中的整形数值和双精度浮点型数值
public static void main
操作结果：调用主函数
2022-12-14 19:34:01
111KB
1
（4）二叉树转换成森林
抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
2022-03-03 22:56:42
3.39MB
1