《《数据结构》课程树和二叉树》由会员分享，可在线阅读，更多相关《《数据结构》课程树和二叉树（146页珍藏版）》请在金锄头文库上搜索。
1、2020 2 5 数据结构 1 第六章树 树形结构是一种重要的非线性结构 在我们的客观世界和现实生活中大量存在 我们学院的组织结构 在计算机领域也常用到树形结构 例如编译程序中用树表示源程序语法结构 数据库系统中用树组织信息等等 2020 2 5 数据结构 2 我们的家谱 2020 2 5 数据结构 3 6 1树的概念 1 树的定义 树 Tree 是n n 0 个结点的有限集合T 它满足如下条件 1 有且仅有一个称为根 Root 的结点 2 其余结点可分为m m 0 个互不相交的有限集合 T1 T2 Tm 其中每个集合又是一棵树 并称其为根的子树 Subtree 这是一个递归定义 有时n 0也
2、称为空树 集合1 集合2 集合3 一 树的基本概念 2020 2 5 数据结构 4 2 树的表示方法 1 树形图法2 嵌套集合法3 广义表形式4 凹入表示法 A B C E F D G 2020 2 5 数据结构 5 1 结点的度 Degree 为该结点的子树的个数 2 树的度 为该树中结点的最大度数 3 终端结点 叶子 度为零的结点 4 非终端结点 分支结点 度不为零的结点 5 内部结点 除根结点之外的分支结点 3 树结构的基本术语 2020 2 5 数据结构 6 6 孩子 child 结点的子树之根双亲 parent 该结点称为孩子的双亲兄弟 sibling 同一双亲的孩子堂兄弟 cous
3、in 双亲不同但其双亲处于同一层的结点7 路径 Path 若树中存在一个结点序列k1 k2 kj 使得ki是ki 1的双亲 1 i j 则称该结点序列是从ki到kj一条路径 Path 路径长度 路径的长度为j 1 其为该路径所经过的边的数目 2020 2 5 数据结构 7 9 结点的层次 Level 从根算起 根结点的层次为1 其余结点的层次为其双亲的层次数加1 11 树的高度 树中结点的最大层次数称为树的高度或深度 Depth 12 有序树 树中每个结点的各子树从左至右有次序之分 不能互换 这样的树称为有序树 8 祖先 Ancestor 若树中结点k到ks存在一条路径 则称k为ks的祖先子孙
4、 descendant ks是k的子孙 2020 2 5 数据结构 8 二 树型结构的逻辑特征 树中任一个结点都可以有零个或多个后继结点 但最多只能有一个前趋结点 有序树中兄弟结点之间从左至右有次序之分 13 森林 m m 0 棵互不相交的树的集合称为森林 2020 2 5 数据结构 9 三 树的逻辑运算 1 setnull T 置T为空树 2 root T 或root x 求树T或结点x所在树的根结点 3 parent T x 求T中x结点的双亲 若x为根或x不在树中 结果为空 4 child T x i 求T中x结点从左至右第i个孩子 若x为叶子或x不在树中 结果为空 2020 2 5 数
5、据结构 10 6 2二叉树 6 2 1二叉树的概念 一 二叉树的定义 二叉树 BinaryTree 是n n 0 个结点的有限集 它或者是空集 n 0 或者由一个根结点和两棵互不相交的 分别称为根的左子树和右子树的二叉树组成 可以看出 二叉树的定义和树的定义一样 均为递归定义 2020 2 5 数据结构 11 二 二叉树的五种基本形态 空二叉树 只有一个根结点的二叉树 右子树为空的二叉树 左子树为空的二叉树 左 右子树均非空的二叉树 注意 二叉树中子树是有左右之分的 即使只有一棵子树 或为左子树 或为右子树 这一点与度为2的有序树不同 这不是二叉树 这是二叉树 2020 2 5 数据结构 12
6、 6 2 2二叉树的性质 性质1 二叉树第i层上的结点数目最多为2i 1 i 1 该性质可用数学归纳法证明 证明 归纳基础 i 1时 有2i 1 20 因为第1层上只有一个根结点 所以命题成立 归纳假设 假设对所有的j 1 j i 命题成立 即第j层上至多有2j 1个结点 证明j i时命题也成立 归纳步骤 根据归纳假设 第i 1层上至多有2i 2个结点 由于二叉树的每一个结点至多有两个孩子 故第i层上的结点数 至多是第i 1层上的最大结点数的2倍 即j i时 该层上至多有2 2i 2 2i 1个结点 故命题成立 2020 2 5 数据结构 13 性质2 深度为k的二叉树至多有2k 1个结点 k
7、 1 证明 在具有相同深度的二叉树中 仅当每一层都含有最大结点数时 其树中结点数最多 因此 利用性质1可得 深度为k的二叉树的结点数至多为 20 21 2k 1 2k 1故命题成立 2020 2 5 数据结构 14 性质3 任意二叉树中 若叶结点的个数为n0 度为2的结点数为n2 则n0 n2 1 证明 设n1为二叉树T中度为1的结点数 因为二叉树中所有结点的度均为小于或等于2 所以其结点总数为 n n0 n1 n2 6 1 另一方面 1度结点有一个孩子 2度结点有两个孩子 故二叉树中孩子结点的总数是n1 2 n2 但树中只有根结点不是任何结点的孩子 故二叉树中的结点总数又可表示为 n n1
8、2 n2 1 6 2 由式 6 1 和 6 2 得n0 n2 1 2020 2 5 数据结构 15 两种特殊形态的二叉树 满二叉树和完全二叉树深度为k且有2k 1个结点的二叉树称为满二叉树 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2 并且最下一层上的结点都集中在该层最左边的若干位置上 则此二叉树称为完全二叉树 2020 2 5 数据结构 16 两种特殊形态的二叉树 满二叉树和完全二叉树深度为k且有2k 1个结点的二叉树称为满二叉树 对满二叉树的结点进行编号 约定编号从根结点起 自上而下 自左至右 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至
9、n的结点一一对应 则称之为完全二叉树 2020 2 5 数据结构 17 根据定义 1 满二叉树是完全二叉树 反之不成立 2 对于完全二叉树 若某结点无左孩子 则必无右孩子 该结点为叶结点 证明 设深度为k 则根据性质2和完全二叉树的定义有2k 1 1 n 2k 1即2k 1 n 2k于是k 1 log2n k 又因为k是整数 所以k 1 log2n 即k log2n 1 性质4 具有n个结点的完全二叉树的深度为 log2n 1 log2 n 1 2020 2 5 数据结构 18 性质5 如果对一棵有n个结点的完全二叉树的结点按层次编号 即自上而下 自左至右 则对任一结点i 11 则其双亲是编号
10、为 i 2 的结点 2 如果2 i n 则结点i无左孩子 否则其左孩子是编号为2 i的结点 3 如果2 i 1 n 则结点i无右孩子 否则其右孩子是编号为2 i 1的结点 4 若i为奇数且不为1 则结点i的左兄弟的编号是i 1 否则 结点i无左兄弟 5 若i为偶数且小于n 则结点i的右兄弟的编号是i 1 否则 结点i无右兄弟 2 3 4 5 1 2020 2 5 数据结构 19 6 2 3二叉树的存储 1 顺序存储结构 1 对于完全二叉树可以采用顺序存储结构 即一维数组 进行存储 编号为i的结点存放在第i个数组元素所分配的存储单元中 完全二叉树结点之间的逻辑关系通过数组元素的下标体现 虚结点
11、占据的空间 补设的 虚结点 2020 2 5 数据结构 20 2 对于非完全二叉树 通过补设一些 虚结点 使得二叉树的结点的编号与完全二叉树相同 再进行顺序存储 每个 虚结点 都将占据一个数组元素存储单元 结论 非完全二叉树采用顺序存储结构会造成存储空间的浪费 2020 2 5 数据结构 21 二叉树除了可以采用顺序存储结构实现存储外 还可以采用链式存储结构进行存储 与采用顺序存储结构相比 采用链式存储结构实现二叉树的存储显得更自然 1 链式存储结构中结点的结构 指向左孩子的指针域 指向右孩子的指针域 存放数据 2 链式存储结构 2020 2 5 数据结构 22 2 结点的存储描述 typed
12、efstructnode datatypedata structnode lchild rchild bitree bitree root 所有类型为node的结点 再加上一个指向根结点的头指针root 就构成了二叉树的存储结构 称为二叉链表 2020 2 5 数据结构 23 例 说明 1 一个二叉链表由头指针唯一确定 若二叉树为空 则root NULL 2 在n个结点的二叉树中一共有2n个指针域 n 1个为空 n 1个非空 2020 2 5 数据结构 24 3 二叉链表是二叉树最常用的存储结构 还有其它链接方法 采用何种方法 主要取决于所要实施的各种运算频度 例 若经常要在二叉树中寻找某结点
13、的双亲时 可在每个结点上再加一个指向其双亲的指针域parent 称为三叉链表 2020 2 5 数据结构 25 特殊的 为了方便找到结点的双亲 还可以在结点结构中增加一个指向该结点双亲的指针域 dada lchild parent rchild 左指针 数据域 双亲指针 右指针 2020 2 5 数据结构 26 若二叉树中每一个结点均采用上述第一或第二种结构 由此便实现了二叉树的链式存储 这种存储结构又称为二叉链表或三叉链表 此外 还需引入一个指针变量 使其指向根结点 该指针变量说明如下 bitree root 2020 2 5 数据结构 27 2 结点的存储描述 typedefstructn
14、ode datatypedata structnode lchild rchild bitree bitree root 所有类型为node的结点 再加上一个指向根结点的头指针root 就构成了二叉树的存储结构 称为二叉链表 2020 2 5 数据结构 28 3 二叉树的生成 1 顺序存储结构非常简单 从终端上读入数据填入数组 2 二叉链表的生成 基本思想 按完全二叉树的层次顺序 非完全二叉树添加虚结点 依次输入结点信息 若输入的结点不是虚结点 则建立一个新结点 若新结点是第一个结点 则令其为根结点 否则将新结点作为孩子链接到它的双亲结点上 如此重复下去 直至所有结点送完并以特殊字符结束 实现
15、技巧 实现过程中引入一个指针队列 该队列中的每个元素指向相应结点 2020 2 5 数据结构 29 事实上 先入队的结点其孩子必将先入队 因此front指针指向的队列元素所指向的结点为当前必须与其孩子建立链接的双亲结点 而rear指针指向的队列元素所指向的结点为当前必须与其双亲建立链接的孩子结点 当rear为偶数时 为左孩子 否则为右孩子 算法描述 bitree q maxsize 队列q为bitree指针类型的数组 bitree creattree charch intfront rear bitree root s root NULL 置空二叉树 front 1 rear 0 置空队列 c
16、h getchar 2020 2 5 数据结构 30 前者简单 不在此讨论 这里仅说明后者的处理方法 基本思想 按完全二叉树的层次顺序 非完全二叉树添加虚结点 依次输入结点信息 若输入的结点不是虚结点 则建立一个新结点 若新结点是第一个结点 则令其为根结点 否则将新结点作为孩子链接到它的双亲结点上 如此重复下去 直至所有结点送完并以特殊字符结束 算法在实现过程中引入一个指针队列 该队列中的每个元素指向相应结点 注意一个事实 先入队的结点其孩子必将先入队 因此front指针指向的队列元素所指向的结点为当前必须与其孩子建立链接的双亲结点 而rear指针指向的队列元素所指向的结点为当前必须与其双亲建立链接的孩子结点 当rear为偶数时 为左孩子 否则为右孩子 算法描述 bitree q maxsize 队列q为bitree指针类型的数组 bitree creattree charch intfront rear bitree root s while ch 为结束符号 s NULL if ch 为虚结点符号 不是虚结点时建立新结点 s malloc sizeof bitree s data
