当前位置：文档之家 › 数据结构实例精讲：二叉树及其存储

数据结构实例精讲：二叉树及其存储

  • 格式：docx
  • 大小：113.05 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

数据结构（二十四）二叉树的链式存储结构（二叉链表）

数据结构（二十四）二叉树的链式存储结构（二叉链表）

数据结构（⼆⼗四）⼆叉树的链式存储结构（⼆叉链表） ⼀、⼆叉树每个结点最多有两个孩⼦，所以为它设计⼀个数据域和两个指针域，称这样的链表叫做⼆叉链表。

⼆、结点结构包括：lchild左孩⼦指针域、data数据域和rchild右孩⼦指针域。

三、⼆叉链表的C语⾔代码实现：#include "string.h"#include "stdio.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* ⽤于构造⼆叉树********************************** */int index=1;typedef char String[24]; /* 0号单元存放串的长度 */String str;Status StrAssign(String T,char *chars){int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;}}/* ************************************************ */typedef char TElemType;TElemType Nil=''; /* 字符型以空格符为空 */Status visit(TElemType e){printf("%c ",e);return OK;}typedef struct BiTNode /* 结点结构 */{TElemType data; /* 结点数据 */struct BiTNode *lchild,*rchild; /* 左右孩⼦指针 */}BiTNode,*BiTree;/* 构造空⼆叉树T */Status InitBiTree(BiTree *T){*T=NULL;return OK;}/* 初始条件: ⼆叉树T存在。

二叉树的储存结构的实现及应用

二叉树的储存结构的实现及应用

二叉树的储存结构的实现及应用二叉树是一种常见的数据结构，它在计算机科学和算法设计中广泛应用。

二叉树的储存结构有多种实现方式，包括顺序储存结构和链式储存结构。

本文将从这两种储存结构的实现和应用角度进行详细介绍，以便读者更好地理解二叉树的储存结构及其在实际应用中的作用。

一、顺序储存结构的实现及应用顺序储存结构是将二叉树的节点按照从上到下、从左到右的顺序依次存储在一维数组中。

通常采用数组来实现顺序储存结构，数组的下标和节点的位置之间存在一定的对应关系，通过数学计算可以快速找到节点的父节点、左孩子和右孩子。

顺序储存结构的实现相对简单，利用数组的特性可以迅速随机访问节点，适用于完全二叉树。

1.1 实现过程在采用顺序储存结构的实现中，需要首先确定二叉树的深度，然后根据深度确定数组的长度。

通过数学计算可以得到节点间的位置关系，初始化数组并按照规定的顺序将二叉树节点逐一填入数组中。

在访问二叉树节点时，可以通过计算得到节点的父节点和子节点的位置，从而实现随机访问。

1.2 应用场景顺序储存结构适用于完全二叉树的储存和遍历，常见的应用场景包括二叉堆和哈夫曼树。

二叉堆是一种特殊的二叉树，顺序储存结构可以方便地实现它的插入、删除和调整操作，因此在堆排序、优先队列等算法中得到广泛应用。

哈夫曼树则是数据压缩领域的重要应用，通过顺序储存结构可以有效地构建和处理哈夫曼树，实现压缩编码和解码操作。

二、链式储存结构的实现及应用链式储存结构是通过指针将二叉树的节点连接起来，形成一个类似链表的结构。

每个节点包含数据域和指针域，指针域指向节点的左右孩子节点。

链式储存结构的实现相对灵活，适用于任意形态的二叉树，但需要额外的指针空间来存储节点的地址信息。

2.1 实现过程在链式储存结构的实现中，每个节点需要定义为一个包含数据域和指针域的结构体或类。

通过指针来连接各个节点，形成一个二叉树的结构。

在树的遍历和操作中，可以通过指针的操作来实现节点的访问和处理，具有较高的灵活性和可扩展性。

数据结构-二叉树的存储结构和遍历

数据结构-二叉树的存储结构和遍历

return(p); }
建立二叉树
以字符串的形式“根左子树右子树”定义 一棵二叉树
1）空树 2）只含一个根 结点的二叉树 A 3）
B C
A
以空白字符“ ”表示
以字符串“A ”表示
D
以下列字符串表示 AB C D
建立二叉树 A B C C
T
A ^ B ^ C^ ^ D^
D
建立二叉树
Status CreateBiTree(BiTree &T) {
1 if (!T) return;
2 Inorder(T->lchild, visit); // 遍历左子树 3 visit(T->data); } // 访问结点 4 Inorder(T->rchild, visit); // 遍历右子树
后序（根）遍历
若二叉树为空树，则空操
根
左 子树
右 子树
作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。
统计二叉树中结点的个数
遍历访问了每个结点一次且仅一次
设置一个全局变量count=0
将visit改为:count++
统计二叉树中结点的个数
void PreOrder (BiTree T){ if (! T ) return; count++; Preorder( T->lchild); Preorder( T->rchild); } void Preorder (BiTree T,void( *visit)(TElemType& e)) { // 先序遍历二叉树 1 if (!T) return; 2 visit(T->data); // 访问结点 3 Preorder(T->lchild, visit); // 遍历左子树 4 Preorder(T->rchild, visit);// 遍历右子树 }

二叉树的现实中典型例子

二叉树的现实中典型例子

二叉树的现实中典型例子二叉树是一种常用的数据结构，它具有广泛的应用。

下面列举了十个二叉树在现实中的典型例子。

一、文件系统文件系统是计算机中常见的二叉树应用之一。

文件系统中的目录和文件可以组织成一棵树，每个目录称为一个节点，而文件则是叶子节点。

通过树的结构，我们可以方便地对文件和目录进行管理和查找。

二、组织架构企业或组织的组织架构通常可以用二叉树来表示。

每个部门可以看作是一个节点，而员工则是叶子节点。

通过组织架构树，我们可以清晰地了解到企业或组织内部的管理层级关系。

三、家谱家谱是一个家族的血缘关系的记录，一般可以用二叉树来表示。

每个人可以看作是一个节点，而父子关系则是节点之间的连接。

通过家谱树，我们可以追溯家族的历史和血缘关系。

四、编译器编译器是将高级语言转换为机器语言的程序。

在编译过程中，编译器通常会使用语法分析树来表示源代码的结构。

语法分析树是一种特殊的二叉树，它将源代码表示为一个树状结构，方便进行语法分析和编译优化。

五、数据库索引数据库中的索引是一种用于提高数据查询效率的数据结构。

常见的索引结构包括B树和B+树，它们都是二叉树的变种。

通过索引树，数据库可以快速地定位到需要查询的数据，提高数据库的检索性能。

六、表达式求值在数学计算中，表达式求值是一项重要的任务。

通过使用二叉树，我们可以方便地表示和计算表达式。

二叉树的叶子节点可以是操作数，而内部节点可以是运算符。

通过遍历二叉树，我们可以按照正确的顺序对表达式进行求值。

七、电路设计在电路设计中，二叉树也有广泛的应用。

例如，我们可以使用二叉树来表示逻辑电路的结构，每个门电路可以看作是一个节点，而连接线则是节点之间的连接。

通过电路设计树，我们可以方便地进行电路的布线和优化。

八、图像处理图像处理是一项常见的计算机技术，而二叉树在图像处理中也有重要的应用。

例如，我们可以使用二叉树来表示图像的像素信息，每个像素可以看作是一个节点，而像素之间的关系则是节点之间的连接。

数据结构 耿国华 西北大学 6-3二叉树的存储结构

数据结构 耿国华 西北大学 6-3二叉树的存储结构

C
7
单支树
D
15
第 6 章 树和二叉树 6.2 二叉树 存储结构：② 链式存储结构：二叉链表
结点结构:
lchild data rchild
typedef srtoroutct Node
{
A
DataType daAta;
B
C
struct struct
BNo∧de Node
* *
rlcchhCiilldd;;
结点结构: parent lchild data rchild root
A
∧A
B
C
B∧
C
D
E
G
F ∧D
∧ E∧ ∧ F∧
∧ G∧
7
第 6 章 树和二叉树 6.2 二叉树
8
返回
D
E }FBiTN∧oDde, *BiT∧reeE; ∧ ∧ F ∧
∧ G∧
G
5
第 6 章 树和二叉树 6.2 二叉树 存储结构：② 链式存储结构：二叉链表
结点结构:
lchild data rchC
D
E
G
F ∧D
∧ E∧ ∧ F∧
∧ G∧
6
第 6 章 树和二叉树 6.2 二叉树 存储结构：② 链式存储结构：三叉链表
ABCDE F GHI J KL
2
1A
2B
3D
5C
7E
14 F
1 2 3 4 5 6 7 8 9 10 11 12 13 14
AB D C E
F
可见，对于一般的二叉树，按照完全二叉树 的编号来存储，会造成空间的极大浪费。
单支树就是一个极端情况：
A

数据结构实验二叉树

数据结构实验二叉树

实验六：二叉树及其应用一、实验目的树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。

其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。

如算术表达式：a+b*(c-d)-e/f三、实验要求如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。

求二叉树的深度。

十进制的四则运算的计算器可以接收用户来自键盘的输入。

由输入的表达式字符串动态生成算术表达式所对应的二叉树。

自动完成求值运算和输出结果。

四、实验环境PC微机DOS操作系统或Windows 操作系统Turbo C 程序集成环境或Visual C++ 程序集成环境五、实验步骤1、根据二叉树的各种存储结构建立二叉树；2、设计求叶子结点个数算法和树的深度算法；3、根据表达式建立相应的二叉树，生成表达式树的模块；4、根据表达式树，求出表达式值，生成求值模块；5、程序运行效果，测试数据分析算法。

六、测试数据1、输入数据：2.2*（3.1+1.20）-7.5/3正确结果：6.962、输入数据：(1+2)*3+(5+6*7);正确输出：56七、表达式求值由于表达式求值算法较为复杂，所以单独列出来加以分析：1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。

例如有如下的中缀表达式：a+b-c转换成后缀表达式为：ab+c-然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。

如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。

计算机数据结构知识点梳理 二叉树的定义及其主要特征

计算机数据结构知识点梳理 二叉树的定义及其主要特征

当 n ≠ 2k , 即 n 不是2的方幂或者 n = 2k 但是一棵满二叉树，其高度为
。
当 n = 2k 但是非满二叉树，其高度为
。
②有n个结点的完全k叉树的高度为
。
性质5推广：一棵满k叉树，如果按层次顺序从1开始对全部结点编号，
①编号为p=1的结点无父结点，否则编号为p结点的父结点的编号是
（k≥2）；
[题1]若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有（ ）个结点。
A.32
B.64
C.63
D.不存在第7层
分析：根据二叉树的性质，第7层至多有64（27-1）个结点，但是题目中给出了二叉树的结点 总数126，由此来判断第7层是否可以有64个结点？
要在二叉树的第7层达到最多的结点个数，其上面6层必须是一个满二叉树，深度为6的满 二叉树有63（26－1）个结点，由此可以判断出此二叉树的第7层不可能达到64个结点，最 多是126-63=63个结点。
（2）完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到 右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树 中的位置相同，则这棵二叉树称为完全二叉树。它的特点是：叶子结点只能出现在最下 层和次下层，且最下层的叶子结点集中在树的左部。
任何完全二叉树中度为1的结点只有0个或1个。
中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：
（1）如果i＞1，则序号i的结点的双亲结点的序号为 ；如果i＝1，则序号为i的结点是根 结点，无双亲结点。
（2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i＞n，则序号为i的结 点无左孩子。
（3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1＞n，则 序号为i的结点无右孩子。

【数据结构】二叉树

【数据结构】二叉树

【数据结构】⼆叉树【⼆叉树】 ⼆叉树是最为简单的⼀种树形结构。

所谓树形结构，其特征（部分名词的定义就不明确给出了，毕竟不是学术⽂章。

）在于： 1. 如果是⾮空的树形结构，那么拥有⼀个唯⼀的起始节点称之为root（根节点） 2. 除了根节点外，其他节点都有且仅有⼀个“⽗节点”；除此外这些节点还都可以有0到若⼲个“⼦节点” 3. 树中的所有节点都必须可以通过根节点经过若⼲次后继操作到达 4. 节点之间不会形成循环关系，即任意⼀个节点都不可能从⾃⾝出发，经过不重复的径路再回到⾃⾝。

说明了树形结构内部蕴含着⼀种“序”，但是不是线性表那样的“全序” 5. 从树中的任意两个节点出发获取到的两个任意⼦树，要不两者⽆交集，要不其中⼀者是另⼀者的⼦集 限定到⼆叉树，⼆叉树就是任意⼀个节点⾄多只能有两个⼦节点的树形结构。

也就是说，某个节点的⼦节点数可以是0,1或2。

由于可以有两个⼦节点，所以区别两个⼦节点可以将其分别定义为左⼦节点和右⼦节点。

但是需要注意的是，若⼀个节点只有⼀个⼦节点，那么也必须明确这个⼦节点是左⼦节点还是右⼦节点。

不存在“中⼦节点”或者“单⼦节点”这种表述。

由于上述规则对所有节点都⽣效，所以⼆叉树也是⼀个递归的结构。

事实上，递归就是⼆叉树⼀个⾮常重要的特点，后⾯还会提到很多通过递归的思想来建⽴的例⼦。

对于左⼦节点作为根节点的那颗⼆叉树被称为相对本节点的左⼦树，右⼦树是同理。

■ 基本概念 空树 不包含任何节点的⼆叉树，连根节点也没有 单点树 只包含⼀个根节点的⼆叉树是单点树 ⾄于兄弟关系，⽗⼦关系，长辈后辈关系是⼀⾔既明的就不说了。

树中没有⼦节点的节点被称为树叶（节点），其余的则是分⽀节点。

⼀个节点的⼦节点个数被称为“度数”。

正如上所说，⼆叉树任意节点的度数取值可能是0，1或2。

节点与节点之间存在关联关系，这种关联关系的基本长度是1。

通过⼀个节点经过若⼲个关联关系到达另⼀个节点，经过的这些关联关系合起来被称为⼀个路径。

数据结构二叉树知识点总结

数据结构二叉树知识点总结

数据结构二叉树知识点总结二叉树是指每个节点最多有两个子节点的树结构。

它是一种重要的数据结构，在算法和程序设计中被广泛应用。

下面是对二叉树的主要知识点进行详细总结。

1.二叉树的基本概念：-树节点：树的基本单元，包含数据项（节点值）和指向其他节点的指针。

-根节点：树的第一个节点。

-叶节点（又称为终端节点）：没有子节点的节点。

-子节点：一些节点的下一级节点。

-父节点：一些节点的上一级节点。

-兄弟节点：拥有同一父节点的节点。

-深度：从根节点到当前节点的路径长度。

-高度：从当前节点到最远叶节点的路径长度。

2.二叉树的分类：-严格二叉树：每个节点要么没有子节点，要么有两个子节点。

-完全二叉树：除了最后一层外，其他层的节点数都达到最大，并且最后一层的节点依次从左到右排列。

-满二叉树：每个节点要么没有子节点，要么有两个子节点，并且所有叶节点都在同一层上。

-平衡二叉树：任意节点的两棵子树的高度差不超过13.二叉树的遍历：-前序遍历：根节点->左子树->右子树。

递归实现时，先访问当前节点，然后递归遍历左子树和右子树。

-中序遍历：左子树->根节点->右子树。

递归实现时，先递归遍历左子树，然后访问当前节点，最后递归遍历右子树。

-后序遍历：左子树->右子树->根节点。

递归实现时，先递归遍历左子树，然后递归遍历右子树，最后访问当前节点。

-层序遍历：从上到下，从左到右依次访问每个节点。

使用队列实现。

4.二叉查找树（BST）：-二叉查找树是一种有序的二叉树，对于树中的每个节点，其左子树的节点的值都小于当前节点的值，右子树的节点的值都大于当前节点的值。

-插入操作：从根节点开始，递归地比较要插入的值和当前节点的值，根据比较结果向左或向右移动，直到找到插入位置为止。

-查找操作：从根节点开始，递归地比较要查找的值和当前节点的值，根据比较结果向左或向右移动，直到找到目标节点或到叶节点。

-删除操作：有三种情况：-被删除节点是叶节点：直接将其删除。

数据结构实验报告二叉树

数据结构实验报告二叉树

数据结构实验报告二叉树二叉树是一种重要的数据结构，广泛应用于计算机科学和算法设计中。

在本次实验中，我们通过实际编程实践，深入理解了二叉树的基本概念、性质和操作。

一、二叉树的定义和基本性质二叉树是一种特殊的树结构，每个节点最多有两个子节点。

它具有以下基本性质：1. 根节点：二叉树的顶部节点称为根节点，它没有父节点。

2. 子节点：每个节点最多有两个子节点，分别称为左子节点和右子节点。

3. 叶节点：没有子节点的节点称为叶节点。

4. 深度：从根节点到某个节点的路径长度称为该节点的深度。

5. 高度：从某个节点到其叶节点的最长路径长度称为该节点的高度。

6. 层次遍历：按照从上到下、从左到右的顺序遍历二叉树的节点。

二、二叉树的实现在本次实验中，我们使用C++语言实现了二叉树的基本操作，包括创建二叉树、插入节点、删除节点、查找节点等。

通过这些操作，我们可以方便地对二叉树进行增删改查。

三、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树的所有节点。

常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：先访问根节点，然后依次递归遍历左子树和右子树。

2. 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

3. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

四、二叉树的应用二叉树在计算机科学和算法设计中有广泛的应用。

以下是一些常见的应用场景：1. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树的值都小于根节点的值，右子树的值都大于根节点的值。

它可以高效地支持插入、删除和查找操作，常用于有序数据的存储和检索。

2. 堆：堆是一种特殊的二叉树，它的每个节点的值都大于（或小于）其子节点的值。

堆常用于实现优先队列等数据结构。

3. 表达式树：表达式树是一种用二叉树表示数学表达式的方法。

通过对表达式树的遍历，可以实现对数学表达式的计算。

4. 平衡树：平衡树是一种特殊的二叉树，它的左右子树的高度差不超过1。

二叉树的二叉链表存储及基本操作

二叉树的二叉链表存储及基本操作

二叉树的二叉链表存储及基本操作《二叉树的二叉链表存储及基本操作》一、二叉树的二叉链表表示及存储1．定义二叉树的二叉链表存储表示是把一个二叉树存放在计算机中的一种表示形式，它是由一组以结点对象为元素的链表构成的，结点对象中包括数据域和结构域。

数据域存放结点的数据元素；结构域由两个指针域组成，其中一个指向左孩子，另一个指向右孩子。

2．存储形式二叉树的二叉链表存储表示可以用如下的存储形式表示：typedef struct BTNode {TElemType data; // 结点的数据域struct BTNode *lchild; // 指向左孩子的指针域struct BTNode *rchild; // 指向右孩子的指针域} BTNode; // 树结点的定义typedef BTNode *BiTree; // 定义二叉树的指针类型3．空的二叉树把一个指向树结点的指针设为NULL，称为一个空的二叉树。

一般在某个树被销毁后，都要把该树设置成空树。

二、二叉树的基本操作1．求二叉树的结点数要求二叉树的结点数，可以用递归的方法求解。

求n个结点的二叉树的结点数，可以先求出它的左子树结点数，右子树结点数，再加上根结点的数量就得到了结点数。

// 求二叉树的结点数int CountBTNode(BiTree T){if (T == NULL) // 空树，结点数为0return 0;else // 左子树结点数 + 右子树结点数 + 1return CountBTNode(T -> lchild) + CountBTNode(T -> rchild) + 1;}2．求二叉树叶结点数要求二叉树叶结点数，也可以用递归的方法求解。

当一个结点的左子树为空树，右子树也为空树时，它就是一个叶结点，则叶结点数加1；如果结点不是叶结点，则继续求它的左子树叶结点数和右子树叶结点数，再把它们加起来就是该二叉树的叶结点数。

// 求二叉树叶结点数int CountBTLeaf(BiTree T){if (T == NULL) // 空树，叶结点数为0return 0;else if (T -> lchild == NULL && T -> rchild == NULL) //判读是否是叶结点return 1;else // 左子树叶结点数 + 右子树叶结点数return CountBTLeaf(T -> lchild) + CountBTLeaf(T -> rchild);}3．求二叉树深度要求二叉树深度，也可以用递归的方法求解。

数据结构C语言版_二叉树的三叉链表存储表示

数据结构C语言版_二叉树的三叉链表存储表示
TElemType RightSibling(BiPTree T,TElemType e)
{
BiPTree a;
if(T) // 非空树
{
a=Point(T,e); // a是结点e的指针
// T中存在结点e且e存在右兄弟
if(a&&a!=T&&a->parent->rchild&&a->parent->rchild!=a)
int BiTreeEmpty(BiPTree T)
{
if(T)
return 0;
else
return 1;
}
// 返回T的深度
int BiTreeDepth(BiPTree T)
{
int i,j;
if(!T)
return 0;
if(T->lchild)
{
QElemType data; //数据域
struct QNode *next; //指针域
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,//队头指针，指针域指向队头元素
rear; //队尾指针，指向队尾元素
}LinkQueue;
int DeQueue(LinkQueue *Q,QElemType *e) f((*Q).front==(*Q).rear)
return 0;
p=(*Q).front->next; //队头元素
*e=p->data;
(*Q).front->next=p->next;

二叉树的顺序存储结构代码

二叉树的顺序存储结构代码

二叉树的顺序存储结构代码介绍二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。

在计算机中，我们通常使用顺序存储结构来表示二叉树。

顺序存储结构是将二叉树的节点按照从上到下、从左到右的顺序依次存储在一个数组中。

本文将详细介绍二叉树的顺序存储结构代码，包括初始化、插入节点、删除节点以及遍历等操作。

二叉树的顺序存储结构代码实现初始化二叉树首先，我们需要定义一个数组来存储二叉树的节点。

假设数组的大小为n，则二叉树的最大节点数量为n-1。

# 初始化二叉树，将数组中所有元素置为空def init_binary_tree(n):binary_tree = [None] * nreturn binary_tree插入节点在二叉树的顺序存储结构中，节点的插入操作需要保持二叉树的特性，即左子节点小于父节点，右子节点大于父节点。

插入节点的算法如下：1.找到待插入位置的父节点索引parent_index。

2.如果待插入节点小于父节点，将其插入到父节点的左子节点位置，即数组索引2*parent_index+1处。

3.如果待插入节点大于父节点，将其插入到父节点的右子节点位置，即数组索引2*parent_index+2处。

# 插入节点def insert_node(binary_tree, node):index = 0 # 当前节点的索引值，初始值为根节点的索引值while binary_tree[index] is not None:if node < binary_tree[index]:index = 2 * index + 1 # 插入到左子节点else:index = 2 * index + 2 # 插入到右子节点binary_tree[index] = node删除节点删除节点需要保持二叉树的特性，即在删除节点后，仍然满足左子节点小于父节点，右子节点大于父节点的条件。

删除节点的算法如下：1.找到待删除节点的索引delete_index。

二级公共基础知识2-数据结构与算法2(二叉树)

二级公共基础知识2-数据结构与算法2(二叉树)

起泡排序 快速排序 简单选择排序 堆排序 直接插入排序 折半插入排序 希尔排序
选择排序 排序方法 插入排序
归并排序等
1.8.2 插入排序
直接插入、折半插入
1、直接插入排序: • 基本思想：从数组的第2号元素开始， 顺序从数组中取出元素，并将该元素插 入到其左端已排好序的数组的适当位置 上。 • 在最坏情况下需要n(n-1)/2次比较
E
F
0
0
0
0
2h-1= 24-1 = 15 若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。 一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。
North China Electric Power University
(2).二叉树的链式存储结构(二叉链表)
链结点的构造为
(2) 二叉树的基本性质
A、 二叉树的第i层上至多有2 i-1（i 1）个结点。
1
2 3
4 8 9
10
5
11 12
6
13 14
7
15
第三层上(i=3)，有23-1=4个节点。
第四层上(i=4)，有24-1=8个节点。
(2) 二叉树的基本性质
A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多含有2h-1个结点。
组 成 原 理 试 验 室
管 理 信 息 系 统 研 究 室
知 识 工 程 研 究 室
微 机 应 用 研 究 室
A
树中的基本术语：
B C F
D
H I
1.结点、结点的度、树的度 P32中 E
2.叶子结点、分支结点 3.孩子、双亲、兄弟、 堂兄弟、祖先、子孙 4.结点的层次、树的深度 5.有序树和无序树
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构实例精讲：二叉树及其存储树形结构是一类非常重要的非线性结构，它用于描述数据元素之间的层次关系，如人类社会的族谱和各种社会组织机构的表示等等。

在计算机领域中，树形结构的应用也非常广泛，磁盘文件的目录结构就是一个典型的例子。

树和二叉树是常用的树形结构，由于二叉树表示对于树的存储和运算有很大意义，可以把对于树的许多处理转换到对应的二叉树中去做，因此，本章重点讨论二叉树的有关概念、存储结构和常用操作。

5.1 树和二叉树的基本概念5.1.1 树的基本概念树是一个或多个结点组成的有限集合T，有一个特定的结点称为树的根结点，其余的结点被分成m（m≥0）个不相交的集合T1、T2、…、Tm。

，每一个集合本身又是一棵树，被称为这个根结点的子树。

图5-1所示是一棵具有10个结点的树，结点A为树的根结点，除A之外的其余结点分为3个不相交的集合T1={B，E，F}、T2={C，G}和T3=｛D，H，I，J｝，形成了结点A的3棵子树，T1、T2和T3本身也分别是一棵树。

例如，子树T1的根结点为B，其余结点又分为两个不相交的集合{E}和{F}，它们形成了子树T1的根结点B的两棵子树。

图5-1 一棵具有10个结点的树树的基本术语有：孩子、双亲、兄弟：树中某结点的各子树的根称做该结点的孩子；相应地该结点称做其孩子的双亲；具有相同双亲的结点互称为兄弟。

图5-1中，结点B、C、D都是结点A的孩子，结点A是结点B的双亲，也是结点C、D的双亲，结点B、C、D互为兄弟。

结点的度：一个结点所拥有的子树的个数称为该结点的度。

图5-1中，结点A的度为3，结点B的度为2，结点E的度为0。

叶结点、分支结点：度为0的结点称为叶结点，或者称为终端结点；度不为0的结点称为分支结点，或者称为非终端结点。

图5-1中，结点A、B、C、D为分支结点，结点E、F、G、H、I、J为叶结点。

结点的层数：规定树的根结点的层数为1，其他任何结点的层数等于它的双亲结点的层数加1。

图5-1中，结点A的层数为1，结点B、C、D的层数为2，结点E、F、G、H、I、J的层数为3。

树的深度：一棵树的叶结点的最大层数称为树的深度。

图5-1所示的树的深度为3。

5.1.2 二叉树的基本概念二叉树是结点的有限集合，这个有限集合或者为空集（称为空二叉树），或者由一个根结点及两棵不相交的、分别称做这个根的左子树和右子树的二叉树组成。

图5-2所示的是一棵二叉树，根结点为A，其左子树包含结点B、D、G、H，右子树包含结点C、E、F、I、J。

根A的左子树又是一棵二叉树，其根为结点B，有非空的左子树（由结点D、G、H组成）和空的右子树。

根A的右子树也是一棵二叉树，其根为结点C，有非空的左子树（由结点E、I、J组成）和右子树（由结点F组成）。

图5-2 二叉树上面介绍的树的基本术语在二叉树中同样适用，但需要说明的是，尽管树和二叉树的概念之间有许多关系，但它们是两个概念。

二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树是有序的，二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

例如，图5-3中是四棵不同的二叉树，但如果作为树，它们就是相同的了。

图5-3 四棵不同的二叉树满二叉树和完全二叉树是两种特殊形态的二叉树。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的一棵二叉树称做满二叉树。

完全二叉树：一棵深度为k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i （1≤i ≤n ）的结点与满二叉树中编号为i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

显然，一棵满二叉树必定是一棵完全二叉树。

在图5-4中，（a ）为一棵满二叉树，（b ）为一棵完全二叉树，（c ）为一棵非完全二叉树。

图5-4 满二叉树、完全二叉树和非完全二叉树5.1.3 二叉树的性质二叉树具有下列重要性质：【性质1】在二叉树中，第i 层的结点数最多为2i - 1个（i ≥1）。

利用归纳法来证明。

i=1时，只有一个根结点，2i – 1=20=1成立。

假设对所有的i=k （k ≥1）命题成立，即第k 层上至多有2k - 1个结点。

则当i=k+1时，由于二叉树的每个结点的度数至多为2，所以在第k+1层上的最大结点数为第k 层上的最大结点数的2倍，即2*2k - 1=2k ，命题成立。

【性质2】在深度为k 的二叉树中，结点总数最多为2k - 1个（k ≥1）。

由性质1知，深度为k 的二叉树的最大结点数为122i (111-==∑∑=-=k ki i k i 层上的最大结点数）第（5-1）可见，所谓满二叉树就是深度为 k 且有2k - 1个结点的二叉树，即一棵满二叉树中，每一层的结点数均达到了最大值。

【性质3】对任何一棵二叉树T ，如果其终端结点数为n 0 ，度为2的结点数为n 2 ，则n 0 = n 2 + 1。

设二叉树T 中度为1的结点数为n 1，因为二叉树中结点的度数均小于或等于 2，所以其结点总数为n = n 0 + n 1 + n 2 （5-2）又设B 为二叉树T 中总的分支数目。

因为除根结点外，其余结点都有一个分支进入，所以B = n - 1。

但这些分支是由度数为1或2的结点射出的，所以又有B = n 1 + 2 n 2 ，于是得n=n 1+2n 2+1 （5-3）由式（5-2）和式（5-3）得 n 0 = n 2 + 1【性质4】具有n个结点的完全二叉树的深度为[log2n] + 1 。

证明：假设深度为k，则根据性质2和完全二叉树的定义有2k -1- 1 < n≤2k-1 或2k - 1≤n < 2k于是k - 1≤log2n<k因为k是整数，所以k =[log2n] + 1【性质5】如果对一棵有n个结点的完全二叉树的结点从1到n按层序编号，则对任一结点i（1≤i≤n），有：1) 如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲是结点[i / 2]。

2) 如果2i> n，则结点i无左孩子（结点i为叶子结点）；否则，其左孩子是结点2i。

3) 如果2i + 1> n，则结点i无右孩子；否则，其右孩子是结点2i + 1。

5.2 二叉树的存储1．二叉树的顺序存储结构所谓顺序存储结构，就是用一组连续的存储单元存放二叉树中的结点。

完全二叉树由于其结构上的特点，通常采用顺序方式存储。

按从上至下、从左到右的次序将一棵有n个结点的完全二叉树的所有结点从1到n编号，就得到结点的一个线性序列，如同图5-4（b）所示。

由二叉树的“性质5”知道，在完全二叉树中从一个结点的编号就可以推知它的双亲及左、右孩子结点的编号，即完全二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上至下、从左到右的顺序存储树中所有结点的数据信息，通过数组元素的下标关系反映完全二叉树中结点之间的逻辑关系。

图5-5给出了图5-4（b）所示的完全二叉树的顺序存储示意图（注意由于数组下标从0开始，因此数组元素的下标等于结点在完全二叉树中的序号减1）。

数组下标树中结点图5-5 完全二叉树的顺序存储示意图对于一般的二叉树，如果仍按照从上至下、从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能反映二叉树中结点之间的逻辑关系，这时我们假设可将一般二叉树进行改造，增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。

在二叉树中假设增添的结点在数组中所对应的元素值为“空”。

图5-6给出了图5-4（c）所示的非完全二叉树的顺序存储示意图。

数组下标树中结点图5-6 非完全二叉树的顺序存储示意图2．二叉树的链式存储结构二叉树的链式存储结构是用链建立二叉树中结点之间的关系，通常采用的链式存储结构为二叉链表。

所谓二叉链表，是将二叉树中的结点设置为如下的结构体类型：其中data表示保存结点本身信息的信息域，lchild和rchild分别为指向结点的左孩子和右孩子的指针域。

由于每个结点有两个指针域，所以形象地称之为二叉链表。

当二叉树采用二叉链表存储结构时，如果某结点的左孩子或右孩子不存在，则相应的指针域为空。

此外，设置一指针变量指向二叉树的根结点，称之为头指针。

和单链表中头指针的作用相似，二叉链表中的头指针可以唯一地确定一棵二叉树。

图5-7给出了图5-4（c）所示的非完全二叉树的二叉链表存储示意图。

图5-7 二叉链表存储示意图【实例5-1】创建二叉树。

编写程序，根据输入的结点信息建立二叉树的二叉链表存储结构。

（1）问题分析。

定义二叉树的二叉链表存储方式的结点结构为：struct BiTNode{TElemType data;BiTNode* lchild;BiTNode* rchild;};定义二叉树类型为：typedef BiTNode* BiTree;在建立二叉树的二叉链表存储结构时，可以通过输入各个非终端结点的情况来完成二叉树的创建。

设有二叉树如图5-8所示，该树有9个结点，先动态分配一个指向二叉链表结点类型的指针数组pNode[9]，依次输入9个结点的元素值ch，为每个结点i（0<=i<9）分配存储空间，用指针pNode[i]指向结点i所分配的存储空间，使该结点的数据域等于ch，两个指针域均为空；然后依次输入结点间的关系，输入时按“父结点序号、左子结点序号和右子结点序号方式”定义。

若某结点不存在左子或右子结点，则子结点序号输入为0。

定义关系时，每个非终端结点定义一次，叶子结点无需定义。

例如输入“1 2 3”，则表示结点A的左子结点为B，右子结点为C，由这一输入可以修改结点A的左子和右子指针域，从而将它们链接起来。

图5-8 一棵二叉树（2）源程序。

#include <iostream>using namespace std;typedef char TElemType;struct BiTNode{TElemType data;BiTNode* lchild;BiTNode* rchild;};typedef BiTNode* BiTree;BiTNode* CreateBiTNode(TElemType value){BiTNode* pNode = new BiTNode();pNode->data = value;pNode->lchild = NULL;pNode->rchild = NULL;return pNode;}void ConnectTreeNodes(BiTNode* pParent, BiTNode* pLeft, BiTNode* pRight) {if(pParent != NULL){pParent->lchild = pLeft;pParent->rchild = pRight;}}void PrintTreeNode(BiTNode* pNode){{cout<<"结点"<<pNode->data<<" 的";if(pNode->lchild != NULL)cout<<"左子为"<< pNode->lchild->data;elsecout<<"左子为空";if(pNode->rchild != NULL)cout<<" ，右子为"<< pNode->rchild->data<<"。

相关主题