有没有专门做建材的网站,wordpress 调取栏目,网站域名备案密码,wordpress必备文件组合数据结构之二叉树的性质与存储结构 1、二叉树的性质2、二叉树的存储结构 数据结构是程序设计的重要基础#xff0c;它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发#xff0c;分析和研究计算机加工的数据的特性#xff0c;… 数据结构之二叉树的性质与存储结构 1、二叉树的性质2、二叉树的存储结构 数据结构是程序设计的重要基础它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发分析和研究计算机加工的数据的特性以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法为提高利用计算机解决问题的效率服务。 数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的
逻辑结构数据元素及元素之间关系的存储称为
存储结构(或物理结构)。数据结构按照逻辑关系的不同分为
线性结构和
非线性结构两大类其中非线性结构又可分为树结构和图结构。 树结构是一种非常重要的非线性结构该结构中的一个数据元素可以有两个或两个以上的直接后继元素树可以用来描述客观世界中广泛存在的层次结构关系。 二叉树是 n(n≥0)个结点的有限集合它或者是空树(n0)或者是由一个根结点及两棵不相交的且分别称为左、右子树的二叉树所组成。可见二叉树具有递归性质。 1、二叉树的性质 1二叉树第 i 层(i≥1)上最多有 2i-1 个结点。 2高度为 k 的二叉树最多有 2k-1 个结点 (k≥1)。 由性质 1每一层的结点数都取最大值 Σ i 1 k 2 i − 1 2 k − 1 {\huge\Sigma}^k_{i1}2^{i-1} 2^k-1 Σi1k2i−12k−1 即可。 3对于任何一棵二叉树若其终端结点数为 n0度为2的结点数为 n2则n0n21。 4具有n 个结点的完全二叉树的深度为[log2n]1。 若深度为 k 的二叉树有 2k-1 个结点则称其为满二叉树。可以对满二叉树中的结点进行连续编号 约定编号从根结点起自上而下、自左至右依次进行。深度为 k、有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从1至n 的结点一一对应时称之为完全二叉树。满二叉树如下图 (a)所示高度为 3 的一个完全二叉树如下图 (b) 所示。 在一个高度为 h 的完全二叉树中除了第 h 层即最后一层其余各层都是满的。在第 h 层上的结点必须从左到右依次放置不能留空。下图 © 所示的二叉树不是完全二叉树因为 6号结点的左边有空结点。
2、二叉树的存储结构 1二叉树的顺序存储结构 顺序存储是用一组地址连续的存储单元存储二叉树中的结点必须把结点排成一个适当的线性序列并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。 用一组地址连续的存储单元存储二叉树中的结点必须把结点排成一个适当的线性序列并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。对于深度为 k 的完全二叉树除第k层外其余各层中含有最大的结点数即每一层的结点数恰为其上一层结点数的两倍由此从一个结点的编号可推知其双亲、左孩子和右孩子的编号。 假设有编号为 i 的结点则有 ● 若 i1则该结点为根结点无双亲若 i1则该结点的双亲结点为[i/2]。 ● 若 2≤n则该结点的左孩子编号为 2i否则无左孩子。 ● 若 2i1≤n则该结点的右孩子编号为 2i1否则无右孩子。 完全二叉树的顺序存储结构如下图所示。 显然完全二叉树采用顺序存储结构既简单又节省空间对于一般的二叉树则不宜采用顺序存储结构。因为一般的二叉树也必须按照完全二叉树的形式存储也就是要添上一些实际并不存在的“虚结点”这将造成空间的浪费如下图所示。 在最坏情况下一个深度为 k 且只有 k 个结点的二叉树单支树 需要 2k-1 个存储单元。 2二叉树的链式存储结构 由于二叉树的结点中包含有数据元素、左子树的根、右子树的根及双亲等信息因此可以用三叉链表或二叉链表即一个结点含有 3 个指针或两个指针来存储二叉树链表的头指针指向二叉树的根结点如下图所示。 设结点中的数据元素为整型则二叉链表的结点类型定义如下:
typedef struct BiTnode{int data;struct BiTnode *lchild,*rchild;
}BiTnode.*BiTree;在不同的存储结构中实现二叉树的运算方法也不同具体应采用什么存储结构除考虑二叉树的形态外还应考虑需要进行的运算特点。
